Алгоритм Дейкстра, Детальна інформація

проведемо через цю пряму |E| різних на півплощин;

реалізуємо кожне ребро у своїй на півплощині.

~

Виникає питання: чи будь-який граф можна реалізувати на площині? Відповідь - негативний. Геометричну реалізацію на площині допускають лише деякі графи; такі графи називаються компланарними.

Для наступного викладу нам знадобиться поняття грані. Неформально визначимо грань як частина площини, на які площина "розрізається" лініями геометричної реалізації графа. Завжди існує необмежена зовнішня грань.

- 7 вершин, 8 ребер, 3 грані

Формула Ейлера. Для будь-якої геометричної реалізації графа G=(V,E) на площині вірно: p-q+r=2, де p=|V|, q=|E|, r - число граней (без доказу).

Теорема 2. Якщо в зв'язковому планарним графі немає циклів довжини менше k і k\xF0B33, то q\xF0A3k(p-2)/(k-2), де p=|V|, q=|E|.

Доказ (не зовсім формальне): нехай граф реалізований на площині і при цьому вийшло r граней. Нехай qi - число сторін у i-й грані (див. малюнок). Кожне ребро є стороною двох граней, тому 2q=Sum(qi, i=1..r). По умови в графі немає циклів довжини менше k, але тоді qi\xF0B3k (тому що сторони грані утворять цикл) і 2q=Sum(qi, i=1..r)\xF0B3k\xF0D7r. По формулі Эйлера r=2-p+q, отже, 2q\xF0B3k\xF0D7(2-p+q), з чого випливає доказувана нерівність.

- 8 ребер, 3 грані, 3+6+7=16 сторін

~

Наслідок 1 теореми 2: для будь-якого зв'язкового пленарного графа без петель і кратних ребер виконується нерівність: q\xF0A33(p-2), де p=|V|, q=|E|.

Доказ: тому що за умовою в графі немає петель і кратних ребер, у ньому немає і циклів довжини менше 3, тому, підставляючи k=3 у нерівність HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "ПланарТ2" теоремі 2 , одержуємо: q\xF0A3k(p-2)/(k-2)=3(p-2).

~

Теорема 3. Граф K5 не компланарний.

Доказ: K5 зв'язний, у ньому немає петель і кратних ребер, але наслідок 1 теореми 2 не виконується - q=10>3(p-2)=9. Виходить, K5 не компланарний.

~

Теорема 4. Граф K33 не компланарний.

Зауваження: використання наслідку 1 теореми 2 тут не допоможе, тому що q=9<3(p-2)=12.

Доказ: у K33 немає циклів довжини менше 4, тому застосуємо нерівність HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "ПланарТ2" теоремі 2 безпосередньо (при k=4): q=9>4(p-2)/2=8. Отже, K33 не компланарний.

~

Теорема Понтрягіна-Куратовского (критерій компланарності графів). Граф G планарин тоді і тільки тоді, коли він не містить підграфов, гомеоморфних K5 чи K33.

Доказ: необхідність випливає з тверджень 1-4 (див. нижче), а також з того факту, що графи K5 і K33 не компланарні (відповідно до теорем HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "ПланарТ3" 3 і HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "ПланарТ4" 4 ).

Твердження 1: якщо графи U1 і U2 ізоморфні, то U1 компланарний тоді і тільки тоді, коли U2 компланарний.

Доказ: будь-яка геометрична реалізація 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 компланарний.