Доказ: будь-яка геометрична реалізація U1 є геометричною реалізацією U2, і навпаки.
Твердження 2: будь-який підрозділ U' графа U компланарний тоді і тільки тоді, коли U компланарний.
Доказ:
(=>) граф U' компланарний, отже, існує його геометрична реалізація на площині R'. Побудуємо по R' плоску геометричну реалізацію R графа U. Для цього об'єднаємо всі лінії R', що відповідають ребрам U', отриманим у результаті виконання операцій підрозділу ребер. У силу існування R граф U є компланарним.
<=) граф U компланарний, отже, існує його геометрична реалізація на площині R. Побудуємо по R плоску геометричну реалізацію R' графа U'. Для цього повторимо в будь-якій послідовності операції підрозділу ребер, що привели до побудови U'. Після виконання кожної з цих операцій будемо розбивати лінію, що відповідає ребру, що підрозділяється, на двох ліній (розбивка можна робити в будь-якій крапці, що не збігається з кінцями лінії). У силу існування R' граф U' є компланарним.
Твердження 3: якщо графи U1 і U2 гомеоморфні, те U1 компланарний тоді і тільки тоді, коли U2 компланарний.
Доказ:
(=>) за умовою U1 і U2 гомеоморфні {по визначенню} існують їхні ізоморфні підрозділи U1' і U2'. За умовою граф U1 компланарний {по утв.2} граф U1' компланарний {по утв.1} ізоморфний йому граф U2' компланарний {по утв.2} граф U2 компланарний.
(<=) аналогічно.
Твердження 4: якщо підграф U' графа U не компланарний, те U також не компланарний.
Доказ: допустимо, що граф U компланарний. Отже, існує його плоска геометрична реалізація R. Але тоді можна побудувати плоску геометричну реалізацію R' графа U': для цього досить видалити з R крапки і лінії, що відповідають тим вершинам і ребрам U, яких немає в U'. З існування R' випливає, що U' компланарний - одержали протиріччя.
Достатність теореми доводиться набагато складніше (див., наприклад, [3]).
~
Існують і інші критерії компланарності графів [3].
Розфарбування графів
Верховим розфарбуванням (далі - просто розфарбуванням) графа називається відображення безлічі вершин графа на кінцеву безліч (безліч квітів); n-розфарбування графа - розфарбування з використанням n квітів. Розфарбування називається правильної, якщо ніякі дві вершини одного кольору не суміжні. Очевидно, що для графа без петель завжди існує правильне розфарбування в |V| квітів.
Хроматичним числом графа G називається мінімальне число n=(G), таке, що існує правильне n-розфарбування.
Лема 1. У будь-якому компланарному графі без петель і кратних ребер існує вершина ступеня не більш п'яти.
Доказ: допустимо, що ступеня усіх вершин перевершують 5. Тоді 2q=Sum(deg(vi), i=1..|V|)p і q3p. Але по слідству 1 теореми 2 повинне виконуватися нерівність q3(p-2)<3p - одержали протиріччя.
~
Теорема про п'ять фарб. Кожен компланарний граф без петель і кратних ребер є не більш ніж 5-хроматичним.
Доказ: (індукцією по числу вершин).
При p=1 твердження теореми вірно. Допустимо, що (*) твердження вірне для всіх p<p0. Доведемо, що тоді воно вірно і для p0.
Розглянемо компланарний граф G без петель і кратних ребер з p0 вершинами; по лемі 1 у ньому є вершина v0 ступеня не більш 5. По припущенню індукції (*) граф G', одержуваний видаленням з G вершини v0 (очевидно, також компланарний), може бути розфарбований не більш, ніж у 5 квітів. Нехай (**) v1...vk, k=deg(v0) - усі вершини-сусіди вершини v0, розташовані по годинній стрілці відносно v0. Якщо в розфарбуванні вершин v1...vk використовується не більш 4-х квітів, то "пофарбуємо" вершину v0 у що залишився 5-й колір і одержимо правильне розфарбування.
Залишилося розглянути випадок, коли в розфарбуванні вершин v1...vk у графі G' використовується 5 квітів (k=5). Нехай ci - колір вершини vi (i=1..5). Розглянемо безліч A, що складається з вершини v1 і усіх вершин графа G, крім v0, у котрі можна дійти з v1 тільки по вершинах квітів c1 і c3. Можливі два випадки:
У першому випадку поміняємо кольору вершин безлічі A (c1c3); фарбування при цьому залишиться правильної. Дійсно, безліч A складається по визначенню з усіх вершин квітів c1 і c3, у котрі можна дійти з v1, тому серед вершин, суміжних вершинам, що належать A, немає вершин квітів c1 чи c3. Після заміни квітів вершин безлічі A вершина v1 одержить колір з3, отже, можна використовувати колір c1 для "фарбування" вершини v0 і одержати в такий спосіб правильне розфарбування графа G.
Залишається другий випадок. З приналежності вершини v3 безлічі A випливає, що існує шлях з v1 у v3 (v1Sv3), що проходить тільки по вершинах квітів c1 і c3 (див. малюнок). Розглянемо цикл L=v1Sv3(v3,v0)v0(v0,v1)v1 і замкнуту криву, що відповідає цьому циклу в геометричній реалізації графа. Вершина v2 знаходиться усередині цієї замкнутої кривої, а v4 - зовні. Це випливає, по-перше, з того, що лінії, що відповідають ребрам графа в його геометричній реалізації, не можуть перетинатися (не вважаючи кінців), і, по-друге, з (**).Визначимо безліч B, що складається з вершини v2 і усіх вершин графа G, крім v0, у котрі можна дійти з v2 тільки по вершинах квітів c2 і c4. Вершина v4 не належить B, оскільки будь-який шлях з v2 у v4 повинний проходити, принаймні, через одну вершину, що належить циклу L - тобто або через вершину v0, або через вершину, пофарбовану в кольори c1 чи c3. Отже, як і в першому випадку, можна поміняти кольору вершин безлічі B (c2c4) і "пофарбувати" v0 у c2.
~
Теорема про чотири фарби. Кожен компланарний граф без петель і кратних ребер є не більш ніж 4-хроматичним.
Проблема чотирьох фарб залишалася невирішеної протягом багатьох літ. Затверджується, що ця теорема була доведена за допомогою хитромудрих міркувань і комп'ютерної програми в 1976 році (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980). Короткий виклад ідеї їхнього доказу мається в [3].
Графи з атрибутами
У багатьох випадках елементам (вершинам і ребрам) графа ставляться у відповідність різні дані - атрибути (мітки). Якщо як атрибути використовуються цілі чи речовинні числа, то такі графи називають зваженими. Фактично, зважений граф - це функція, визначена на графі. Як атрибути можуть виступати і нечислові дані, тому я буду називати графів з атрибутами позначеними, чи атрибутованнями (Графами-а-графами). Наприклад, структурні формули хімічних сполук представляються молекулярними графами - А-графами, вершини яких відповідають атомам хімічної структури, а ребра - валентним зв'язкам між атомами. Для вершин молекулярного графа визначений, принаймні, атрибут "номер атома в періодичній таблиці елементів", для ребер - "тип валентного зв'язку (одинарна, подвійна, потрійна й ін.)"; можуть використовуватися додаткові атрибути, наприклад, заряд атома.
Для графів з атрибутами можна ввести посилене визначення ізоморфізму: будемо вважати дві А-графи ізоморфними, якщо вони ізоморфні в звичайному змісті, і, крім того, ізоморфне відображення зберігає атрибути (тобто атрибути відповідних вершин і ребер в обох графах збігаються).
Незалежні безлічі і покриття
Незалежна безліч вершин (НМВ) - безліч вершин графа, ніякі дві вершини якого не інцидентні.
Максимальна незалежна безліч вершин (МНМВ) - НМВ, що не міститься ні в якому іншому НМВ.
Зауваження: у даному визначенні "максимальність" означає "нерозширюваність"; у загальному випадку граф може мати трохи МНМВ різної потужності.
Найбільша незалежна безліч вершин - НМВ максимальної потужності.
Потужність найбільшого НМВ (очевидно, це одне з МНМВ) називається верховим числом незалежності графа (а також нещільністю, числом внутрішньої чи стійкості числом верхового упакування графа); позначення - (G).
Незалежна безліч ребер (НМР), чи паросполучення - безліч ребер графа, ніякі два ребра якого не інцидентні.
Потужність найбільшого паросполучення називається числом паросполучення графа; позначення - (G).
Домінуюче безліч вершин (ДМВ) - така безліч вершин графа, що кожна вершина графа або належить ДМВ, або інцидентна деякій вершині, що належить ДМВ.
Верхове покриття (ВП) - така безліч вершин графа, що кожне ребро графа інцидентне хоча б одній вершині, що належить ДМВ.
Потужність найменшого верхового покриття називається числом верхового покриття графа; позначення - (G).
Домінуюче безліч ребер (ДМР), чи реберне покриття - така безліч ребер зв'язного графа, що кожна вершина графа інцидентна хоча б одному ребру, що входить у ДМР.
Потужність найменшого ДМР називається числом реберного покриття графа; позначення - (G).
На малюнку позначені реберне покритті графа (пунктиром), МНМВ (білі вершини) і верхове покриття (чорні вершини).
Величини (G), (G), (G) і (G) є інваріантами графа. Між цими інваріантами існує зв'язок, установлювана наступними лемами.
Лема 1. Безліч S є найменшим верховим покриттям графа G=(V,E) тоді і тільки тоді, коли T=V(G)\S є найбільшою незалежною безліччю вершин графа.
Доказ:
(=>)
1. доведемо, що ніякі дві вершини, що входять у T, не інцидентні (тобто T є НМВ). Допустимо зворотне: (vi,vj)E(G), viT, vjT. Але це означає, що ребро (vi,vj) не покривається безліччю S - протиріччя з визначенням ВП.
2. T є найбільшим НМВ у силу мінімальності |S| і тотожності |S| + |V(G)\S| |V(G)|.
(<=)
1. доведемо, що кожне ребро G інцидентне хоча б одній вершині S (тобто S є ВП). Допустимо зворотне: (vi,vj)E(G), viS, vjS. Але це значить, що viT, vjT - протиріччя з визначенням НМВ.
2. аналогічно доказу (=>).