На головну

теорема Ейлера

  1.  Друга теорема подвійності
  2.  Друга теорема Шеннона
  3.  Діаграми Ейлера - Венна
  4.  Диференціальні рівняння руху Ейлера
  5.  Диференціальні рівняння рівноваги Ейлера
  6.  Закон Кулона. Електростатичний теорема Гаусса
  7.  Закон Кулона. Електростатичний теорема Гаусса

ланцюг називається ейлеровой, Якщо вона є простою і проходить по всіх ребрах графа.

ейлеровим циклом називається простий цикл, що проходить по всіх ребрах.

Граф, що має ейлерову цикл, називається ейлеровим графом.

теорема: Для того щоб зв'язний граф був ейлеровим необхідно і достатньо, щоб мірі всіх вершин його були парними.

Доведення: 1) Доведемо необхідність.

Нехай є вершина з непарної ступенем. Ця вершина не може бути першою


так як виходити і повертатися в неї можна, використовуючи парне число ребер. Непарне ребро зумовить остаточний відхід з цієї вершини. Але ця вершина повинна бути і останньою, щоб забезпечити цикл. Що неможливо.

Вершина з непарної ступенем не може бути і проміжної, бо в кінцевому підсумку в цій вершині закінчиться ланцюг. Крім ребра, по якому один раз в цю вершину зайшли, залишиться парне число ребер, за якими будемо йти з вершини і обов'язково в неї повертатися.


Таким чином доведено необхідність того, щоб всі вершини були парними.

2) Доведемо достатність вимоги парності вершин.

Візьмемо будь-який граф, що містить тільки вершини парного степеня.

Будуємо з будь-якої вершини простий цикл. Якщо пройдені всі ребра, то теорема доведена інакше

Будуємо для будь-якої вершини в контурі простий цикл з вільних ребер і вставляємо новий цикл в попередній. (Тобто при обході перериваємо у відповідній вершині перший цикл і проходимо другий, закінчивши його в вершині, з якої вийшли. І закінчуємо перший цикл).


Якщо таким чином пройдені всі ребра графа, то теорема доведена. Інакше вибирається нова вершина, инцидентная непройденого ребрах (їх парне число) і будується новий цикл. І так до вичерпання непройденого ребер графа.

Таким чином, теорема доведена. А, отже, вирішена і завдання про Кенигсбергских мостах. Слово «вирішена» тут використовується в расшірненном розумінні, прийнятому в побуті у математиків, оскільки Ейлер на самій-то справі довів, що завдання не має рішення.

слідство. Для того, щоб в графі існувала Ейлерова ланцюг необхідно, щоб в ньому було рівно дві вершини з непарної ступенем, причому цей ланцюг починається в одній з цих вершин і закінчується в інший.

Відома дитяча завдання намалювати, не відриваючи олівця, будиночок - найкраща ілюстрація до цього слідству.


Елементарний цикл, що проходить через всі вершини, називається гамільтоновим циклом, А відповідний граф - гамільтоновим графом.

Приклад гамільнтонова графа


Однак, для гамільтонових графів не вдалося довести красивою теореми, на зразок теореми Ейлера.




 Аксіоматичні теорії першого порядку |  система Генцен |  система Аристотеля |  Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |

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