Поняття графа

Тема 2.1. ОСНОВНІ ЕЛЕМЕНТИ ТЕОРІЇ ГРАФІВ

Теорія графів – важливий розділ дискретної математики, який зародився при розв’язанні головоломок та ігор, таких як задача про кенігсбергські мости (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 – однакові.

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

Дата добавления: 2014-10-17