12

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

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

Индукция по величине 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 не являющееся мостом. Тогда граф

U = (V ; E n feg) по индукционному предположению имеет (m 1) n + 2 граней.

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

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

Индукция по величине 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 не являющееся мостом. Тогда граф

U = (V ; E n feg) по индукционному предположению имеет (m 1) n + 2 граней. Но поскольку e содержалось в некотором цикле, количестово граней в U на единицу меньше чем в G.

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

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

Индукция по величине 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 не являющееся мостом. Тогда граф

U = (V ; E n feg) по индукционному предположению имеет (m 1) n + 2 граней. Но поскольку e содержалось в некотором цикле, количестово граней в U на единицу меньше чем в G.поэтому в G ровно

(m 1) n + 2 + 1 = m n + 2 граней.

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

. Доказательство. n = 5,

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

. Доказательство. n = 5,m = 5 4=2 = 10:

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

. Доказательство. n = 5,m = 5 4=2 = 10: Если бы граф был плоским, то он содержал бы f = m n + 2 = 7 ребер.

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

. Доказательство. n = 5,m = 5 4=2 = 10: Если бы граф был плоским, то он содержал бы f = m n + 2 = 7 ребер. Каждая грань ограничена как минимум из тремя ребрами

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

Граф K5

Определение. Полный граф Kn простой граф с n вершинами, у которого две различные вершины соединены ребром.

Следствие. Граф K5 не является плоским.

. Доказательство. n = 5,m = 5 4=2 = 10: Если бы граф был плоским, то он содержал бы f = m n + 2 = 7 ребер. Каждая грань ограничена как минимум из тремя ребрами, поэтому общее число ребер с повторениями не меньше

7 3 = 21.