WikiSort.ru - Не сортированное

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

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

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

Определение

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

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

Примеры

См. также

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

Ссылки

• Eric W. Weisstein. "Biconnected Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html
• 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. http://www.nist.gov/dads/HTML/biconnectedGraph.html

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

• The tree of the biconnected components Java implementation in the jBPT library (see BCTree class).

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.