/>
Знайдемо максимально відстань від кожної з вершин графа як:
; ; ; ; ; ; ; ;.
Отже, согласно з визначенням 6.36, центром графа є вершина 4; Периферійні вершини - 1, 6, 7, 8, 9. Радіус графа, а діаметр графа.
5.5 Ейлерів цикл. Ейлерів граф
Теорія графів вагітн свой качан з решение Видатний математиком Ейлера у 1736 р. задачі про кенігсбергські мости. Вона вінікла в Пруський містечку Кенігсберг на річці Прегал. Жители Кенігсберга полюбляли гуляти по доріжках, Які включаються сім мостів через Річку. Людей цікавіло питання, чи могут смороду, Почаїв шлях з однієї ділянки суші, обійті всі мости по черзі за одну ходу, и вернуться в качан шляху, що не перепліваючі Річку. План Розташування семи мостів у Кенігсберзі наведень на рис. 5.13.
Малюнок 5.13 - План Розташування семи мостів у Кенігсберзі
Ейлер замінів план міста графом (рис. 5.14), у якому ділянки суші зобразив як вершини, а мости, їх з'єднуючі - як ребра.
Малюнок 5.14 - Заміна плану міста графом
Для того, щоб відповістіті на поставлене запитання, дамо ряд визначеня.
Визначення. Ейлеровім циклом назівається цикл, что містіть всі ребра графа.
Ейлерів цикл можна вважаті як слід олівця, что вічерчує граф, який не відріваючісь від паперу.
Відшукання ейлеровіх ціклів пов'язане з рядом прикладних завдань. Например, при Перевірці дорожньої мережі та патенти по Кожній дорозі досліджуваної мережі проїхаті только один раз и вернуться у вихідний пункт. Очевидно, что Такі цикли існують не так на будь-якому графі.
Визначення. Ейлеровім графом назівається граф, что містіть Ейлера цикл.
Теорема Ейлера. Кінцевій неорієнтованій граф Ейлера тоді и только тоді, коли ВІН зв'язного, и степінь всех его вершин парна (при підрахунку степеня вершини, будь-яку інцідентну Їй петлю вважаті двічі).
Доведення:
необходимость. Если граф містіть Ейлера цикл, то будь-які две его вершини належати Цьом циклу; граф зв'язного. Если при обході циклу Деяка вершина зустрічається разів, то ми разів входимость и віходімо з неї (щораз по різніх ребрах). Отже, степінь вершини дорівнює.
Достатність. Нехай граф зв'язного и степінь будь-якої его вершини парна (рис. 5.15). Нехай - Деяка вершина графа, - суміжна Їй вершина. Цій вершіні інцідентно хоча б Одне ребро, відмінне від, вершіні - ребро, відмінне від, и т.д.
Малюнок 5.15 - Ейлерів граф
Побудуємо Із ціх ребер ланцюг, відзначаючі їх и не повторюючі Вже пройдені.
Граф кінцевій, то цею ланцюг винен закінчітіся в деякій вершіні. Число ребер, інцідентних вершіні хлопця. Якби булу Відмінною від, ланцюг та патенти Було бі продовжіті. Отже,.
Мі побудувалося цикл. Если в графі залиша невідмічені ребра, то оскількі зв'язного, среди них знайдеться хоча б Одне, інцідентне Якій-небудь вершіні на ціклі. Починаючі з вершини, ми Можемо побудуваті, як и Ранее, цикл Із ребер, что НЕ ввійшлі в. З и можна Скласти новий цикл, что проходити Із у по, потім уздовж Усього циклу, и по части циклу, что залиша від до. Оскількі граф кінцевій, то после кінцевого числа кроків, мі одержимо Ейлера цикл.
Отже, ми Готові відповістіті на запитання жителей Кенігсберга. Для цього підрахуємо степіні вершин графа, побудованого Ейлера (рис. 6.33):; ; ;. Цей граф має непарні степені вершин. Отже, цею граф НЕ має ейлерова циклу. Тобто, Неможливо пройти КОЖЕН міст по черзі за одну ходу и вернуться у віхідну точку шляху.
Приклад. Чі мают графи, зображені на ріс.5.16 (а, б), ейлерів цикл?
Малюнок 5.16 - Приклад графів
розв язання:
Щоб відповістіті на поставлене запитання, порахуємо степені вершин графа: а); ; ; ;.
Степені всех вершин графа, збережений на рис. 6.35, а, парні, отже, граф, має Ейлера цикл;
б); ; ; ; ;.
Степені вершин и графа, збережений на рис. 6.35, б, непарні, отже, граф НЕ має Ейлера цикл.
Що стосується кенігсбергськіх мостів, можна Задати інше питання: чі можливо пройти КОЖЕН міст по одному разі и не обов'язково повертатіся у віхідну точку маршруту? Відповідь на це питання жадає від нас знання следующего визначення и теореми.
Визначення. Шлях, что Включає Кожне ребро графа только один раз, назівається ейлеровім путем. У того випадка, если Ейлера шл...
