Головна

Доведення формули Ейлера для плоских зв'язкових графів

Індукція за величиною 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. Алгоритм Дейкстри знаходження найкоротшого шляху.



 Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  доведення коректності

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Вершин, ребер і компонент зв'язності. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху. |  алгоритм |  Операції об'єднання і перетину регулярних мов |

© um.co.ua - учбові матеріали та реферати