Сведение к клике
Подграф изоморфизма
У нас есть графики G_1=(V_1,E_1), G_2=(V_2,E_2).
Вопрос: граф G_1 изоморфен подграфу G_2?
(т. е. существует ли подмножество вершин G_2, V ⊆ V_2 и подмножество ребер G_2, E ⊆ E_2 такое, что |V|=|V_1| и |E|=|E_1| и существует ли однозначный одно сопоставление вершин G_1 в подмножестве вершин V из G_2, f:V_1 -> V, такое, что {u,v} ∈ E_1 <=> { f(u),f(v) } ∈ E)
- Покажите, что проблема изоморфизма подграфа принадлежит NP.
- Покажите, что проблема является NP-полной, сводя проблему к клику. (Подсказка: считайте, что граф G_1 полон)
Я пробовал следующее:
- Недетерминированная машина Тьюринга сначала "угадывает" подмножество узлов V и подмножество ребер E в G_2, а затем проверяет, что |V|=|V_1| и |E|=|E_1| и что существует взаимно-однозначное соответствие f: V_1 -> V такое, что {u,v} ∈ E_1 <=> { f(u), f(v) } ∈ E .
Поскольку существует O(|V_2|^2) разных пар вершин, проверка требует полиномиального времени. Так что проблема принадлежит НП.
- Пусть (G,k) произвольный экземпляр задачи клики, где k - количество вершин клики.
Мы можем построить экземпляр задачи об изоморфизме подграфа за полиномиальное время следующим образом: G_2 - граф на n вершинах.
G_1 - полный граф на k вершинах для некоторого k <= n. Пусть G=G_2. Задача Изоморфизм подграфа имеет решение тогда и только тогда, когда существует полный подграф группы G_2 с k вершинами, т. Е. Если граф G имеет полный подграф с k вершинами.
Таким образом, экземпляр задачи Подграф Изоморфизм имеет решение тогда и только тогда, когда исходный экземпляр проблемы Клика имеет решение.
Следовательно, проблема подграфа изоморфизма является NP-полной.
Не могли бы вы сказать мне, если это правильно или я мог бы что-то улучшить?