Критерий планарности Уитни
Материал из Википедии — свободной encyclopedia
Критерий планарности Уитни — это матроидное описание планарных графов. Критерий носит имя Хасслера Уитни[1]. Критерий утверждает, что граф G планарен тогда и только тогда, когда его графовый матроид[англ.] является также кографовым (то есть является двойственным матроидом[англ.] другого графового матроида).
В терминах чисто теории графов этот критерий можно сформулировать следующим образом: должен существовать другой (двойственный) граф G'=(V',E') и биективное соответствие между рёбрами E' и рёбрами E исходного графа G, такое, что подмножество T рёбер E образует остовное дерево графа G тогда и только тогда, когда рёбра, соответствующие дополнению множества E-T образуют остовное дерево графа G'.
Существуют и другие критерии планарности, например, теорема Понтрягина — Куратовского.