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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також ред.

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

Примітки ред.

↑ Whitney, 1932, с. 339–362.
↑ Tutte, 1965, с. 1–47.

Література ред.

Hassler Whitney. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34, вип. 2. — DOI:10.1090/S0002-9947-1932-1501641-2.
Tutte W. T. Lectures on matroids // Journal of Research of the National Bureau of Standards. — 1965. — Т. 69B. — DOI:10.6028/jres.069b.001. Архівовано з джерела 13 березня 2017. Процитовано 22 травня 2022.. Див., зокрема, стор. 5–6 розділу 2.5 «Bon-matroid of a graph», стор. 19–20 розділу 5.6 «Graphic and co-graphic matroids» і стор. 38–47 розділу 9 «Graphic matroids»

[FOOTNOTEWhitney1932339–362-1] Whitney, 1932, с. 339–362.

[FOOTNOTETutte19651–47-2] Tutte, 1965, с. 1–47.

[1]

[2]