UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваОбходи графів (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1825
Скачало237
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Обходи графів

 

Початок теорії графів як розділу математики пов’язують із так званою

задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга були

розташовані на річці Прегель так, як зображено на рис.3.11,а.

 

 

а) б)

 

Рис.3.11

 

Задача полягає в тому, чи можна, починаючи з будь-якої точки (А,B,C або

D), здійснити прогулянку (обхід) через усі мости так, щоб пройти кожен

міст тільки один раз і повернутися у вихідну точку.

 

Оскільки суттєвими є тільки переходи через мости, то план міста можна

зобразити у вигляді графа G (з так званими кратними ребрами), вершинами

якого є береги і острови (точки А,В,С і D), а ребрами ( мости

(див. рис.3.11,б). Тоді задачу про кенігсберзькі мости можна мовою

теорії графів сформулювати таким чином: чи існує в графі G цикл, який

містить усі ребра цього графа? Інше відоме формулювання цієї проблеми

виглядає так: чи можна намалювати фігуру, що зображає граф G, не

відриваючи олівця від паперу і не повторюючи ліній двічі, почавши і

закінчивши цю процедуру в одній з вершин фігури? Вперше відповідь на це

питання дав Л.Ейлер у 1736 році. Робота Ейлера, яка містить цей

розв’язок, вважається початком теорії графів.

 

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

Зв’язний граф, який має ейлерів цикл, називається ейлеровим графом.

 

Теорема 3.20 (теорема Ейлера). Зв’язний граф G є ейлеровим тоді і тільки

тоді, коли степені всіх його вершин парні.

 

Доведення. Необхідність. Нехай G ( ейлерів граф. Ейлерів цикл цього

графа, проходячи через кожну вершину, заходить у неї по одному ребру, а

виходить ( по іншому. Це означає, що кожна вершина інцидентна парній

кількості ребер ейлерового циклу, а оскільки цей цикл містить усі ребра

графа, то звідси випливає парність степенів усіх вершин графа.

 

Достатність. Припустимо, що степені всіх вершин графа G =(V,E ) парні.

Візьмемо деяку вершину v1(V і розпочнемо з неї обхід графа, кожен раз

обираючи ребро, яке раніше не використовувалось. Оскільки степінь кожної

вершини парний і ненульовий, то цей шлях може закінчитися тільки у

вершині v1, утворивши таким чином цикл Z1. Якщо в результаті описаного

процесу використано всі ребра графа G, то шуканий ейлерів цикл

побудовано. Якщо ж Z1 містить не всі ребра графа G, то вилучимо з G всі

ребра, які входять у Z1. Одержимо граф G1 ( підграф графа G, всі

вершини якого також матимуть парні степені (це випливає з того, що і G,

i Z1 мають вершини тільки парних степенів). Крім того, внаслідок

зв’язності графа G Z1 i G1 мають принаймні одну спільну вершину v2.

Відтак, починаючи з вершини v2, побудуємо цикл Z2 у графі G1. Позначимо

через Z1( частину циклу Z1 від v1 до v2, а через Z1(( ( частину циклу

Z1 від v2 до v1. Отримаємо новий цикл Z1(, Z2, Z1((, що веде з v1 у v1.

Якщо цей цикл ейлерів ( процес завершився. У противному разі продовжуємо

аналогічні побудови ще раз і т.д. Цей процес завершиться побудовою

шуканого ейлерового циклу.

 

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

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