Критерий планарности Уитни — это матроидное описание планарных графов. Критерий носит имя Хасслера Уитни[1]. Критерий утверждает, что граф G планарен тогда и только тогда, когда его графовый матроид является также кографовым (то есть является двойственным матроидом другого графового матроида).
В терминах чисто теории графов этот критерий можно сформулировать следующим образом: должен существовать другой (двойственный) граф 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. — PMC 1076008.
- Tutte W. T. Lectures on matroids // Journal of Research of the National Bureau of Standards. — 1965. — Т. 69B. — doi:10.6028/jres.069b.001.. См., в частности, стр. 5–6 раздела 2.5 "Bon-matroid of a graph", стр. 19–20 раздела 5.6 "Graphic and co-graphic matroids" и стр. 38–47 раздела 9 "Graphic matroids"
Эта страница в последний раз была отредактирована 13 июня 2018 в 08:03.
Обычно почти сразу, изредка в течении часа.