Алгоритм Краскала

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

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

.

Пример.

2 3 5 5

6

4 4 8 6

6

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

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

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

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

1 2 3 4

4 3 2 1

4 вершины Þ 4^{4 - 2} = 16 различных помеченных деревьев

1 2 3

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

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

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

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

Þ Þ

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

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

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

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

К₅ К_3,3

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

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

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

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

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

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

В + Г = Р + 2.

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

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

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

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

1 + 1 = 0 + 2

2 + 1 = 1 + 2

3 + 2 = 3 + 2

4 + 2 = 4 + 2

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

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