Основні властивості графів.

Теорія графів — одна з істотних частин математичного апарату інформатики та кібернетики. У термінах теорії графів можна сформулювати багато задач, пов'язаних із дискретними об'єктами. Такі задачі виникають у проектуванні інтегральних схем і схем управління, у дослідженні автоматів, в економіці й статистиці, теорії розкладів і дискретній оптимізації.

Термін „граф" уперше з'явився в книзі видатного угорського математика Д. Кеніга 1936 p., хоча перші задачі теорії графів пов'язані ще з іменем Л. Ейлера (XVIII ст.).

Простим графом називають пару G=(V, Е), де V — непорожня скінченна множина елементів, називаних вершинами, Е — множина невпорядкованих пар різних елементів із V. Елементи множини Е (невпорядковані пари різних вершин) називають ребрами.

Приклад. На рис. 1 зображено простий граф G з множиною вершин V={v₁, v₂, v₃, v₄} : множиною ребер E= {{v₁, v₂}, {v₁, v₃), {v₂, v₃}, {v₃, v₄}}.

Рисунок 1 – Простий граф G

Говорять, що ребро {u, v} з'єднує вершини u та v. Оскільки Е — множина, то з простому графі пару вершин може з'єднувати не більше ніж одне ребро.

Іноді розглядають графи, у яких дві вершини можуть бути з'єднані більше ніж одним ребром. Так виникає поняття мультиграфа. Мультиграфом називають пару (V, Е), де V — скінченна непорожня множина вершин, а Е — сім'я невпорядкованих пар різних елементів множини V. Тут застосовано термін „сім'я" замість поняття „множина", бо елементи в Е (ребра) можуть повторюватись. Ребра, що з'єднують одну й ту саму пару вершин, називають кратними (або паралельними). Окрім кратних ребер розглядають також петлі, тобто ребра, які з'єднують вершину саму із собою. Псевдографом називають пару (V, Е), де V — скінченна непорожня множина вершин, а Е — сім'я невпорядкованих пар не обов'язково різних вершин.

Приклад. На рис. 2 зображено мультиграф (рис. 2, а) і псевдограф (рис. 2, б).

Рисунок 2 – Мультограф та псевдограф

Розглянуті три типи графів називають неоріентованими. Псевдограф — це найзагальніший тип неорієнтованого графа, бо він може містити петлі й кратні ребра. Мультиграф — це неорієнтований граф, який може містити кратні ребра, але не може містити петель. Нарешті, простий граф — це неорієнтований граф без кратних ребер і без петель.

Розглядають також орієнтовані графи. Орієнтованим графом називають пару (V, Е), де V — скінченна непорожня множина вершин, а Е – множина впорядкованих пар елементів множини V. Елементи множини Е в орієнтованому графі називають дугами (чи орієнтованими ребрами). Дугу (u, v) називають петлею.

Приклад. На рис. 3 зображено орієнтований граф із множиною вершин V={v₁, v₂, v₃, v₄, v₅}: множиною дуг E= {{v₂, v₁}, {v₂, v₃), {v₃, v₂}, {v₃, v₄},{v₄, v₃},{v₄, v₅},{v₅, v₅}}.

Рисунок 3 – Орієнтований граф

Дві вершини u та v в неорієнтованому графі G називають суміжними, якщо {u, v} — ребро: {u, v}Е. Якщо е={u, v} — ребро, то вершини u та v називають його кінцями. Два ребра називають суміжними, якщо вони мають спільний кінець. Вершину v та ребро e називають інцидентними, якщо вершина v — кінець ребра e. Зазначимо, що суміжність — це зв'язок між однорідними елементами графа, а інцидентність — зв'язок між його різнорідними елементами.

Степінь вершини в неорієнтованому графі — це кількість інцидентних їй ребер, причому петлю враховують двічі. Степінь вершини v позначають deg(f). Якщо deg(e) = 0, то вершину v називають ізольованою; якщо deg(a) = 1 — висячою, або лицевою.

Приклад. У неорієнтованому графі на рис. 4 степені вершин такі: deg(v₁)=4, deg(v₂)=4, deg(v₃)=6, deg(v₄)=1, deg(v₅)=3, deg(v₆)=0. Отже, вершина v₆ — ізольована, a v₄ — висяча.

Рисунок 4 – Степені вершин у неорієнтованого графу