12

Нахождение остова наименьшего веса

Плоские графы

Определение. Граф называется плоским, если он представим в пространстве R2.

Теорема. Каждое дерево (а следовательно каждый лес) является плоским графом.

Определение. Гранью в плоском представлении называется часть пространства R2; отделенная дугами этого представления.

Теорема (формула Эйлера). Количество граней в плоском представлении связного графа с n вершинами и m ребрами равно m n + 2.

Нахождение остова наименьшего веса

Плоские графы

Определение. Граф называется плоским, если он представим в пространстве R2.

Теорема. Каждое дерево (а следовательно каждый лес) является плоским графом.

Определение. Гранью в плоском представлении называется часть пространства R2; отделенная дугами этого представления.

Теорема (формула Эйлера). Количество граней в плоском представлении связного графа с n вершинами и m ребрами равно m n + 2.

Следствие. Количество граней в плоском представлении графа с n вершинами , m ребрами и k компонентами связности равно m n + k + 1.

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1: База индукции:

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2:

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2: Индукционное предположение:

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2: Индукционное предположение: предположим формула Эйлера верна для всех плоских представлений с m n = t.

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2: Индукционное предположение: предположим формула Эйлера верна для всех плоских представлений с m n = t. Индукционное шаг:

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2: Индукционное предположение: предположим формула Эйлера верна для всех плоских представлений с m n = t. Индукционное шаг: пусть дано плоское представление

G = (V ; E) с n вершигами и m ребрами, причем m n = t + 1 0.

Нахождение остова наименьшего веса

Доказательство формулы Эйлера для плоских связных графов

Индукция по величине t = m n 1:

База индукции: если t = m n = 1, то граф является деревом и количество граней равно 1 1 + 2 = m n + 2: Индукционное предположение: предположим формула Эйлера верна для всех плоских представлений с m n = t. Индукционное шаг: пусть дано плоское представление

G = (V ; E) с n вершигами и m ребрами, причем

m n = t + 1 0. Тогда G не является деревом, и содержит ребро e 2 E не являющееся мостом.