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

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

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

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

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

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

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

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

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

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

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

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

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

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

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