Sergey
04.05.2004 21:33
Занимался курсовой работой, и в ее ходе возник вопрос: определение планарности графа - NP-полная задача или нет? Может существует простое доказательство np-полности или, наоборот, простой алгоритм проверки? Кто интересовался подобными вещами, подскажите плз...
Денис Назаров
04.05.2004 23:34
Есть очень интересная теорема:
Теорема Понтрягина-Куратовского Граф планарен тогда и только тогда, когда оне не содержит в качестве частей графы K(5) и K(3,3) (быть может с дополнительными вершинами степени 2)
Однако пользоваться такой формулировкой для определения планарности графа затруднительно. Более логично использовать алгоритм "гамма" (его можно найти в книжке В.И.Рубленицкий "Введение в мир алгоритмов"). Естественно, это не NP-полная задача.
boris
06.05.2004 09:06
А кто-нибудь писал определение планарности графа?
