Гамільтоновим назив. простий цикл, який проходить через кожну вершину графа.
Граф, в якому є ланцюг, що проходить через кожну вершину, містить гамільтонів ланцюг.
Граф називається гальмітоновим, якщо він містить гальмінтований цикл, містить кожну вершину графа тільки один раз. Такий цикл існує далеко не в кожному графі. більш того, через будь – які дві вершини графа, який розглядається, може пройти простий цикл (у цьому випадку граф G називається циклічно зв’язним), а гальмі тонів цикл при цьому може відсутнім.
Поняття укладання графа. Пласкі та планарні графи.
Див. на листку А4.
Гранню плоского графа називається максимальне заключення множина точок площини, кожну пару яких можна з’єднати неперервною лінією баз само перетинів і перетинів ребер графа відмінних від його кінців. Межа грані – це множина ребер, що належать грані. Граф G називається планарним (плоским), якщо існує ізоморфний йому граф, який може бути зображений на площині без перетину ребер.
Теорема. Ейлера та властивості планарного графа
Граф містить ейлерів цикл тоді і тільки тоді, коли він зв’язний і степені всіх його вершин – парні. Якщо граф ейлерів, то він зв’язний і при обході ейлерова циклу захід і вихід в чергову вершину вносить дві одиниці в її степінь (тому що ребра не повторюються). Оскільки проходять всі ребра графа, то степені всіх вершин – парні. Гранню плоского графа називається максимальне заключення множина точок площини, кожну пару яких можна з’єднати неперервною лінією баз само перетинів і перетинів ребер графа відмінних від його кінців. Межа грані – це множина ребер, що належать грані.
Критерії планарності
Операція підрозбиття ребра е (е=(v,w)) полягає в тому, що з графа вилучається ребро е, до множини вершин додається вершина u, до множини ребер додаються ребра (v, u) та (u, w).
Графи назив. гомеоморфними, якщо їх можна отрим. один з одного за допомогою підрозбиття ребер. Ці графи мають однаковий характер планарності.
Теорема Портнягіна-Куратовського: граф планарний тоді і тільки тоді, коли не містить під графа, гомеоморфного К5 або К3,3
Граф, що містить підграф, який за допом. операції стягування може бути перетворений в К5 або К3,3 – не є планарним.
Критерії планарності
Граф (абстрактний або геометричний),що має геометричну реалізацію y R2 (інакше – плоску – реалізацію), називається планарним. Якщо граф має n – вершин (n?3) та m – ребер, то справджується твердження: m<=3n-6. Якщо граф має n – вершин та m – ребер, при чому компонент зв’язності є планарним, то виконується наступне співвідношення: m<=3n-3k-3<=3n-6.
1)В-вершина,р-ребра,г-кількість граней, в-р+г=2 (Якщо граф зв’язний плоский);
2) в-р+г=k+1, тоді г=р-в+k+1(плоский граф з k-звязними компонентами);
3)Якщо граф має n-вершин (n>=3), m-ребер, тоm<=3n-6 ;
4) Якщо граф має n-вершин m-ребер(m>=3), k-компонент звязності , і є планарним то m<=3n-3k-3<=3n-6 ;
5) Кожен планарний граф містить вершини степінь яких =5 або менше.
78. Хроматичне число графа
Мінімальна кількість фарб, для якої існує правильне розфарбування графа G,
називається (вершинним) хроматичним числом графа G й позначається χ(G).
Це розфарбування називається мінімальним.
Хроматичне число порожнього графа дорівнює 1. Якщо граф має хоча б одне ребро, його хроматичне число не менше 2, для довільного підграфа H графа G справджується нерівність χ(H) ≤ χ(G).
Теорема 53. Хроматичне число графа дорівнює найбільшому з хроматичних
чисел його зв’язних компонент.
Якщо для розфарбування кожної зв’язної компоненти достатньо k фарб, то й для розфарбування всіх зв’язних компонент достатньо k фарб.
Теорема 54. Якщо в графі G вершина v має степінь k і граф G-v можна правильно розфарбувати в k' > k кольорів, то граф G можна правильно розфарбу в k' кольорів.
Висновок 54.1. Якщо в графі G вершина v має степінь k і χ(G-v) > k, то χ(G) = χ(G-v). За теоремою χ(G) ≤ χ(G-v). Але G-v⊆G, тому χ(G-v) ≤ χ(G), і χ(G) = χ(G-v).
Висновок 54.2. Якщо Δ(G) — найбільший зі степенів вершин графа G, то χ(G) ≤
1+Δ(G).
79. Гіпотеза чотирьох фарб та теорема про п’ять фарб для планарних графів
Гіпотеза чотирьох фарб пов’язана з розфарбуванням політичних географічних карт. Вважається, що територія кожної країни є зв’язною областю, а суміжні країни мають спільну межу у вигляді лінії (а не однієї спільної точки). Території суміжних країн фарбуються в різні кольори. Гіпотеза полягає в тому, що для будь-якої карти достатньо чотирьох фарб. Ця гіпотеза має еквівалентне формулювання в термінах графів. Областям карти відповідають вершини графа, їх межам — ребра. Очевидно, що цей граф плоский. Таким чином, гіпотеза чотирьох фарб полягає в існуванні правильного
розфарбування вершин довільного планарного графа не більш ніж у чотири кольори.
Теорема 55 (про 5 фарб). Для правильного розфарбування довільного планарного графа достатньо п’яти фарб. Оскільки ізоморфні графи мають однакові хроматичні числа, то твердження достатньо довести для плоских графів.
