Fichas
3. Связность в графах
Fichas del conjunto (14)
- 1Вершинная и рёберная связностьВершинная связность Κ(G) - минимальное число вершин, которое надо удалить, чтобы граф перестал быть связным.
Рёберная связность λ(G) - минимальное число рёбер, которое надо удалить, чтобы граф перестал быть связным. - 2Минимальный вершинное/рёберное разделяющее множествоМинимальное множество вершин/рёбер, которые надо удалить, чтобы граф распался.
- 3Вершинно/рёберно k-связный графГраф, в котором можно удалить любые k-1 вершин/рёбер, и он останется связным.
- 4Рёберный разрез в графеПусть S - множество вершин графа G, такое, что хотя бы одна вершина графа в это множество не входит. Тогда рёберный разрез [S, S(доп)] - множество всех рёбер, имеющих один конец на вершине множества S, а другой на вершине множества S(доп).
- 5Свойства минимального рёберного разделяющего множестваЛюбой м. р. р. м. является рёберным разрезом графа.
- 6Отношение рёберной связности λ(g), вершинной связности K(G) и минимальной степени вершины в графе δ(G)K(G) <= λ(g) <= δ(G)
- 7Отношение похожести рёбер в графеДва ребра называются похожими, если они либо совпадают, либо находятся в одном простом цикле. Похожесть - отношение эквивалентности.
- 8Необходимые и достаточные условия двусвязности графа1) Любые 2 ребра в графе похожи
ИЛИ
2) Через любые 2 вершины графа проходит какой-то простой цикл - 9Классы эквивалентности отношения похожестиОтношение похожести разбивает граф на классы эквивалентности, являющиеся либо одиночными рёбрами, либо двусвязными подграфами
- 10Граф блоков и точек сочленения B(G)Это правильно раскрашенный граф, в котором вершины одного цвета представляют собой блоки исходного графа G (набор похожих рёбер и смежных к ним вершин), а вершины другого цвета - точки сочленения.
- 11Алгоритм Хопкрафта-ТарьянаАлгоритм поиска точек сочленения в графе.
1) Построить остовное дерево графа поиском в глубину из любой точки;
2) Если точка x - корень, то она является точкой сочленения, если у неё есть хотя бы два ребра, принадлежащих дереву;
3) Если точка x - не корень, то она является точкой сочленения, если у неё есть хотя бы один потомок в дереве, у которого нет не принадлежащих дереву рёбер, соединяющих вершину этого потомка с предком x - 12Декомпозиция двусвязного графаЛюбой двусвязный граф может быть представлен как некоторый простой цикл и набор присоединённых к нему ручек.
- 13Точка сочленения и мостТочка сочленения - вершина, при удалении которой граф теряет связность.
Мост - ребро, при удалении которого граф теряет связность.
Если в графе есть мост, то есть и точка сочленения; обратное неверно. - 14Рёберно-двусвязный граф. Определение и декомпозицияРёберно-двусвязный граф - граф без мостов.
Допускает декомпозицию на некоторый простой цикл и набор присоединённых "замкнутых ручек".
Información
- Descripción
- Карточки по третьей лекции курса "Основы теории графов" на stepic.org
- Creado por
- Sergei Fomin
- Visitas
- 72
- Etiquetas
- Valoración