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

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

Критерій планарності Вітні — це матроїдний опис планарних графів. Критерій носить ім'я Шаблон:НпШаблон:Sfn. Критерій стверджує, що граф $G$ планарний тоді й лише тоді, коли його Шаблон:Не перекладено є також кографовим (тобто є Шаблон:Не перекладено іншого графового матроїда).

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

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

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

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

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

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

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

• поверхня, на якій існує вкладення, топологічно еквівалентна площині, сфері або проколотій площині;
• граф $H$ алгебрично двоїстий $G$;
• будь-який простий цикл у $G$ відповідає мінімальному перерізу в графі $H$, і навпаки;
• будь-який простий цикл у $H$ відповідає мінімальному перерізу в графі $G$, і навпаки;
• будь-яке кістякове дерево в $G$ відповідає доповненню кістякового дерева в графі $H$, і навпакиШаблон:Sfn.

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття. Див., зокрема, стор. 5–6 розділу 2.5 «Bon-matroid of a graph», стор. 19–20 розділу 5.6 «Graphic and co-graphic matroids» і стор. 38–47 розділу 9 «Graphic matroids»