петлі вважають двічі). Вершина називається ізольованою, якщо вона не є кінцем ні для одного ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.
Орієнтований граф.
Орієнтований граф (скорочено орграф) - це впорядкована пара, для якої виконані наступні умови:
- це непорожнє безліч вершин або вузлів,
це безліч (впорядкованих) пар різних вершин, званих дугами або орієнтованими ребрами.
Малюнок 1.1 - Орієнтований граф
Дуга - це впорядкована пара вершин, де вершину називають початком, а - кінцем дуги. Можна сказати, що дуга веде від вершини до вершини.
Змішаний граф
Змішаний граф - це граф, в якому деякі ребра можуть бути орієнтованими, а деякі - неорієнтованими. Записується впорядкованої трійкою, де, і визначені так само, як вище.
Орієнтований і неорієнтований графи є окремими випадками змішаного.
Ізоморфні графи
Граф називається ізоморфним графу, якщо існує біекція з безлічі вершин графа в безліч вершин графа, що володіє наступною властивістю: якщо в графі є ребро з вершини у вершину, то в графі повинно бути ребро з вершини у вершину і навпаки - якщо в графі є ребро з вершини у вершину, то в графі повинно бути ребро з вершини у вершину. У разі орієнтованого графа ця біекція також повинна зберігати орієнтацію ребра. У разі зваженого графа біекція також повинна зберігати вагу ребра.
Інші пов'язані визначення
Шляхом (або ланцюгом) у графі називають кінцеву послідовність вершин, в якій кожна вершина (крім останньої) з'єднана з наступною в послідовності вершин ребром.
Орієнтованим шляхом в орграфе називають кінцеву послідовність вершин, для якої всі пари є (орієнтованими) ребрами.
Циклом називають шлях, в якому перша і остання вершини збігаються. При цьому довжиною шляху (або циклу) називають число складових його ребер. Зауважимо, що якщо вершини і є кінцями деякого ребра, то згідно з цим визначенням, послідовність є циклом. Щоб уникнути таких «вироджених» випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра в ньому не повторюються; елементарним, якщо він простий і вершини в ньому не повторюються. Нескладно бачити, що:
· всякий шлях, що з'єднує дві вершини, містить елементарний шлях, що з'єднує ті ж дві вершини.
· всякий простий Неелементарні шлях містить елементарний цикл.
· всякий простий цикл, що проходить через деяку вершину (або ребро), містить елементарний (під-) цикл, що проходить через ту ж вершину (або ребро).
· петля - елементарний цикл.
Бінарне відношення на множині вершин графа, задане як «існує шлях з в», є відношенням еквівалентності і, отже, розбиває це безліч на класи еквівалентності, що називаються компонентами зв'язності графа. Якщо у графа рівно одна компонента зв'язності, то граф зв'язний. На компоненті зв'язності можна ввести поняття відстані між вершинами як мінімальну довжину шляху, що з'єднує ці вершини.
Всякий максимальний зв'язний підграф графа G називається зв'язковий компонентою (або просто компонентою) графа. Слово «максимальний» означає максимальний щодо включення, тобто не міститься в зв'язковому підграфі з великим числом елементів
Ребро графа називається мостом, якщо його вид...
