Теми рефератів
> Реферати > Дипломні проекти > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті > Контакти
Реклама
Реферати, твори, дипломи, практика » Курсовые проекты » Ейлерови графи

Реферат Ейлерови графи

>)-маршрутом. Маршрут замкнутий, якщо v 0 = v n , і відкритий в іншому випадку. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі вершини (а отже, і ребра) різні. Замкнута ланцюг називається циклом. Замкнуте маршрут називається простим циклом, якщо всі його n вершин різні і n Ві 3.

Граф G називається зв'язковим, якщо будь-яка пара його вершин з'єднана простий ланцюгом. [6]

Задача про кенігсберзькими мостах.

Отцем теорії графів є Ейлер (1707-1782), який вирішив в 1736г. широко відому в той час завдання, яка звалася проблемою Кенигсбергских мостів. У місті Кенігсберзі (нині Калінінград) було два острови, з'єднаних сім'ю мостами з берегами річки Преголя і один з одним так, як показано на малюнку 5. Завдання полягало в наступному: знайти маршрут проходження всіх чотирьох частин суші, який починався б з будь-якої з них, кінчався б на цій же частині і рівно один раз проходив по кожному мосту.


В 

В В 









Рис.5.

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

Для доказу того, що завдання не має рішення, Ейлер позначив кожну частину суші точкою (вершиною), а кожен міст - лінією (ребром), що з'єднує відповідні точки. Вийшов "Граф". Цей граф зображений на малюнку 6, де точки відзначені тими ж буквами, що і чотири частини суші на малюнку 5. <В 





Рис.6. p> Твердження про не існування "Позитивного" рішення у цієї задачі еквівалентно твердженням про неможливість обійти спеціальним чином граф, представлений на малюнку 6.

Вирушаючи від цього приватного випадку Ейлер узагальнив постановку завдання і знайшов критерій існування обходу у даного графа, а саме граф повинен бути зв'язковим і кожна його вершина має бути інцидентна парним числом ребер. [6]

Ейлерови графи

Рішення Ейлером задачі про Кенигсбергских мостах призвела до першої опублікованій роботі з теорії графів. Задачу про обхід мостів можна узагальнити і отримати таку завдання теорії графів: чи можна знайти в даному графі G цикл, що містить всі вершини і всі ребра? Граф, у якому це можливо, називається ейлеровим. Таким чином, Ейлером граф має Ейлером цикл - замкнутий ланцюг, що містить всі вершини і всі ребра. Ясно, що Ейлером граф повинен бути зв'язковим. [6]

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

В 

Теорема 1 (критерій):

Граф з більш ніж однією вершиною має Ейлером цикл тоді і тільки тоді, коли він зв'язний і кожна його вершина має парну ступінь.

Доказ: Припустимо, ...


Предыдущая страница | Страница 3 из 10 | Следующая страница
Реклама
//