Связность (теория графов)
-
Определение связности в теории графов
- Связность — это свойство графа, при котором все вершины связаны друг с другом.
- Связность вершин и ребер определяется как количество вершин и ребер, которые необходимо удалить, чтобы граф стал несвязным.
-
Примеры связности
- Полный граф с n вершинами имеет связность вершин и ребер, равную n — 1.
- Дерево имеет связность ребер, равную 1, между любыми двумя вершинами.
-
Свойства связности
- Связность вершин меньше или равна связности ребер.
- Для вершинно-транзитивных графов степени d связность вершин и ребер равна d.
- Связность сохраняется при гомоморфизмах графов.
-
Вычислительные аспекты связности
- Задача определения связности между двумя вершинами может быть решена с помощью алгоритмов поиска.
- Теорема Менгера позволяет эффективно вычислять связность и реберную связность графа.
-
Ограничения на связность
- Для графа с минимальной степенью d связность ребер меньше или равна d.
- Для многогранных графов и плоских графов с 3 вершинами связность равна количеству вершин.
-
Другие свойства связности
- Графы с k-связностью имеют циклы, проходящие через все вершины в наборе из k вершин.
- Теорема Дж. A. Дирака утверждает, что для каждого набора из k вершин существует цикл, проходящий через все вершины в наборе.
Полный текст статьи: