Планарный граф

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

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

Содержание 1 Критерий непланарности: 2 Теорема Понтрягина-Куратовского 3 См. также 4 Ссылки

[править] Критерий непланарности:

• достаточное условие — если граф содержит двудольный подграф K_3,3 или полный подграф K₅, то он является не планарным;
• необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин степень которых больше 3 или больше 5 вершин степени больше 2.

[править] Теорема Понтрягина-Куратовского

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K₅ или K_3,3.

• Вариант

Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K₅ или K_3,3.

[править] См. также

• Словарь терминов теории графов
• Теория графов

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

• А. Ю. Ольшанский. Плоские графы, СОЖ, 1996, No 11, с. 117—122.
• Ф. Харари. Теория графов. М.: «Мир». 1973
• Алгоритмы и краткие описания и программ на C++
• ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, визуализация графов, апплеты

Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.