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

Индукция по величине 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 ∈ E не являющееся мостом. Тогда граф U = (V, E \ {e}) по индукционному предположению имеет (m − 1) − n + 2 граней.

Но поскольку e содержалось в некотором цикле, количество граней в U на единицу

меньше чем в G. (m − 1) − n + 2 + 1 = m − n + 2 граней.

17 Ориентированные графы. Положительные и отрицательные степени вершин. Теорема о суммах положительных и отрицательны степеней. Изоморфизм ориентированных графов.

Определение. Ориентированный граф состоит из множества вершин V и множества ребер E, причем каждому ребру e ∈ E сопоставлена упорядоченная пара вершин (a, b) ∈ V^2.

В этом случае говорят, что вершина a ∈ V является началом, а b ∈ V — концом ребра e ∈ E.

Определение. Ребро, сопоставленное паре (a, a) называется петлей. Если несколько ребер имеют одинаковое начало и конец, то такие ребра называют кратными.

Определение. Неориентированный граф (V, E) называется простым, если среди элементов V нет петель и кратных ребер. Для случая простых графов мы будем отождествлять ребра e ∈ E с соответствующей парой вершин (a, b) ∈ V^2.

Определение. Путь из A ∈ V в B ∈ V во взвешенном графе G = (V, E) с весовой функцией w: E 7→ R+ называется минимальны м, если его длина не превосходит длины любого другого пути из A ∈ V в B ∈ V.

Определение. Расстоянием d(A, B) из A ∈ V в B ∈ V во взвешенном графе G = (V, E) называется длина

минимального пути из A в B. Если путей из A в B нет, то d(A, B) = ∞..

Степень захода вершины v орграфа D = (V, A) определяется следующим образом

d+D(v) = |{u ∈ V | (u, v) ∈ A}|.

Степень исхода вершины v орграфа D = (V, A) определяется следующим образом

d−D(v) = |{u ∈ V | (v, u) ∈ A}|.

Имеет место следующий аналог леммы о рукопожатиях.

Лемма 7. Если D = (V, A) ориентированный граф, то d+D(v) = |A| = d−D(v).

Орграфы G = (V, E) и G’ = (V’, A’) называются изоморфным и, если существует такая биекция

ϕ: V → V’, что (u, v) ∈ A ⇔ (ϕ(u), ϕ(v)) ∈ A’.

Отображение ϕ называется изоморфизмом.

Таким образом, как и в случае неориентированных графов, изоморфизм это биективное отображение множества вершин при котором смежным вершинами графа G соответствуют смежные вершины графа G’ и наоборот и, кроме того, сохраняются направления дуг.

18. Алгоритм Дейкстры нахождения кратчайшего пути.