REFERATUA.ORG.UA — База українських рефератів



Головна Математика, Геометрія → Алгоритм Дейкстра

компланарним.

Твердження 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 і q3p. Але по слідству 1 теореми 2 повинне виконуватися нерівність q3(p-2)<3p - одержали протиріччя.

~

Теорема про п'ять фарб. Кожен компланарний граф без петель і кратних ребер є не більш ніж 5-хроматичним.

Доказ: (індукцією по числу вершин).

При p=1 твердження теореми вірно. Допустимо, що (*) твердження вірне для всіх p

Розглянемо компланарний граф 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. Можливі два випадки:

  • v3A;

  • v3A.

    У першому випадку поміняємо кольору вершин безлічі A (c1c3); фарбування при цьому залишиться правильної. Дійсно, безліч 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 (c2c4) і "пофарбувати" v0 у c2.

    ~

    Теорема про чотири фарби. Кожен компланарний граф без петель і кратних ребер є не більш ніж 4-хроматичним.

    Проблема чотирьох фарб залишалася невирішеної протягом багатьох літ. Затверджується, що ця теорема була доведена за допомогою хитромудрих міркувань і комп'ютерної програми в 1976 році (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980). Короткий виклад ідеї їхнього доказу мається в [3].

    Графи з атрибутами

    У багатьох випадках елементам (вершинам і ребрам) графа ставляться у відповідність різні дані - атрибути (мітки). Якщо як атрибути використовуються цілі чи речовинні числа, то такі графи називають зваженими. Фактично, зважений граф - це функція, визначена на графі. Як атрибути можуть виступати і нечислові дані, тому я буду називати графів з атрибутами позначеними, чи атрибутованнями (Графами-а-графами). Наприклад, структурні формули хімічних сполук представляються молекулярними графами - А-графами, вершини яких відповідають атомам хімічної структури, а ребра - валентним зв'язкам між атомами. Для вершин молекулярного графа визначений, принаймні, атрибут "номер атома в періодичній таблиці елементів", для ребер - "тип валентного зв'язку (одинарна, подвійна, потрійна й ін.)"; можуть використовуватися додаткові атрибути, наприклад, заряд атома.

    Для графів з атрибутами можна ввести посилене визначення ізоморфізму: будемо вважати дві А-графи ізоморфними, якщо вони ізоморфні в звичайному змісті, і, крім того, ізоморфне відображення зберігає атрибути (тобто атрибути відповідних вершин і ребер в обох графах збігаються).

    Незалежні безлічі і покриття

    Незалежна безліч вершин (НМВ) - безліч вершин графа, ніякі дві вершини якого не інцидентні.

    Максимальна незалежна безліч вершин (МНМВ) - НМВ, що не міститься ні в якому іншому НМВ.

    Зауваження: у даному визначенні "максимальність" означає "нерозширюваність"; у загальному випадку граф може мати трохи МНМВ різної потужності.

    Найбільша незалежна безліч вершин - НМВ максимальної потужності.

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

    Незалежна безліч ребер (НМР), чи паросполучення - безліч ребер графа, ніякі два ребра якого не інцидентні.

    Потужність найбільшого паросполучення називається


  •  
    Загрузка...