577
правок
Изменения
Новая страница: «{{Задача |definition=Определить, является ли граф планарным, и, если да, произвести его плоскую ...»
{{Задача
|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.
}}
Существует [[Теорема Понтрягина-Куратовского|теорема Понтрягина-Куратовского]], которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.
Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.
|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.
}}
Существует [[Теорема Понтрягина-Куратовского|теорема Понтрягина-Куратовского]], которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.
Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.
