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