Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Планарний граф



План:


Введення

Планарний граф - граф, який може бути зображений на площині без перетину ребер.

Більш строго: Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним, його вершини - це точки площині, а ребра - лінії на ній. Області, на які граф розбиває поверхню, називаються гранями. Плоский граф - граф, покладений на площину. Граф називається планарним, якщо він ізоморфний деякому плоскому графу.


1. Два приклади непланарних графів

Тут ми користуємося інтуїтивним поняттям слова "лінія", докладніше див відповідній статті.

1.1. Повний граф з п'ятьма вершинами

K 5, повний граф з 5 вершинами

Лема. Повний граф з п'ятьма вершинами 5) не можна укласти на площину.

1.2. "Хатки і колодязі"

Граф "будиночки і криниці" (K 3,3)

Задача про трьох колодязях. Є три будинки і три криниці. Чи можна так прокласти доріжки між будинками і колодязями, щоб від кожного будинку до кожного колодязя вела доріжка, і ніякі дві доріжки не перетиналися б. Мости будувати не можна.

Лемма. Повний двочастковий граф з трьома вершинами в кожній з часток (До 3,3) не можна укласти на площину.


2. Теорема Понтрягина-Куратовского

Очевидно твердження: якщо граф G містить подграф, гомеоморфни K 5 чи K 3,3, його неможливо розкласти на площині. Виявляється, вірно і зворотне.

Граф планарії тоді і тільки тоді, коли він не містить подграфов, гомеоморфних повного графу з п'яти вершин (K 5) або графу "будиночки і криниці" (K 3,3).

Теорему також можна сформулювати в наступному варіанті (іноді його називають "теорема Вагнера").

Граф планарії тоді і тільки тоді, коли не містить подграфов, стягуються у K 5 чи K 3,3.


3. Ознаки непланарних графів

  • достатня умова - якщо граф містить двочастковий подграф K 3,3 або повний подграф K 5, то він є не планарним;
  • необхідна умова - якщо граф не планарний, то він повинен містити більше 4 вершин, ступінь яких більше 3, або більше 5 вершин ступеня більше 2.

4. Формула Ейлера

Для зв'язного плоского графа справедливо наступне співвідношення між кількістю вершин | V (G) | , Ребер | E (G) | і граней | F (G) | (Включаючи зовнішню грань):

\ | V (G) | - | E (G) | + | F (G) | = 2.

Воно було знайдено Ейлером в 1736 р. [1] при вивченні властивостей опуклих багатогранників. Це співвідношення справедливо і для інших поверхонь з точністю до коефіцієнта, званого ейлеровой характеристикою. Це інваріант поверхні, для площині або сфери він дорівнює двом. Формула має безліч корисних наслідків. Якщо кожна грань обмежена не менш ніж трьома ребрами (за умови, що в графі більше двох ребер), а кожне ребро розділяє дві грані, то

3 | F (G) | \ le 2 | E (G) |,

отже,

| E (G) | \ le 3 | V (G) | -6,

тобто, при більшій кількості ребер такий граф свідомо непланарен. Протилежне твердження не вірно, наприклад, граф Петерсена. Звідси випливає, що в планарному графі завжди можна знайти вершину мірою не більше 5.


5. Планарниє графи в задачах

Розмальовка карти. Необхідно розфарбувати плоску карту заданим числом фарб так, що будь-які дві країни, які мають загальний ділянку кордону, мали різні кольори. Виявляється, що за відсутності анклавів, ніколи не бракує чотирьох фарб, але це твердження надзвичайно складно довести, см. Проблема чотирьох фарб.

Примітки

  1. Ф. Харарі Теорія графів УРСС стор 126

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Граф
Граф Нулін
Граф Петерсена
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
Граф Лестер
© Усі права захищені
написати до нас
Рейтинг@Mail.ru