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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

История[править | править код]

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

Предварительные определения[править | править код]

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

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

Формулировка[править | править код]

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

Вариации и обобщения[править | править код]

Примечания[править | править код]

Ссылки[править | править код]