НОУ ІНТУІТ, Лекція, Уявлення про планарний граф
Тріангульований граф
Розглянемо плоский граф із п'ятьма вершинами.
Якщо додати до нього ребра і , отриманий новий граф теж буде плоским.
До цього графу не вдається додати жодного ребра те щоб новий граф теж був плоским.
Плоский граф називається максимально плоским якщо неможливо додати до нього жодного ребра так, щоб отриманий граф був плоским. Зображений граф є максимально пласким.
Кожна грань у плоскій поданні максимально плоского графа має вершини. Тому максимально плоский граф називають тріангульованим.
Операція додавання нових ребер, в результаті якої в плоскому поданні кожна грань має рівно 3 вершини, називається тріангуляціі графа .
Завдання 1. На ділянці три будинки та три колодязі. Від кожного будинку до кожної криниці веде стежка.
Коли власники будинків посварилися, вони задумали прокласти дороги від кожного будинку до кожної криниці так, щоб не зустрічатися на шляху до криниць. Потрібно показати, що їхні наміри не можуть здійснитись.
Рішення. Для розв'язання задачі достатньо довести, що граф , зображений малюнку, не плоский.
Припустимо, що граф — плоский, тобто його плоске уявлення . Граф — зв'язковий, не має жодного мосту, тому немає і перегородок. За формулою Ейлера, . Тут число вершин, число ребер, число граней з урахуванням нескінченної грані. Підрахуємо число вершин і ребер: = 6 = 9, тому .
Тепер оцінимо подвоєне число ребер. Зауважимо, що у графі немає простих циклів довжиною 3, тобто межа будь-якої грані у плоскому поданні графа містить не менше чотирьох ребер. Зауважимо, що кожне ребро є межею двох граней, такяк ми враховуємо і нескінченну грань. У цьому число може бути більше подвоєного числа всіх ребер: . Якби ми знали число ребер у межі кожної грані, то їх сума має дорівнювати; але відомо, що , а , звідки . Отримана суперечність доводить, що припущення було неправильне, тобто граф не плоский. Таким чином, наміри сусідів неможливі.
Завдання 2. Кожен із чотирьох сусідів поєднав свій будинок із трьома іншими доріжками, які перетиналися лише біля будинків.