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

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

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

Определение

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

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

Примеры

См. также

• Шарнир (теория графов)

Ссылки

• Eric W. Weisstein. "Biconnected Graph." From MathWorld--A Wolfram Web Resource.
• Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.

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

• in the jBPT library (see BCTree class).