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

Планарный граф и его двойственный граф. Каждый цикл в синем графе является минимальным разрезом в красном графе, и наоборот, поэтому эти два графа являются алгебраическими двойственными и имеют двойственные графические матроиды.

В математике критерий планарности Уитни — это теоретико- матроидная характеристика плоских графов , названная в честь Хасслера Уитни . Он утверждает, что граф 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 и наоборот.

Можно определить двойственные графы графов, встроенных в неплоские поверхности, такие как тор, но эти двойственные графы обычно не имеют соответствия между разрезами, циклами и остовными деревьями, требуемыми критерием Уитни.