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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Приклади використання[ред.ред. код]

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

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

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

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

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

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

Деякі критерії зв'язності[ред.ред. код]

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

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

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

Див. також[ред.ред. код]