Зв’язок у неорієнтованих графах
Визначення.Неорієнтований граф G зв'язаний, якщо існує хоча б один маршрут G між кожною парою вершин i і j.
Визначення.Підграфом графаG(V,E) називається граф, всі вершини якого належатьV(G), а всі ребра належатьE(G).
Визначення.Максимальний зв'язковий підграф графа G називається зв'язковим компонентом графа G.Зауваження:Максимальний не в сенсі кількості ребер, а в сенсі нерозширюваності.
Наприклад, малюнку 19 зображено незв'язний граф з трьома компонентами зв'язності.
Зауважимо, що кожна компонента зв'язності неорієнтованого графа є неорієнтованим графом, а значить, для неї виконується лема про рукостискання.
Зв'язність орієнтованих графів
Визначення.Орієнтований граф G зв'язаний, якщо неорієнтований граф, що виходить з G шляхом видалення орієнтації ребер, є зв'язковим.
Визначення.Орієнтований графсильно зв'язаний, якщо для кожної пари вершиніїіснує принаймні один шлях зiвjі принаймні один шлях зiвi.
Визначення.Максимальний зв'язний підграф орграфа називаєтьсясильно зв'язною компонентою.
На малюнках 20 - 222 зображені незв'язний, зв'язковий, але не сильно і сильнозв'язний графи відповідно.
Ейлерів цикл
Визначення.Ейлерів цикл- цикл, який проходить рівно один раз по кожному ребру (дузі) графа.
Визначення.Якщо граф має цикл, що містить усі ребра (дуги) графа по одному разу, то граф називається ейлеровим.
Не всі графи мають ейлерові цикли, але якщо ейлерів цикл існує, це означає, що, слідуючи вздовж цього циклу, можна намалювати граф на папері, не відриваючи від неї олівця.
Граф, зображений малюнку23 є ейлеровим. Завдання про Кенегсберзьких мостах, розглянуте вище, передбачає знаходження ейлерового циклу в мультиграфі.
Теорема.Зв'язковий неорієнтований граф G містить ейлерів цикл тоді і лише тоді, коли всі вершини в ньому мають парний ступінь.
Доведемо пряму теорему.
Нехай граф G містить ейлерів цикл, значить, існує цикл, що проходить по всіх ребрах графа рівно по одному разу. Ітимемо за циклом, і рахуватимемо ступеня вершин. Т.к. проходячи через вершину щоразу, додаємо до її ступеня 2, то ступеня всіх вершин парні.
Доведемо зворотну теорему (спосіб підтвердження – конструктивний, тобто дає алгоритм побудови ейлерового циклу).
Нехай усі вершини графа мають парний ступінь. Будуватимемо ейлерів цикл, починаючи з деякої вершиниv0, при цьому пройдені ребра будемо видаляти. Так як всі вершини мають парний ступінь, то, потрапивши в якусь вершину, обов'язково знайдемо ребро, яким можна з неї вийти. Таким чином, обов'язково повернемося у вершинуv0, отримавши при цьому деякий цикл Р. Якщо при цьому всі ребра графа беруть участь у циклі, теорема доведена.
В іншому випадку, оскільки граф зв'язаний, обов'язково знайдеться ребро, що не входить до циклу, але інцидентне будь-якій вершині циклу. Позначимо цю вершинуv1. Будуватимемо цикл починаючи з вершиниv1. З аналогічних міркувань ми обов'язково повернемося у вершинуv1, отримавши цикл Р1. Якщо при цьому всі ребра графа присутні в циклах Р і Р1, то циклv1Рv1Р1v1містить всі ребра графа по одному разу, тобто є ейлеровим, отже теорема доведена. В іншому випадку продовжуємо аналогічні міркування. Так як ребер у графі кінцева кількість побудовациклу обов'язково закінчиться.
Теорема.Зв'язковий орграф є ейлеровим тоді і тільки тоді, коли півступінь результату кожної вершини дорівнює півступеню її заходу.
Доказаналогічно випадку неорієнтованого графа.