86405 (612740), страница 3

Файл №612740 86405 (Основи теорії графів. Властивості ойлерових та гамільтонових графів) 3 страница86405 (612740) страница 32016-07-30СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

– довільна вершина графа . Побудуємо по індукції маршрут

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

, з якої вийшли. Отримаємо цикл

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

Теорема 2.1 Для зв’язного графа наступні умови еквівалентні:

  1. - ойлерів граф;

  2. кожна вершина має парний степінь;

  3. множину ребер графа можна розбити на прості цикли.

Доведення.

Нехай - ойлерів цикл графа . Будемо рухатись по циклу

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

Оскільки - зв’язний граф , степінь кожної вершини дорівнює принаймні 2; тому в силу леми 2.1 містить простий цикл

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

циклів

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

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

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

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

.

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

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

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

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

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

і .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доведення.

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

А0

А1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Виділену умову ми коротко назвемо умовою різноманітності.

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

Характеристики

Тип файла
Документ
Размер
138,86 Mb
Тип материала
Предмет
Учебное заведение
Неизвестно

Список файлов курсовой работы

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6374
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее