Алгоритм Дейкстра

~

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

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

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

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

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

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

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

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

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

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

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

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

Потужність найбільшого паросполучення називається числом паросполучення графа; позначення - (G).

Домінуюче безліч вершин (ДМВ) - така безліч вершин графа, що кожна вершина графа або належить ДМВ, або інцидентна деякій вершині, що належить ДМВ.

Верхове покриття (ВП) - така безліч вершин графа, що кожне ребро графа інцидентне хоча б одній вершині, що належить ДМВ.

Потужність найменшого верхового покриття називається числом верхового покриття графа; позначення - (G).

Домінуюче безліч ребер (ДМР), чи реберне покриття - така безліч ребер зв'язного графа, що кожна вершина графа інцидентна хоча б одному ребру, що входить у ДМР.