Зв'язний граф
Ця стаття не містить посилань на джерела. (липень 2013) |
Зв'язний граф — граф, що містить рівно одну компоненту зв'язності. Це значить, що між будь-якою парою вершин цього графа існує шлях.
Приклади використанняРедагувати
Прямим використанням теорії графів є теорія мереж — та її застосування — теорія електронних мереж. Наприклад, всі комп'ютери, що знаходяться в мережі інтернет, утворюють зв'язний граф, і хоча окрема пара комп'ютерів може бути не з'єднана безпосередньо (в формулюванні для графів — не бути поєднаною ребром), від кожного комп'ютера можна передати інформацію до будь-якого іншого (існує шлях з будь-якої вершини графа до будь-якої іншої).
Зв'язність для орієнтованих графівРедагувати
В орієнтованих графах розрізняють декілька понять зв'язності.
Орієнтований граф називається сильно-зв'язним, якщо в ньому існує (орієнтований) шлях з будь-якої вершини до будь-якої іншої, або, що тотожно, граф містить рівно одну компоненту сильної зв'язності.
Орієнтований граф називається односторонньо-зв'язним, якщо для будь-яких двох його вершин u і v існує хоча б один з маршрутів від v до u чи від u до v.
Орієнтований граф називається слабко-зв'язним, якщо є зв'язним неорієнтований граф, отриманий з нього заміною орієнтованих ребер на неорієнтовані.
Деякі критерії зв'язностіРедагувати
Тут наведені деякі критеріальні (тотожні) визначення зв'язного графа:
Граф називається однозв'язним (зв'язним), якщо:
- У нього одна компонента зв'язності
- Між будь-якою парою вершин існує шлях, що поєднує їх
- Існує шлях їз заданої вершини в будь-яку іншу
- Граф містить зв'язний підграф, що містить всі вершини початкового графа
- Містить як підграф дерево, що містить всі вершини початкового графа (таке дерево називається кістяковим)
- За довільним поділом його вершин на дві групи завжди існує хоча б одне ребро, що поєднує пару вершин з різних груп