іжними, якщо вони мають спільну кінцеву вершину.
Два ребра називаються кратними, якщо множини їх кінцевих вершин збігаються.
Ребро називається петлею, якщо його кінці збігаються, тобто e= {v, v }.
Ступенем degV вершини V називають кількість інцидентних їй ребер (при цьому петлі вважають двічі).
Вершина називається ізольованою, якщо вона не є кінцем ні для одного ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.
програмний граф ізоморфний інтерфейс
1.1 Орієнтований граф
Орієнтований граф (скорочено орграф) G - це впорядкована пара G:=(V, A), для якої виконані наступні умови:
· V - це непорожнє безліч вершин або вузлів,
· A - це безліч (впорядкованих) пар різних вершин, званих дугами або орієнтованими ребрами.
Дуга - це впорядкована пара вершин (v, w), де вершину v називають початком, а w - кінцем дуги. Можна сказати, що дуга v - w веде від вершини v до вершини w.
1.2 Змішаний граф
Змішаний граф G - це граф, в якому деякі ребра можуть бути орієнтованими, а деякі - неорієнтованими. Записується впорядкованої трійкою G:=(V, E, A), де V, E і A визначені так само, як вище. Орієнтований і неорієнтовний графи є окремими випадками змішаного.
1.3 Ізоморфні графи
Граф G називається ізоморфним графу H, якщо існує біекція f з безлічі вершин графа G в безліч вершин графа H, що володіє наступною властивістю: якщо в графі G є ребро з вершини A в вершину B, то в графі H має бути ребро з вершини f (A) в вершину f (B) і навпаки - якщо в графі H є ребро з вершини A в вершину B, то в графі G повинно бути ребро з вершини f ^ {- 1} (A) в вершину f ^ {- 1} (B). У разі орієнтованого графа ця біекція також повинна зберігати орієнтацію ребра. У разі зваженого графа біекція також повинна зберігати вагу ребра.
1.4 Інші пов'язані визначення
Шляхом (або ланцюгом) у графі називають кінцеву послідовність вершин, в якій кожна вершина (крім останньої) з'єднана з наступною в послідовності вершин ребром.
Орієнтованим шляхом в орграфе називають кінцеву послідовність вершин v_i (i=1, ldots, k), для якої всі пари (v_i, v_ {i + 1}) (i=1, ... k - 1) є (орієнтованими) ребрами.
Циклом називають шлях, в якому перша і остання вершини збігаються. При цьому довжиною шляху (або циклу) називають число складових його ребер. Зауважимо, що якщо вершини u і v є кінцями деякого ребра, то згідно з цим визначенням, послідовність (u, v, u) є циклом. Щоб уникнути таких «вироджених» випадків, вводять такі поняття. Шлях (або цикл) називають простим, якщо ребра в ньому не повторюються; елементарним, якщо він простий і вершини в ньому не повторюються. Нескладно бачити, що:
· Всякий шлях, що з'єднує дві вершини, містить елементарний шлях, що з'єднує ті ж дві вершини.
· Всякий простий Неелементарні шлях містить елементарний цикл.
· Всякий простий цикл, що проходить через деяку вершину (або ребро), містить елементарний (під-) цикл, що проходить через ту ж вершину (або ребро).
· Петля - елементарний цикл.
Бінарне відношення на множині вершин графа, задане як «існує шлях з u в v», є відношенням еквівалентності і, отже, розбиває це безліч на класи еквівалентності, що називаються компонентами зв'язності графа. Якщо у графа рівно один компонент зв'язності, то граф зв'язний. На компоненті зв'язності можна ввести поняття відстані між вершинами як мінімальну довжину шляху, що з'єднує ці вершини.
Всякий максимальний зв'язний підграф графа G називається зв'язковий компонентою (або просто компонентою) графа G. Слово «максимальний» означає максимальний щодо включення, тобто не міститься в зв'язковому підграфі з великим числом елементів
Ребро графа називається мостом, якщо його видалення збільшує число компонент.
1.5 Додаткові характеристики графів
Граф називається:
· зв'язковим, якщо для будь-яких вершин u, v є шлях з u в v.
· сильно зв'язковим або орієнтовано зв'язковим, якщо він орієнтований, і з будь-якої вершини в будь-яку іншу мається орієнтований шлях.
· деревом, якщо він зв'язний і не містить простих циклів.
· повним, якщо будь-які його дві (різні, якщо не допускаються петлі) вершини з'єднані ребром.
· дводольним, якщо його вершини можна розбит...
