76. Теорема. Ейлера та властивості планарного графа

Граф містить ейлерів цикл тоді і тільки тоді, коли він зв’язний і степені всіх його вершин – парні. Якщо граф ейлерів, то він зв’язний і при обході ейлерова циклу захід і вихід в чергову вершину вносить дві одиниці в її степінь (тому що ребра не повторюються). Оскільки проходять всі ребра графа,  то степені всіх вершин – парні. Гранню плоского графа називається максимальне заключення множина точок площини, кожну пару яких можна з’єднати неперервною лінією баз само перетинів і перетинів ребер графа відмінних від його кінців. Межа грані – це множина ребер, що належать грані.

77. Критерії планарності

Операція підрозбиття ребра е (е=(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 фарб). Для правильного розфарбування довільного планарного графа достатньо п’яти фарб. Оскільки ізоморфні графи мають однакові хроматичні числа, то твердження достатньо довести для плоских графів.