ро между сусіднімі країнамі провести через проміжок Спільного кордону. Зрозуміло что таким чином ми отримавших плоский граф.
Завдання про розфарбування карти
Знайте хроматична число.
Легко придумат карту, для якої трьох кольорів буде недостатньо. Приклад подобной карти наведені на малий. 2. Не Важко зрозуміті, что Цій карте відповідає граф, хроматична число которого рівне 4.
Мал. 2
СПРОБА придумат карту, для якої недостатньо и чотірьох кольорів, довгий годину не приводили до успіху. Тому й Дійсно вінікла наступна гіпотеза.
Гіпотеза про Чотири кольори
хроматична число будь-якого планарного графа НЕ перевіщує 4.
Теорема Хівуда
хроматична число будь-которого планарного графа НЕ перевіщує 5.
Для доведення нам Знадоби
Лема про вершину степеня lt; 5
У будь-якому звічайна плоскому графі знайдеться вершина, степінь якої НЕ перевіщує 5.
Доведення. Достатньо показати, что потрібна вершина знайдеться в одній з компонент звязності заданого графа G . Отже, можнa вважаті, что граф G звязній. Припустиме і. За відповідності про Кількість ребер з теореми Ейлера про плоскі графи
Оскількі сума n доданків менше 6n, хоча б Одне з Додавання менше 6 (тобто НЕ більше 5 так як степінь вершини - натуральне число). Отже, існує вершина v графа G така, что ()? 5. Нехай G - планарні графи. Можна вважаті, что граф G е звічайна (петлі и кратні ребра що вплівають на хроматична число) i плоским (оскількі хроматична число не змінюється при ізоморфізмі). Припустиме и будемо доводіті індукцією по n. База індукції очевидна: если звічайній граф G містіть одну вершину, то.
Крок індукції. Нехай n gt; 1 . Віберемо в графі G вершину v степеня? 5 (така вершина існує за только-що деведеню лемою). Розглянемо граф G -v . У ньом n - 1 вершина, а отже, по умові індукції існує правильне розфарбування f графа G - v
Если для розфарбування вершин, суміжніх з v , Використано менше 5 кольорів, то розфарбування f можна доповніті до правильного розфарбування графа G v «Не зайнятості» Кольорах. Тому далі можна вважаті, что для розфарбування вершин, суміжніх з v, вікорістані всі 5 кольорів. У даного випадка з v суміжні Рівно 5 вершин, позначімо їх,,,. У порядку слідування за годінніковою стрілкою відносно v (див. Мал.3).
Так як ми розглядаємо G як плоский граф, тобто як фігуру на площіні, мі маємо право користуватись геометричність міркуваннямі.
Мал.3
Будемо вважаті, что, ... ,. Позначімо через підграф графа G, породженій усіма вершинами u, что . У нашому випадка , граф містіть вершини і. Розглянемо 2 випадки.
Випадок 1: вершини и лежати в різніх компонентах звязності графа. Нехай К - компоента звязності в, что містіть вершину.
Перепозначімо f на K, перефарбувавші вершини кольору 1 в третьому, и навпаки. Нова функція f теж буде правильно розфарбування графа G - v. Дійсно, «Нові» вершини кольору 1 цієї статті не суміжні ні между собою (оскількі и Ранее малі одна колір) ні зі старими вершинами кольору 1 (знаходяться в різніх компонентах графа). Теж самє справедливо и для вершин кольору 3, а для вершин других кольорів Нічого НЕ змінілось.
Отже, ми побудувалося правильне 5-розфарбування графа G - v, при якому ні один з вершин, суміжніх з v в графі < i> G , що не має кольору 1 (в результате перефарбування вершина поміняла колір на 3, а вершини,,, збереглі колір). Отже, можна зафарбуваті вершину v в колір 1, отрімуючі правильне 5-розфарбування графа G , что и Вимагаю.
Мал. 4
Випадок 2: Вершини и лежати в одній и тій самій компоненті звязності графа. Отже, у графі G існує простий (,) ланцюг, усі вершини якої мают кольори 1 і 3. Дода до цього ланцюга ребра (,) і (,) , отрімаємо простий цикл C (виділений на мал.4 червоним), обмежуючій часть площини, яка містіть Рівно одну з вершин і. Розглянемо підграф графа G , породженій усіма вершинами кольорів 2 та 4. У даного випадка, містіть вершини і.
Припустиме, что вершини и лежати в одній компоненті звязності графа. Тоді їх можна поеднаті Ланцюг, что проходити только через вершини графа. З геометрічної точки зору, цею л...
