Учитывая два графика G1 и G2 в одном и том же наборе узлов V, я хочу, чтобы максимальный общий подграф сохранял маркировку узлов.Максимальное общее обозначение подграфа
Я знаю, что общая проблема MCS - NP-Hard, все еще это с этим ограничением? Существует ли конкретный алгоритм для этого случая?
Благодаря
Это не совсем ясно для меня, что проблема именно. В частности, что означает «на одном наборе узлов»?
Но: если общая проблема NP-hard (что, в зависимости от того, что проблема в точности, она может быть или не быть), тогда проблема, которая включает метки, также должна быть NP-hard, потому что мы можем уменьшить исходную задачу (без меток) к проблеме с метками, просто давая каждому узлу в G1 и G2 одну и ту же метку.
Если вы хотите получить более четкий ответ, вы должны определить ваш вопрос более точно:
«Тот же набор узлов» означает, что два графика имеют одни и те же узлы. Узел A в G1 - это узел A в G2, узел B в G1 - это узел B в G2 и т. Д. – imabug
Извините, но если 'G1 = (V, E1)' и 'G2 = (V, E2)', не является MCS просто 'GM = (V, EI)' где 'EI' является пересечением' E1' и 'E2'? Я имею в виду, что причина MCS - NP-Hard - из-за проблемы изоморфизма. Если у вас уже есть соответствие вершин, проблем больше нет. – beaker
Нет, это не так. Возьмем, к примеру: G1 1-2 1-3 G2 1-2 1-3 2-3 Пересечение будет 1-2 1-3 Но это не MCS (в своем сильном определении) – imabug
Почему бы и нет? Это подграф G1, и он является подграфом G2, и он не может быть больше, потому что он уже является всем G1. – Hoopje