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

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

Кількість зв'язних графів з розміткою вершин наведено в Енциклопедії послідовностей цілих чисел як послідовність A001187:

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

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

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

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

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

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

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

• Теорема Менгера
• Перевірка зв'язності графів