Критерий планарности Уитни Критерий планарности Уитни — это матроидное описание планарных графов. Критерий носит имя Хасслера Уитни[1]. Критерий утверждает, что граф G планарен тогда и только тогда, когда его графовый матроид[англ.] является также кографовым (то есть является двойственным матроидом[англ.] другого графового матроида). В терминах чисто теории графов этот критерий можно сформулировать следующим образом: должен существовать другой (двойственный) граф G'=(V',E') и биективное соответствие между рёбрами E' и рёбрами E исходного графа G, такое, что подмножество T рёбер E образует остовное дерево графа G тогда и только тогда, когда рёбра, соответствующие дополнению множества E-T образуют остовное дерево графа G'. Существуют и другие критерии планарности, например, теорема Понтрягина — Куратовского. Алгебраическая двойственностьЭквивалентная форма критерия Уитни гласит, что граф G планарен тогда и только тогда, когда он имеет двойственный граф, графовый матроид которого двойственен графовому матроиду графа G. Граф, графовый матроид которого двойственен графовому матроида графа G, известен как алгебраически двойственный граф для графа G. Тогда критерий планарности Уитни можно перефразировать следующим образом: граф планарен тогда и только тогда, когда у него есть алгебраически двойственный граф. Топологическая двойственностьЕсли граф вложен в топологическую поверхность, такую как плоскость, таким образом, что любая грань при вложении является топологическим диском, тогда двойственный граф вложения определяется как граф (в некоторых случаях — мультиграф) H, который имеет вершину для каждой грани вложения и ребро для каждой пары смежных граней. Согласно критерию Уитни следующие условия эквивалентны:
Можно определить двойственные графы графа, вложенного в неплоские поверхности, такие как тор, но такие двойственные графы, в общем случае, не имеют соответствия с сечениями, циклами и остовными деревьями, которое требует критерий Уитни. Примечания
Литература
|
Portal di Ensiklopedia Dunia
