ОстОвное дерево. Алгоритм Крускала.
Остовное дерево – это дерево, содержащее все вершины исходного графа и только те ребра, которые необходимы для сохранения связности.
Минимальное остовное дерево – это остовное дерево неориентированного взвешенного графа, сумма весов оставшихся ребер в котором минимальна.
В любом связном графе на n вершинах имеется остовное дерево.
Алгоритм – На каждом шаге выбирается ребро наименьшего веса среди множества ребер, которые не образуют цикл. (находить дуги минимального веса, а затем проверять не будет ли включение данной дуги провоцировать включение цикла)
Длина минимального остовного дерева
Алгоритм поиска минимального остовного дерева
Плоский граф. Лемма Жордана. Задача «три дома – три колодца».
Теорема Жордана:
Если есть замкнутая линия l, не имеющая самопересечений, то для любой точки P, находящейся внутри области, и точки Q, находящейся вне области, невозможно провести соединяющую их линию, чтобы она не пересекала l.
Сжатие/разжатие графа. Теорема Куратовского.
Разжатие графа – добавление фиктивных узлов в разрыв ребра.
Сжатие графа – удаление узлов, если они связаны только с двумя соседями.
Теорема Куратовского:
Если полное сжатие графа не содержит графа типа «Три дома, три колодца» или графа типа «Пентаграмма», то граф является планарным (Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер.).
Способы хранения структуры графа в ЭВМ.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер.
Компоненты связности. Алгоритм нахождения КС.
Поиск в ширину (англ. breadth-first search, BFS) – один из алгоритмов обхода графа. Метод лежит в основе некоторых других алгоритмов близкой тематики. Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень – произвольно выбранный узел, затем – все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм не обходит все рёбра, он посещает все вершины
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].
- Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.
- Изоморфизм графов. Примеры.
- Пути, цепи, циклы.
- Связность графов.
- Эйлеров цикл. Определение, условие существования, алгоритм нахождения.
- Гамильтонов цикл. Определение. Задача о коммивояжере.
- Деревья.
- ОстОвное дерево. Алгоритм Крускала.
- Алгоритм поиска кратчайшего пути в графе.
- Клики. Алгоритм поиска клик.
- Раскраска графов. Алгоритмы раскраски.
- Генерация случайных графов.