Алгоритм Дейкстра, Детальна інформація

Якщо порядок елементів, що входять у ei, має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф.

Приклад: G=(V,E); V={1,2,3,4}; E=<(1,1), (1,2), (1,3), (2,4), (2,4)>

  G

Якщо e=(v,u), те вершини v і u називаються кінцями ребра. При цьому говорять, що ребро e є суміжним (інцидентним) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями.

Ступінь вершини графа - це число ребер, інцидентних даній вершині, причому петлі враховуються двічі. Оскільки кожне ребро інцидентне двом вершинам, сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер: Sum(deg(vi), i=1..|V|)=2\xF0D7|E|.

Граф, що не містить петель і кратних ребер, називається звичайним, чи простим графом (simple graph). У багатьох публікаціях використовується інша термінологія: під графом розуміється простий граф, граф із кратними ребрами називають мультиграфом, з петлями - псевдографом.

Деякі класи графів одержали особливі найменування. Граф з будь-якою кількістю вершин, не утримуючих ребер, називається порожнім. Звичайний граф з n вершинами, будь-яка пара вершин якого з'єднана ребром, називається повним і позначається Kn (очевидно, що в повному графі n(n-1)/2 ребер).



Граф, вершини якого можна розбити на непересічні підмножини V1 і V2 так, що ніякі дві вершини, що належать тому самому підмножині, не суміжні, називається двочастковим (чи біхроматичним, чи графом Кенига) і позначається Bmn (m=|V1|, n=|V2|, m+n=|V|). Повний двочастковий граф - такий двочастковий граф, що кожна вершина безлічі V1 зв'язана з усіма вершинами безлічі V2, і навпаки; позначення - Kmn. Зауваження: повний двочастковий граф Bmn не є повним (за винятком B11=K2).

B33

Підграфом, чи частиною графа G=(V,E) називається такий граф G'=(V',E'), що V'\xF0CDV і дві несуміжні вершини в G не суміжні в G'. Повним підграфом називається підграф, будь-яка пара вершин якого суміжна.

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

Ізоморфізм, гомеоморфізм

Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними (позначення: G1~G2), якщо між графами існує взаємо-однозначне відображення \xF06A: G1\xF0ABG2 (V1\xF0ABV2, E1\xF0ABE2), що зберігає відповідність між ребрами (дугами) графів, тобто для будь-якого ребра (дуги) e=(v,u) вірно: е'=\xF06A(v,u)=(\xF06A(v),\xF06A(u)) (e\xF0CEE1, е'\xF0CEE2). Відображення \xF06A називається ізоморфним відображенням.

Іншими словами, ізоморфні графи розрізняються тільки позначенням вершин.



Ізоморфні графи. Одне з ізоморфних відображень: (0,0), (1,3), (2,5), (3,6), (4,7), (5,2), (6,1), (7,4), (8,9), (9,8).

Характеристики графів, інваріантні відносно ізоморфизмов графів (тобто приймаючі однакові значення на ізоморфних графах), називаються інваріантами графів.

Підрозділом ребра (v1,v2) графи називається операція додавання в граф вершини v' і заміни цього ребра на два суміжних ребра (v1,v') і (v',v2): V'=V+{v'}, E'=E-{(v1,v2)}+{(v1,v')}+{(v',v2).

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

Дві графи називаються гомеоморфними, якщо для них існують ізоморфні підрозділи.

Шляхи і цикли

Шляхом у графі (чи маршрутом в орграфі) називається послідовність вершин, що чергується, і ребер (чи дуг - в орграфі) виду v0, (v0,v1), v1, ... , (vn-1,vn), vn. Число n називається довжиною шляху. Шлях без повторюваних ребер називається ланцюгом, без повторюваних вершин - простим ланцюгом. Шлях може бути замкнутим (v0=vn). Замкнутий шлях без повторюваних ребер називається циклом (чи контуром в орграфі); без повторюваних вершин (крім першої й останньої) - простим циклом.

Твердження 1. Якщо в графі існує шлях, що веде з вершини v0 у vn, то існує і простий ланцюг між цими вершинами.

Доказ: такий простий ланцюг можна побудувати, "викинувши" зі шляху всі цикли.

~

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

Для орграфів поняття св'язаність є більш складним: розрізняють сильну св'язаність, однобічну звязність і слабку зв’язність. Орграф називається сильно зв'язковим, якщо для будь-яких двох його вершин v і u існує як маршрут з v у u (v->u), так і з u у v (u->v). Орграф називається односторонньо зв'язковим, якщо для будь-яких двох його вершин u і v існує по крайньої один з маршрутів v->u чи u->v. Нарешті, орграф називається слабко зв'язковим, якщо зв'язний неорієнтований граф, одержуваний з цього орграфа шляхом зняття орієнтації з дуг. Очевидно, що будь-який сильно зв'язний граф є односторонньо зв'язковим, а односторонньо зв'язний - слабко зв'язковим, але не навпаки.

Дерева

Деревом називається довільний зв'язний граф без циклів.