Критерій планарності Вітні

Критерій планарності Вітні — це матроїдний опис планарних графів. Критерій названо іменем Гасслера Вітні^[en][1]. Критерій стверджує, що граф ${\displaystyle G}$ планарний тоді й лише тоді, коли його графовий матроїд^[en] є також кографовим (тобто є двоїстим матроїдом^[en] іншого графового матроїда).

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

У термінах чисто теорії графів цей критерій можна сформулювати так:

повинен існувати інший (двоїстий) граф ${\displaystyle G'=(V',E')}$ і бієктивна відповідність між ребрами ${\displaystyle E'}$ і ребрами ${\displaystyle E}$ початкового графа ${\displaystyle G}$, така, що підмножина ${\displaystyle T}$ ребер ${\displaystyle E}$ утворює кістякове дерево графа ${\displaystyle G}$ тоді й лише тоді, коли ребра, відповідні доповненню множини ${\displaystyle E-T}$ утворюють кістякове дерево графа ${\displaystyle G'}$.

Існують і інші критерії планарності, наприклад, теорема Понтрягіна — Куратовського.

Алгебрична двоїстість

Еквівалентна форма критерію Вітні:

граф ${\displaystyle G}$ планарний тоді й лише тоді, коли він має двоїстий граф, графовий матроїд якого двоїстий графовому матроїду графа ${\displaystyle G}$.

Граф, графовий матроїд якого двоїстий графовому матроїду графа ${\displaystyle G}$, знаний як алгебрично двоїстий граф для графа ${\displaystyle G}$. Тоді критерій планарності Вітні можна перефразувати так:

граф планарний тоді й лише тоді, коли він має алгебрично двоїстий граф.

Топологічна двоїстість

Якщо граф укладено в топологічну поверхню, таку як площина, так, що будь-яка грань при вкладенні є топологічним диском, то двоїстий граф вкладення визначається як граф (у деяких випадках — мультиграф) ${\displaystyle H}$, який має вершину для кожної грані вкладення і ребро для кожної пари суміжних граней. Згідно з критерієм Вітні такі умови еквівалентні:

• поверхня, на якій існує вкладення, топологічно еквівалентна площині, сфері або проколотій площині;
• граф ${\displaystyle H}$ алгебрично двоїстий ${\displaystyle G}$;
• будь-який простий цикл у ${\displaystyle G}$ відповідає мінімальному перерізу в графі ${\displaystyle H}$, і навпаки;
• будь-який простий цикл у ${\displaystyle H}$ відповідає мінімальному перерізу в графі ${\displaystyle G}$, і навпаки;
• будь-яке кістякове дерево в ${\displaystyle G}$ відповідає доповненню кістякового дерева в графі ${\displaystyle H}$, і навпаки^[2].

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

Див. також

• Перевірка планарності