Поняття графа. Теорія графів – важливий розділ дискретної математики, який зародився при розв’язанні головоломок та ігор

Теорія графів – важливий розділ дискретної математики, який зародився при розв’язанні головоломок та ігор, таких як задача про кенігсбергські мости (1736 р.), задача про три криниці і три будинки, гра Гамільтона, задача про чотири фарби. Зараз ця теорія стала потужним засобом дослідження і розв’язання багатьох задач, які виникають при дослідженні великих і складних систем, зокрема обчислювальних. Одним з основних напрямків її використання в обчислювальній техніці є побудова та опис ефективних алгоритмів і аналіз їх складності.

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

Основним поняттям є поняття графа.

Означення 2.1.1. Графом G називають пару об’єктів G(Х,Г), де Х – скінчена непорожня множина, а Г – скінчена підмножина прямого добутку Х´Х´N (можливо і порожня), причому Х називають множиною вершин, а Г – множиною дуг графа G.

Наприклад: , , де , , , , , . У позначенні дуги вершини та , які визначають дугу, називають кінцевими або граничними, причому перша координата вказує на вихідну вершину дуги , друга координата – на вхідну, а де nÎN – номер дуги для позначення різних дуг з однаковими вихідними та вхідними вершинами (при цьому не обов’язково використовують номери від 1 до кількості дуг).

Означення 2.1.2. Дві вершини графа називають суміжними, якщо вони є кінцевими для хоча б однієї дуги.

Означення 2.1.3. Дві дуги графа називають суміжними, якщо вони мають принаймні одну спільну вершину.

Зауважимо, що суміжність – відношення між однорідними елементами графа – вершиною і вершиною, дугою і дугою. Для позначення відношення між різнорідними елементами графа вводять поняття “інциденція”.

Означення 2.1.4. Дугу та вершину графа називають інцидентними, якщо ця вершина є початком або кінцем даної дуги (першою або другою проекцією: або .

У наведеному прикладі графа вершини x₁ і x₂, x₂ і x₃, x₄ і x₅ – суміжні, а x₁ і x₃, x₃ і x₄, x₅ і x₆ – несуміжні, дуги и₁ і и₂, и₄ і и₆ – суміжні, а и₁ і и₄, и₃ і и₆ – несуміжні, вершина x₁ і дуга и₁ – інцидентні, а вершина x₁ і дуга и₄ – неінцидентні.

Дуги з однаковими кінцевими вершинами називають паралельними або кратними. У наведеному прикладі ребра u₁ та u₂ – паралельні.

Якщо кінцеві вершини дуги однакові, то її називають петлею. Дуга є петлею.

Граф, який не містить петель і паралельних ребер називають простим, у протилежному випадку – мультиграфом.

Граф G є графом порядку n, якщо множина його вершин складається з n елементів: .

Якщо у графі G вершина x_i не є початком і кінцем жодного ребра, то її називають ізольованою. У прикладі: вершина x₆ – ізольована.

Граф, який складається з ізольованих вершин, тобто не містить жодного ребра, називають нуль-графом, порожнім або виродженим.

Якщо у графі вершина x_i є початком або кінцем лише одного ребра, то її називають висячою або тупиком. У прикладі вершина x₃ – висяча.

Якщо граф має n вершин (n>1) і кожна пара вершин з’єднана ребром, то його називають повним.

Граф називають плоским, якщо він має геометричну реалізацію на площині.

Області площини, окреслені ребрами плоского графа, називають його гранями.

Граф G(Х,Г) називають дводольним, якщо множину його множин X можна розбити на дві такі підмножини X₁ та X₂, що кожне ребро, яке належить Г має одну кінцеву вершину у множині X₁, а другу – в X₂.

Рефлективним називають граф, що має петлю у кожній вершині.

Симетричним називають граф, у якому кожній дузі u=(x₁,x₂) відповідає дуга u’=(x₂,x₁).

Транзитивним називають граф, у якому існування дуг u₁=(x₁,x₂) і u₂=(x₂,x₃) означає існування дуги u₃=(x₁,x₃).

Граф G(X,Г) називають орієнтованим або орграфом, якщо розрізняють початкову і кінцеву вершини дуги. Для геометричного зображення використовують стрілки.

У випадку орієнтованого графа, його ребра називають дугами, заданими впорядкованими парами (трійками):

Тоді, коли зв’язок між вершинами не позначений стрілками, його називають ребром графа, причому початок x_i і кінець x_j ребра не розрізняють, тобто пара (x_i, x_j) є не впорядкованою.

Якщо дуги (x_i,x_j,n) та (x_j,x_i,n) є різними, то ребро – це підмножина виду , причому номери n – однакові.

Графи бувають неорієнтованими, орієнтованими та змішаними: