В теории графов , Двусвязный граф является связным и «неотделимым» графом , а это означает , что если одна вершины должны были быть удалена, график будет оставаться на связь. Следовательно, двусвязный граф не имеет сочлененных вершин .
Свойство быть 2-связным эквивалентно двусвязности, за исключением того, что полный граф из двух вершин обычно не считается 2-связным.
Это свойство особенно полезно при поддержании графа с двукратной избыточностью , чтобы предотвратить отключение при удалении единственного ребра (или соединения).
Использование двусвязных графов очень важно в области сетей (см. Сетевой поток ) из-за этого свойства избыточности.
Определение
Двухсвязные неориентированный граф является связным графом , который не разбивается на отключенных куски, удалив любую одну вершину (и ее падающие ребра).
Двухсвязные ориентированный граф является одним из таких , что для любых двух вершин V и W есть два направленных пути от V до W , которые не имеют общих вершин , отличных от V и W .
Вершины | Количество возможностей |
---|---|
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 |
Примеры
Двусвязный граф с четырьмя вершинами и четырьмя ребрами
Граф, который не двусвязен. Удаление вершины x отключит граф.
Двусвязный граф с пятью вершинами и шестью ребрами
Граф, который не двусвязен. Удаление вершины x отключит граф.
Смотрите также
Рекомендации
- Эрик В. Вайсштейн. «Двусвязный граф». Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/BiconnectedGraph.html
- Пол Э. Блэк, «двусвязный граф», в Словаре алгоритмов и структур данных [онлайн], Пол Э. Блэк, изд., Национальный институт стандартов и технологий США. 17 декабря 2004 г. (доступ СЕГОДНЯ) Доступно по адресу : https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
Внешние ссылки
- Дерево реализации двусвязных компонентов Java в библиотеке jBPT (см. Класс BCTree).