П. 4. Ейлерови графи.
Ми вже говорили, що історично теорія графів (як і топологія) зародилася при вирішенні Ейлером головоломок, в яких потрібно викреслити на площині розчерком замкнуті криві, обводячи кожну ділянку в точності один раз.
Визначення 24.Ейлеровим шляхом в графі називається шлях, який містить всі ребра графа.
Визначення 25.Ейлеровим циклом в графі називається цикл, що містить всі ребра графа.
Визначення 26. Граф, що володіє ейлеровим циклом. називається ейлеровим графом.
Теорема 2. Якщо граф має ейлеровим циклом, то він зв'язний.
Приклади ейлерових графів:
1) план виставки, якщо експонати розташовані по обидва боки залів, тобто можна скласти таке собі замкнене маршрут, що за кожним залом відвідувач зможе пройти в точності два рази - по одному з кожної сторони в різних напрямках.
2) Будь-яке місто можна обійти, пройшовши по кожній вулиці рівно два рази - по одному в кожному напрямку.
3) На малюнку зображена схема зоопарку. Вершини графа - вхід, вихід, перехрестя, повороти, тупики. Ребра - доріжки, уздовж яких розташовані клітини. Знайдіть маршрут, по якому екскурсовод міг би провести відвідувачів, показавши їм всіх звірів і не проходячи більше одного разу жодної ділянки шляху.
Зауваження. Спосіб обходити всі ребра графа можна використовувати, наприклад, для відшукання шляху, що дозволяє вибратися з лабіринту. Якщо відомо, що у лабіринту все «стінки» пов'язані один з одним, тобто немає замкнутих маршрутів, за якими можна повертатися у вихідну точку, то такий лабіринт завжди можна обійти весь, торкаючись стінки однією рукою, наприклад, правої.
Існує правило Тарра (французький математик) - правило обходу будь-якого лабіринту - при обході лабіринту слід, потрапляючи в будь-яке перехрестя А вперше за деяким шляху а. при поверненні в цей перехрестя А уникати користуватися шляхом а до тих пір, поки це можливо; і лише тільки в тому випадку йти по шляху а у зворотний бік, коли всі інші шляхи з А будуть пройдені двічі.
Теорема 3. Для того, щоб зв'язний граф (мультіграф) був ейлеровим, необхідно і достатньо, щоб мірі всіх його вершин були парними.
Зауваження. Дана теорема дозволяє вирішити задачу про семи кенігсберзькими мостах.
Рішення завдання про семи кенігсберзькими мостах.
В опитування завдання: чи можливо знайти такий маршрут, який закінчувався б на тому ж березі, де і починався, проходив би по всіх мостах, але по кожному мосту - тільки один раз?
У термінах теорії графів ця задача може бути сформульована так: чи є мультіграф семи кенігсберзькими мостів ейлеровим графом?
Знайдемо ступеня вершин. Ступінь А = 3, ст. В = 5, ст. D = 3, ст. С = 3.
З теореми 3 випливає, що даний мультіграф неейлеров, так як його вершини мають непарну ступінь. З цієї ж теореми видно, як потрібно доповнити граф, що б він став ейлеровим.
Відповідь. Такий маршрут не існує.
П. 4. Дводольні графи.
Визначення 27. Граф називається дводольним. якщо безліч його вершин V можна розбити на два таких непересічних підмножини V1 і V2. що ніякі дві вершини з одного і того ж підмножини пов'язані між собою ребрами.
Зауваження. Щоб підкреслити, що даний граф - двочастковий, його вершини на діаграмі мають у своєму розпорядженні паралельними рядками або стовпцями:
Д вудольние графи корисні, коли досліджувані об'єкти поділяються на дві групи так, що всередині груп цікавлять нас взаємодії відсутні. У генетиці, наприклад, це можуть бути ознаки і гени, в демографії - особини різної статі, в екології - хижаки і жертви, в економіці - виробники і споживачі і т. Д.
Визначення 28. дводольні граф називається повним дводольним. якщо кожна вершина V1 з'єднана з кожною вершиною V2.
По виду діаграми графа не завжди просто визначити, чи є даний граф дводольним. Адже зовсім не обов'язково, щоб вершини двудольного графа розташовувалися двома паралельними рядками. Наприклад, будь-яка проста незамкнутая ланцюг - двочастковий граф, як і будь-яке дерево.
Теорема 4. Граф двудолен тоді і тільки тоді, коли всі його прості цикли мають парну довжину. (Прості цикли - все вершини різні, початкова і кінцева вершини збігаються)
З дводольними графами пов'язана задача про призначення. Нехай є кілька робочих місць для будівельників, кілька - для слюсарів, якесь число місць для малярів, монтажників і т. Д. - всього m робочих місць. З іншого боку, є n претендентів. Причому, деякі з претендентів володіють декількома професіями. Чи можна всіх претендентів забезпечити роботою, і кожному з них надати посаду відповідно до його професійною підготовкою?
Зрозуміло, що це можна зробити далеко не завжди. По-перше, д. Б. m ≥ n. Але цього мало, нехай, наприклад, вакантними є три місця монтажника і одне місце будівельника. Тоді групу, що складається з двох будівельників і одного будівельника - монтажника, не можна забезпечити роботою. Один з будівельників виявиться незайнятим.
Сформулюємо задачу в термінах графів. Нехай V1 - безліч претендентів, V2 - безліч вакантних робочих місць. Вершину a з V1 з'єднаємо ребром з вершиною b з V2. якщо претендент a здатний зайняти робоче місце b. Тоді отримаємо двочастковий граф G (рис. 9) Наше завдання полягає в тому, щоб з цього графа виділити підграф G1. що складається з компонент, в кожній з яких тільки дві вершини, і ці вершини з'єднані ребром (рис. 10). G1 - підграф призначень.
Теорема 5 (необхідна і достатня умова існування подграфа призначення)
Нехай безліч V1 двудольного графа G містить n вершин. Для того, щоб граф G містив підграф призначень G1. необхідно і достатньо, щоб для будь-якої підмножини. що містить k вершин, k = 1,2, ..., n. знайшлося k вершин з V2. кожна з яких з'єднана ребром хоча б з однією вершиною з А.
У термінах початкової завдання це означає, що яку б групу з k претендентів ми б не взяли, знайдеться k посад, кожну з яких здатний зайняти хоча б одна людина з взятої групи.
Зауваження 1. Від обмеження m ≥ n можна відмовитися і вивчати питання про те, скільки і яких подграфов призначень з тим або іншим числом компонент можна утворити з даного двудольного графа і т. Д.
Зауваження 2. Німецький математик Герман Вейль називав завдання про призначення завданням про сільських весіллях. У його трактуванні V1 і V2 - це безлічі дівчат і юнаків, які живуть в одному селі, а ребра графа означають, що юнак і дівчина знайомі (або симпатичні) один з одним. Бажаючи забезпечити кожну дівчину нареченим з безлічі знайомих (або симпатичних) хлопців, ми повинні будемо знайти в цьому дводольному графі підграф призначень.
Зауваження 3. Подібно дводольним графам можна розглядати трехдольние і k -дольние з будь-яким k.
П. 5. Планарні і плоскі графи.
Серед ізоморфних діаграм одного і того ж графа можуть бути діаграми з ребрами, що перетинаються не тільки в вершинах. Деякими з таких діаграм легко замінити ізоморфними, позбавленими цього недоліку.
Визначення 29. Граф називається планарним, якщо його можна зобразити на площині діаграмою, ребра якої перетинаються тільки у вершинах.
Саму діаграму називають плоским графом.
Зауваження. Одні графи можна намалювати на площині так, щоб їх ребра не мали спільних точок, крім вершин їм належить; інші так малювати не можна. В силу цього окремі графи можуть розглядатися як географічні карти, нанесення на площину або сферу.
Визначення 30. Якщо планарний граф односвязен, то його плоский граф називається картою.
На ріс.а) зображений не плоский граф. На рис. b) зображений той же граф, тільки плоский.
На рис. с) зображений не планарний граф, на рис. d) - ізоморфний йому плоский граф - карта. На відміну від географічних карт плоский однозв'язний граф може мати висячі вершини.
Розглянемо карту деякого графа.
Визначення 31.Гранью в плоскому поданні графа називається частина площини, обмежена простим циклом і не містить усередині інших циклів.
На рис. а) (1,2,4,1) - не межа, тому що вона містить у собі (1,2,3,1). Всього в графі чотири грані: (1,7.4,1), (1,4,2,3,1), (1,2,3,1), (2.6,5,4,2).
На ріс.b) (1,2,3,4,1) - грань, так як ребро (4,5) не утворює циклу.
Визначення 32. Цикл, що охоплює всі внутрішні межі, називається зовнішнім кордоном карти. Безліч точок площини, що лежать поза цим циклу, називається кордоном зовнішньої межі.
Зауваження. Будь-якому опуклого тривимірному багатограннику можна поставити у відповідність деяку карту, ребра і грані якої, включаючи зовнішню, відповідають ребрам і граням багатогранника.
Теорема 6. Для будь-якої карти число вершин (В), число ребер (Р) і число граней карти (Г), включаючи зовнішню, пов'язані рівністю: В + Г - Р = 2
Теорема 7. Повний двочастковий граф U3,3 і повний граф U5 непланарни.
Теорема 8. Для того, щоб граф G був планарним, необхідно і достатньо, щоб він не містив підграф, який можна було б звузити до U3,3 або U5.
Приклад (задача про трьох будинках і трьох колодязях)
В одному селі недалеко від трьох будинків розташовані три колодязя. У різні пори року доступним виявляється то один, то інший колодязь (в спеку один з колодязів пересихає, в мороз якийсь із них замерзає і т. Д.). Тому кожен будинок повинен бути з'єднаний стежкою з кожним колодязем, причому, стежки перетинаються між собою. З цим господарі будинків легко мирилися, поки жили в дружбі. Але ось вони посварилися, і кожен захотів мати свої власні стежки до криниць, що не перетинаються з стежками сусідів. Чи можна прокласти такі стежки?
Вирішимо цю задачу за допомогою графів. Позначимо вершини графа як a1. a2. a3. b1. b2. b3. де a1. a2. a3 - будинки, b1. b2. b3 - колодязі. Між групою вершин a1. a2. a3 і групою вершин b1. b2. b3 спостерігається відповідність. Від кожної вершини відходить три ребра до відповідних вершин. За умовою завдання, ми маємо повний двочастковий граф U3,3 з пересічними ребрами. Чи можна побудувати плоский граф, ізоморфний графу U3,3. Іншими словами, чи є граф U3,3 планарним?
Двочастковий граф U3,3 має вигляд. З теореми 7 випливає, що даний граф не є планарним. Тобто прокласти непересічні стежки не можна!
Зауваження. Доріжки можна було б влаштувати непересічними, якби один з будинків вдалося підняти над землею. Іншими словами, якщо вершини цього графа розміщувати не в площині, а в тривимірному просторі, його ребра перетинатися не будуть. Це властивість притаманне будь-якому графу.