Xreferat.com » Рефераты по математике » Основи теорії графів. Властивості ойлерових та гамільтонових графів

Основи теорії графів. Властивості ойлерових та гамільтонових графів

Властивості ойлерових та гамільтонових графів" width="63" height="22" align="BOTTOM" border="0" /> є простим графом. Нехай Основи теорії графів. Властивості ойлерових та гамільтонових графів– довільна вершина графа Основи теорії графів. Властивості ойлерових та гамільтонових графів. Побудуємо по індукції маршрут


Основи теорії графів. Властивості ойлерових та гамільтонових графів


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

Лема доведена.

Теорема 2.1 Для зв’язного графа Основи теорії графів. Властивості ойлерових та гамільтонових графів наступні умови еквівалентні:

Основи теорії графів. Властивості ойлерових та гамільтонових графів- ойлерів граф;

кожна вершина Основи теорії графів. Властивості ойлерових та гамільтонових графів має парний степінь;

множину ребер графа Основи теорії графів. Властивості ойлерових та гамільтонових графів можна розбити на прості цикли.

Доведення.

Основи теорії графів. Властивості ойлерових та гамільтонових графівНехай Основи теорії графів. Властивості ойлерових та гамільтонових графів- ойлерів цикл графа Основи теорії графів. Властивості ойлерових та гамільтонових графів. Будемо рухатись по циклу Основи теорії графів. Властивості ойлерових та гамільтонових графів. Проходження кожної вершини збільшує степінь кожної вершини на 2, і оскільки кожне ребро входить в Основи теорії графів. Властивості ойлерових та гамільтонових графів рівно раз , то будь-яка вершина має парний степінь .

Основи теорії графів. Властивості ойлерових та гамільтонових графівОскільки Основи теорії графів. Властивості ойлерових та гамільтонових графів - зв’язний граф , степінь кожної вершини дорівнює принаймні 2; тому в силу леми 2.1 Основи теорії графів. Властивості ойлерових та гамільтонових графів містить простий цикл Основи теорії графів. Властивості ойлерових та гамільтонових графів. Виключимо ребра циклу Основи теорії графів. Властивості ойлерових та гамільтонових графів, отримаємо остовний підграф Основи теорії графів. Властивості ойлерових та гамільтонових графів, в якому кожна вершина має парний степінь. Якщо Основи теорії графів. Властивості ойлерових та гамільтонових графів немає ребер , то (3) доведено. В протилеж-ному випадку застосуємо проведені вище міркування до Основи теорії графів. Властивості ойлерових та гамільтонових графів, отримаємо граф Основи теорії графів. Властивості ойлерових та гамільтонових графів, в якому степені всіх вершин є парними і так далі. Одночасно з порожнім графом Основи теорії графів. Властивості ойлерових та гамільтонових графів , Основи теорії графів. Властивості ойлерових та гамільтонових графів отримаємо розбиття множини ребер на Основи теорії графів. Властивості ойлерових та гамільтонових графів циклів

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

З теореми 2.1 випливає наступна теорема.

Теорема 2.2. Зв’язний граф є ойлеровим тоді і тільки тоді, коли кожна його вершина має парний степінь.


.Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис.2.6. Приклад ойлерового графу в теоремі 2.2


Доведення. Граф зображений на рисунку 2.6. є ойлеровим, оскільки

Степінь вершин А, F, D, C, Q = 4(парні);

Степінь вершин B, E = 2(парні);

Множина ребер цього графа є об’ єднання двох простих циклів

Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графів.

Теорема 2.3. Зв’язний граф є напівойлеровим тоді і тільки тоді , коли в ньому не більше двох вершин непарного степеня.


Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис. 2.7. Приклад напівойлерового графу до теореми 2.3


Доведення. Граф зображений на рисунку 2.7. є нпівойлеровим, оскільки

Степінь вершин А, F, C = 4(парні);

Степінь вершин B = 2(парна);

Степінь вершин E,D = 3(непарна);

Ось один з можливих варіантів обходу Основи теорії графів. Властивості ойлерових та гамільтонових графів. Початковою точкою маршрута є точка Основи теорії графів. Властивості ойлерових та гамільтонових графів, а кінцевою є точка Основи теорії графів. Властивості ойлерових та гамільтонових графів.

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

Зауважимо , що згідно з «лемою про рукостискання» - число вершин непарного степеня є парним.

Спробуємо для довільного графа вказати найменше число ланцюгів та-ких, що жодні два не мають спільних ребер і всі вони повністю накривають ра-зом весь граф. Очевидно, якщо на графі є таке сімейство ланцюгів , то кожна вершина непарного степеня повинна бути або початковою, або кінцевою вер-шиною якогось ланцюга. Загальне число вершин з непарним степенем згідно з лемою про рукостискання є парним, скажімо рівним Основи теорії графів. Властивості ойлерових та гамільтонових графів. Таким чином, кожне сімейство ланцюгів, які накривають граф , повинно містити принаймні Основи теорії графів. Властивості ойлерових та гамільтонових графів лан-цюгів.

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

