|
Покажите, что язык планарных графов (граф задается списком ребер или матрицей смежности) принадлежит классу $%co-NP$%(дополнение к классу $%NP$%) задан 1 Май '16 17:59 
Uchenitsa |
|
Нужно использовать теорему Понтрягина - Куратовского. Если граф не планарен, то в нём имеется (геометрический) подграф, изоморфный $%K_5$% или $%K_{3,3}$%. Такое свойство распознаётся недетерминистским алгоритмом за полиномиальное время. А именно, нужно угадать 5 или 6 вершин, которые соединены между собой цепями, проходящими через попарно различные вершины, чтобы при этом возникал подграф одного из двух типов. Ясно, что если такая конфигурация есть, то её можно предъявить, проверяя за полиномиальное время (видимо, даже за линейное), что она подходит. Тем самым, язык не планарных графов принадлежит NP, и потому язык планарных графов принадлежит co-NP. Если я правильно понимаю, то при планарности графа, существует его дискретная укладка на плоскости, где все рёбра реализуются в виде отрезков (есть такая теорема). По-видимому, тут тоже есть подходящий алгоритм (хотя какие-то детали обосновывать надо), и должен получиться язык, принадлежащий NP. отвечен 1 Май '16 20:47 
falcao |