Планарный граф
Материал из Википедии — свободной энциклопедии
Планарный граф - граф, который может быть изображен на плоскости без пересечения ребер.
[править] Критерий непланарности:
- достаточное условие — если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;
- необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин степень которых больше 3 или больше 5 вершин степени больше 2.
[править] Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.
- Вариант
Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.
[править] Ссылки
- А. Ю. Ольшанский. Плоские графы, СОЖ, 1996, No 11, с. 117–122.
- Ф.Харари. Теория графов. М.: "Мир". 1973
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
