logo
Вопросы на зачет

ОстОвное дерево. Алгоритм Крускала.

Остовное дерево – это дерево, содержащее все вершины исходного графа и только те ребра, которые необходимы для сохранения связности.

Минимальное остовное дерево – это остовное дерево неориентированного взвешенного графа, сумма весов оставшихся ребер в котором минимальна.

В любом связном графе на n вершинах имеется остовное дерево.

Алгоритм – На каждом шаге выбирается ребро наименьшего веса среди множества ребер, которые не образуют цикл. (находить дуги минимального веса, а затем проверять не будет ли включение данной дуги провоцировать включение цикла)

Длина минимального остовного дерева

Алгоритм поиска минимального остовного дерева

  1. Плоский граф. Лемма Жордана. Задача «три дома – три колодца».

Теорема Жордана:

Если есть замкнутая линия l, не имеющая самопересечений, то для любой точки P, находящейся внутри области, и точки Q, находящейся вне области, невозможно провести соединяющую их линию, чтобы она не пересекала l.

  1. Сжатие/разжатие графа. Теорема Куратовского.

Разжатие графа – добавление фиктивных узлов в разрыв ребра.

Сжатие графа – удаление узлов, если они связаны только с двумя соседями.

Теорема Куратовского:

Если полное сжатие графа не содержит графа типа «Три дома, три колодца» или графа типа «Пентаграмма», то граф является планарным (Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер.).

  1. Способы хранения структуры графа в ЭВМ.

Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер.

  1. Компоненты связности. Алгоритм нахождения КС.

Поиск в ширину (англ. breadth-first search, BFS) – один из алгоритмов обхода графа. Метод лежит в основе некоторых других алгоритмов близкой тематики. Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень – произвольно выбранный узел, затем – все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня.

Алгоритм не обходит все рёбра, он посещает все вершины

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].