Двусвязный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров.

Это свойство особенно полезно при рассмотрении графов с двойным резервированием, чтобы избежать разрыва при удалении единственного ребра.

Использование двусвязных графов очень важно в области сетей (смотри транспортные сети) ввиду их свойств резервирования.

Определение

[править | править код]

Двусвязный неориентированный граф — это связный граф, не распадающийся на части при удалении любой вершины (и всех инцидентных ей рёбер).

Двусвязный ориентированный граф — это такой граф, что для любых двух вершин v и w имеется два ориентированных пути из v в w, не имеющих общих вершин кроме v и w.

Неделимые (или 2-связные) графы (или блоки) с n вершинами (последовательность A002218 в OEIS)
Число вершин Число вариантов
1 0
2 1
3 1
4 3
5 10
6 56
7 468
8 7123
9 194066
10 9743542
11 900969091
12 153620333545
13 48432939150704
14 28361824488394169
15 30995890806033380784
16 63501635429109597504951
17 244852079292073376010411280
18 1783160594069429925952824734641
19 24603887051350945867492816663958981

Внешние ссылки

[править | править код]