Теорема Понтрягина — Куратовского

Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа. Имеет эквивалентаную формулировку на языке миноров, так называемою теорему Вагнера.

Теорема утверждает, что графы K5 (полный граф на 5 вершинах) и K3,3 (полный двудольный граф имеющий по 3 вершины в каждой доле) являются единственными минимальными непланарными графами.

ИсторияПравить

Была доказана в 1930 году польским математиком Казимиром Куратовским[1] и в 1927 году советским математиком Львом Семёновичем Понтрягиным, который не опубликовал своё доказательство.

Предварительные определенияПравить

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

Граф   называется подразбиением графа  , если   можно получить из   добавлением вершин на его рёбра.

ФормулировкаПравить

Граф планарен тогда и только тогда, когда он не содержит подразбиениий полного графа с пятью вершинами (K5) и полного двудольного графа с тремя вершинами в каждой доле (K3,3).

Вариации и обобщенияПравить

ПримечанияПравить

СсылкиПравить