Головна

Вершин, ребер і компонент зв'язності.

Визначення. Вершини A і B графа G = (V, E,) називаються пов'язаними, якщо існує шлях з А в В.

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

Компонентою зв'язності графа G = (V, E) називається будь-який зв'язний непорожнє підмножина K ? V, таке що не існує ребер з початком a ? K і кінцем b  K.

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

одиницю).

теорема. Нехай в графі G = (V, E) є рівно n вершин, m ребер і k компонент зв'язності. Тоді m + k ? n.

Доведення. Індукція по m. Нехай m = 0. Тоді k = n, і m + k = k = n ? n. Припустимо, що теорема вірна, якщо кількість ребер дорівнює m - 1, m> 0 Доведемо теорему для m. Для цього видалимо з G якусь ребро e. Отримаємо граф G 'c m-1 ребром, n вершинами і k' компонентами зв'язності. При цьому k '- k ? 1. За припущенням індукції маємо (m - 1) + k' ? n. тоді

m + k ? m + (k '- 1) = (m - 1) + k' ? n.

 



 Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху.

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  Доведення формули Ейлера для плоских зв'язкових графів |  доведення коректності |  алгоритм |  Операції об'єднання і перетину регулярних мов |

© um.co.ua - учбові матеріали та реферати