Теорема 2.4. На будь-якому зв’язному графі з Основи теорії графів. Властивості ойлерових та гамільтонових графів вершинами непарного степеня існує сімейство ланцюгів, які в сукупності містять всі ребра графа в точності один раз кожне.

Доведення. Позначимо вершини з непарними степенями

Основи теорії графів. Властивості ойлерових та гамільтонових графів

Якщо ми додамо до нашого графу ребра

Основи теорії графів. Властивості ойлерових та гамільтонових графів

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

Граф , зображений на рисунку 2.8 має чотири вершини з непарним степе-нем Основи теорії графів. Властивості ойлерових та гамільтонових графів і накривається двома ланцюгами Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графів


Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис.2.8. Граф з непарним степенем вершин до теореми 2.4


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

Так, граф на рисунку 2.9. називається «шаблею Магомета», а ойлерів цикл необхідно побудувати за маршрутом, не відриваючи пера ручки від рисунку за одним разом ( тобто розчерком), викреслити фігуру, подану на рис.2.9.

Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис. 2.9. Ойлерів цикл в графі – «Шабля Магомета»


Більшість збірників математичних задач з розважальної математики містять задачі про лабіринти. Лабіринт складається з коридорів та їх перех-ресть. Отже , він може бути зображений графом, в якому ребра відповідають коридорам, а вершини – перехрестям.

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


Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис.2.10. Застосування апарату ойлерових циклів при розв’язанні задач “маршрут виставки» [3]


Припустимо, що експонати розташовані з обох сторін шляху, який про-ходить територією виставки. Виявляється, що тоді, яким би не був відповідний граф ( або лишень він був зв’язний), можна провести відвідувача так, щоб кож-ний шлях був пройдений двічі - по одному разу в кожному напрямі (див.рис.2.10).

Теорема 2.5. В зв’язному графі існує орієнтований цикл, який проходить через ребро по одному разу в кожному з двох напрямів.

Доведення.

Сформулюємо загальне правило побудови ланцюга, який проходить взовж всіх ребер графа в точності по одному разу в кожному напрямі. Розпоч-немо з довільної вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів і пройдемо вздовж Основи теорії графів. Властивості ойлерових та гамільтонових графів, відзначивши це ребро маленькою стрілкою в точці Основи теорії графів. Властивості ойлерових та гамільтонових графів, яка показує вибраний напрям. Потім перехо-димо послідовно до інших вершин. Одній й ті ж вершини можна відвідувати і декілька раз. Кожного разу , потрапивши в якусь вершину, ми будемо ставити на відповідному ребрі стрілку, яка вказує напрям прибуття. Крім того, потрап-ляючи в якусь вершину вперше, ми як-небудь відзначимо вхідне ребро, щоб потім його можна було відрізнити від інших.


Основи теорії графів. Властивості ойлерових та гамільтонових графівОснови теорії графів. Властивості ойлерових та гамільтонових графівОснови теорії графів. Властивості ойлерових та гамільтонових графів

Рис.2.11. Граф до теореми 2.5 [3]


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

Будемо продовжувати шлях до тих пір, коли це взагалі можливо .В кож-ній вершині є однакове число можливостей для входу і для виходу. Тому рух може закінчитися лише в точці Основи теорії графів. Властивості ойлерових та гамільтонових графів. Залишається перевірити , що у всіх верши-нах всі ребра будуть пройдені в обох напрямах.

Для точки Основи теорії графів. Властивості ойлерових та гамільтонових графів це ясно-всі ребра, які виходять , будуть використані, оскіль-ки в протилежному випадку ми могли б рухатися далі ; тому і всі ребра , які входять, також будуть використані, бо їх число дорівнює числу ребер, які ви-ходять. Зокрема, ребро Основи теорії графів. Властивості ойлерових та гамільтонових графів буде пройдено в обох напрямках. Але це означає , що всі ребра , які інцидентні Основи теорії графів. Властивості ойлерових та гамільтонових графів, також будуть пройдені в обох напрямах, бо перше ребро, яке входить в Основи теорії графів. Властивості ойлерових та гамільтонових графів, ребро Основи теорії графів. Властивості ойлерових та гамільтонових графів , за умовою, повинно використову-ватися для виходу лише в останню чергу. Теж саме міркування можна застосу-вати до наступного ребра Основи теорії графів. Властивості ойлерових та гамільтонових графів і наступної вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів і так далі.

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

Зауважимо, що описаний метод обходу графа може бути використаний для розв’язання задач , пов’язаних з пошуками маршрутів виходу з лабіринтів.


2.3 Приклади ойлерових графів


Приклад 2.1.Задача про призначення на посаду

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

Чи можна кожному з цих людей надати одну з тих посад, які йому підло-дять?

Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра (м,р), що з’єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд, наведений на рис.2.12:


Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис.2.12. Граф для рішення задачі про призначення на посаду


Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.

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

Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:

Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.

Наприклад, якщо один з людей є столяром, а другий - одночасно і

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: