Покажите, что язык планарных графов (граф задается списком ребер или матрицей смежности) принадлежит классу $%co-NP$%(дополнение к классу $%NP$%)

задан 1 Май '16 17:59

10|600 символов нужно символов осталось
1

Нужно использовать теорему Понтрягина - Куратовского. Если граф не планарен, то в нём имеется (геометрический) подграф, изоморфный $%K_5$% или $%K_{3,3}$%. Такое свойство распознаётся недетерминистским алгоритмом за полиномиальное время. А именно, нужно угадать 5 или 6 вершин, которые соединены между собой цепями, проходящими через попарно различные вершины, чтобы при этом возникал подграф одного из двух типов. Ясно, что если такая конфигурация есть, то её можно предъявить, проверяя за полиномиальное время (видимо, даже за линейное), что она подходит.

Тем самым, язык не планарных графов принадлежит NP, и потому язык планарных графов принадлежит co-NP.

Если я правильно понимаю, то при планарности графа, существует его дискретная укладка на плоскости, где все рёбра реализуются в виде отрезков (есть такая теорема). По-видимому, тут тоже есть подходящий алгоритм (хотя какие-то детали обосновывать надо), и должен получиться язык, принадлежащий NP.

ссылка

отвечен 1 Май '16 20:47

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×475
×198
×123

задан
1 Май '16 17:59

показан
512 раз

обновлен
1 Май '16 20:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru