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

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

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

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

Определение

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

Двусвязный ориентированный граф — это такой граф, что для любых двух вершин 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

Примеры

См. также

Ссылки

Внешние ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.