Лекция: Алгоритм Краскала

Пусть дан полный граф. Ребрам приписаны штрафы. На основе этого графа строят дерево, имеющее минимальный суммарный штраф.

Для этого на каждом шаге выбирают ребро, имеющее минимальный штраф и не образующее цикл с уже выбранными ребрами.

.

Пример.

2 3 5 5

6

4 4 8 6

6

Жирными линиями выделено минимальное дерево

Теорема Кэлидля раскрашенных деревьев.

Для n вершин существует nn-2 различных помеченных деревьев.

Например, существует 16 различных деревьев с четырьмя вершинами.

1 2 3 4

4 3 2 1

4 вершины Þ 44 — 2 = 16 различных помеченных деревьев

1 2 3

Планарные графы

Граф — плоский, если он изображен на плоскости без пересечения ребер.

Граф — планарный, если он может быть изображен на плоскости без пересечения ребер.

Любой плоский граф может быть преобразован в граф с прямыми ребрами.

Þ Þ

неплоский, но плоский плоский с

планарный прямыми ребрами

Граф, где все вершины соприкасаются с внешней гранью — внешнепланарный.

Два «замечательных» непланарных графа:

К5 К3,3

Приведем без доказательства две теоремы:

Любой граф, содержащий в качестве подграфа К5 или К3,3 — непланарен.

Два графа гомеоморфны если они тождественны с точностью до вершин со степенью r=2.

Любой граф, содержащий в качестве подграфа граф гомеоморфный К5 или К3,3 или — непланарен.

Теорема (Эйлера для планарных графов):

В любом планарном графе

В + Г = Р + 2.

где: В — число вершин

Г — число граней

Р — число ребер

Доказательство:

1 + 1 = 0 + 2

2 + 1 = 1 + 2

3 + 2 = 3 + 2

4 + 2 = 4 + 2

Пусть есть граф с n вершинами, для которого это соотношение верно.

Добавление ребра приводит к увеличению на едитницу либо числа граней, либо вершин.