Зв'язний граф

Цей граф перестане бути зв'язним, якщо вилучити ребро позначене пунктирною лінією.

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

Приклади використання

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

Кількість зв'язних графів

Кількість і зображення зв'язаних графів з 4 вершинами

Кількість зв'язних графів з розміткою вершин наведено в Енциклопедії послідовностей цілих чисел як послідовність A001187 [Архівовано 20 січня 2022 у Wayback Machine.]:

n Кількість
1 1
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

Зв'язність для орієнтованих графів

В орієнтованих графах розрізняють декілька понять зв'язності.

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

Орієнтований граф називається односторонньо-зв'язним, якщо для будь-яких двох його вершин u і v існує хоча б один з маршрутів від v до u чи від u до v.

Орієнтований граф називається слабко-зв'язним, якщо є зв'язним неорієнтований граф, отриманий з нього заміною орієнтованих ребер на неорієнтовані.

Деякі критерії зв'язності

Тут наведені деякі критеріальні (тотожні) визначення зв'язного графа:

Граф називається однозв'язним (зв'язним), якщо:

  1. У нього одна компонента зв'язності
  2. Між будь-якою парою вершин існує шлях, що поєднує їх
  3. Існує шлях із заданої вершини в будь-яку іншу
  4. Граф містить зв'язний підграф, що містить всі вершини початкового графа
  5. Містить як підграф дерево, що містить всі вершини початкового графа (таке дерево називається кістяковим)
  6. За довільним поділом його вершин на дві групи завжди існує хоча б одне ребро, що поєднує пару вершин з різних груп

Див. також