4287560
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| Вершинная и рёберная связность | Вершинная связность Κ(G) - минимальное число вершин, которое надо удалить, чтобы граф перестал быть связным. Рёберная связность λ(G) - минимальное число рёбер, которое надо удалить, чтобы граф перестал быть связным. |
| Минимальный вершинное/рёберное разделяющее множество | Минимальное множество вершин/рёбер, которые надо удалить, чтобы граф распался. |
| Вершинно/рёберно k-связный граф | Граф, в котором можно удалить любые k-1 вершин/рёбер, и он останется связным. |
| Рёберный разрез в графе | Пусть S - множество вершин графа G, такое, что хотя бы одна вершина графа в это множество не входит. Тогда рёберный разрез [S, S(доп)] - множество всех рёбер, имеющих один конец на вершине множества S, а другой на вершине множества S(доп). |
| Свойства минимального рёберного разделяющего множества | Любой м. р. р. м. является рёберным разрезом графа. |
| Отношение рёберной связности λ(g), вершинной связности K(G) и минимальной степени вершины в графе δ(G) | K(G) <= λ(g) <= δ(G) |
| Отношение похожести рёбер в графе | Два ребра называются похожими, если они либо совпадают, либо находятся в одном простом цикле. Похожесть - отношение эквивалентности. |
| Необходимые и достаточные условия двусвязности графа | 1) Любые 2 ребра в графе похожи ИЛИ 2) Через любые 2 вершины графа проходит какой-то простой цикл |
| Классы эквивалентности отношения похожести | Отношение похожести разбивает граф на классы эквивалентности, являющиеся либо одиночными рёбрами, либо двусвязными подграфами |
| Граф блоков и точек сочленения B(G) | Это правильно раскрашенный граф, в котором вершины одного цвета представляют собой блоки исходного графа G (набор похожих рёбер и смежных к ним вершин), а вершины другого цвета - точки сочленения. |
| Алгоритм Хопкрафта-Тарьяна | Алгоритм поиска точек сочленения в графе. 1) Построить остовное дерево графа поиском в глубину из любой точки; 2) Если точка x - корень, то она является точкой сочленения, если у неё есть хотя бы два ребра, принадлежащих дереву; 3) Если точка x - не корень, то она является точкой сочленения, если у неё есть хотя бы один потомок в дереве, у которого нет не принадлежащих дереву рёбер, соединяющих вершину этого потомка с предком x |
| Декомпозиция двусвязного графа | Любой двусвязный граф может быть представлен как некоторый простой цикл и набор присоединённых к нему ручек. |
| Точка сочленения и мост | Точка сочленения - вершина, при удалении которой граф теряет связность. Мост - ребро, при удалении которого граф теряет связность. Если в графе есть мост, то есть и точка сочленения; обратное неверно. |
| Рёберно-двусвязный граф. Определение и декомпозиция | Рёберно-двусвязный граф - граф без мостов. Допускает декомпозицию на некоторый простой цикл и набор присоединённых "замкнутых ручек". |
Want to create your own Flashcards for free with GoConqr? Learn more.