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