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