и, таких як алгоритм Дейкстри, Флойда-Уоршолла и т.п. Альо ефективних алгоритмів, для поиска циклу Гамільтона мінімальної довжина немає. Через їхню відсутність, щораз Цю практичність задачу доводитися вірішуваті мето?? ом прямого перебирання.
5.7 Планарні графи
Визначення. Граф назівається правильно Укладення на площіні, если его графічне Подання таке, что ребра графа перетінаються только в его вершинах.
Визначення. Граф назівається плоским (планарного), если ВІН ізоморфній Деяк графу, правильно Укладення на площіні. Тобто плоский граф - це граф, Який можна правильно укласті на площіні.
Приклад. Графи І, подані на Наступний малюнку, ізоморфні. Граф - правильно Укладення на площіні. Отже, дані графи - плоскі.
Розглянемо граф як Малюнок на Аркуші паперу. Если граф Планарний, тобто намальованій так, что его ребра що перетінаються, и его необходимо розрізаті уздовж ребер, то граф віявіться розділенім на части, включаючі зовнішню часть. Такі части назіваються гранями. Границя кожної Грані є циклом.
Визначення. Гран планарного графа назівається така максимальна ділянка площини, что будь-які две ее точки могут буті з'єднані кривою, что НЕ перетінає ребро графа.
Завдання про возможности правильного укладання графа на площіні є актуальними у зв'язку з використанн у радіотехніці друкованне схем. Інтегральні мікросхеми складаються Із шарів мініатюрніх мікросхем, удрукованіх у пластину. ЦІ схеми наносячи на ізолятор у друкованне способ и перетінання якіх-небудь двох провідніків, у непередбачуваніх точках (не у вершинах графа), привело б до їх замикання. Тобто для друкування електричних схем просто необходимо, щоб графи (что їх зображують) були плоскими.
Задачі, пов язані Із плоскими графами, Актуальні НЕ только в радіотехніці. Пріведемо класичну задачу про трьох міста и трьох джерела постачання. Нехай є три міста, й й трьох джерела жіттєзабезпечення: водонапірна башта, електростанція и станция магістрального газопроводу. Чі можна з єднаті ЦІ міста Із Джерелі постачання водою, газом и Електрика так, щоб траншеї, проріті для ціх ліній (на одній глібіні) НЕ перетіналіся?
Ця задача зводу до побудова плоского графа, ізоморфного графу, збережений на рис. 5.21.
Малюнок 5.21 - Завдань граф
Відповідь на питання поставлені біля сформульованій задачі негативна. Завжди можна намалюваті 8 попарно неперетінаючіхся ліній, а дев ята обов язково перетне одну Із ціх восьми.
Доведення неможлівості подобной побудова спірається на теорему, доведених Жорданом. Проілюструємо ее в такий способ. Нехай - безперервна замкнута лінія без самоперетінань (рис. 5.22). Ця лінія діліть площинах на две части: зовнішню и внутрішню. Будь-які две точки и Із внутрішньої и зовнішньої частин відповідно можна з'єднати только лінією, что перетінає.
Малюнок 5.22 - Безперервна замкнута лінія
Позначімо граф, збережений на рис. 5.21 як. Замінімо граф Йому ізоморфнім (рис. 5.23).
Малюнок 5.23 - Ізоморфній граф
з'єднати вершини и без перетінання Вже проведених ребер Неможливо, тому что точка лежить усередіні області, обмеженої кривою, а точка - поза зазначеної області. Отже, граф НЕ є Планарний.
Аналогічно доводитися непланарність полного графа (рис. 5.24).
Малюнок 5.24 - Повний граф
Вікорістовуючі графи І, можна сформулюваті Наступний крітерій планарності графів.
Теорема. (Теорема Куратовського). Граф є Планарний тоді и только тоді, коли ВІН НЕ містіть підграф, ізоморфній графу або.
Існують и Інші Критерії планарності графів.
Теорема. Если - зв'язного планарного граф, что містіть вершин, ребер и граней, то винна Виконувати Умова.
За помощью теореми 6.8 задача про жіттєзабезпечення трьох будинків (рис. 6.44) вірішується в такий способ. У графа Шість вершин и дев'ять ребер:,, а Кількість граней -. Підставімо в умову. Умова теореми 6.8 НЕ віконується. Отже, граф - НЕ Планарний.
Лема. У довільному планарному графі з кількістю вершин не менше трьох має місце нерівність.
За помощью Лемі 6.1 доведемо, что граф НЕ Планарний. Граф має п'ять вершин и десять ребер як:,. Скорістаємося умів. Як бачим, Умова для графа НЕ Виконаю, отже, граф НЕ Планарний.
5.8 розфарбування графів
Нехай G=(V, E) довільній граф, а Nk={1,2, ..., k}.
