Оглавление [Скрыть]
Двусвязный граф
-
Определение двусвязного графа
- Двусвязный граф — это связный граф, который не разбивается на несвязанные части при удалении одной вершины.
- Двусвязный ориентированный граф имеет два направленных пути между любыми двумя вершинами, не имеющих общих вершин, кроме этих двух.
-
Примеры двусвязных графов
- Граф с четырьмя вершинами и четырьмя ребрами является двусвязным.
- Граф с пятью вершинами и шестью ребрами не является двусвязным, так как удаление вершины x приводит к разрыву связи.
-
Структура двусвязных графов
- Каждый двусвязный граф может быть построен индуктивно путем добавления путей к циклу.
-
Рекомендации и источники
- Эрик У. Вайсштейн, “Двусвязный граф” из MathWorld.
- Пол Э. Блэк, “двусвязный граф” в Словаре алгоритмов и структур данных.
- Национальный институт стандартов и технологий, 17 декабря 2004 года.