Расширение двудольного графа максимума, соответствующего

Question

Предположим, что есть два графика, как это:

Мы стремимся найти соответствующие соответствия между двумя graph.And теперь мы используем метод для вычисления подобия двух узлов между двумя графиками. w (A, 1) означает сходство узла A от левого графа между узлом 1 от правого графа. Тогда мы можем иметь таблицу, как это:

Наша цель состоит в вычислении максимального соответствия веса всех этих узлов. И мы можем использовать алгоритм Kuhn-Munkras для решения этой проблемы.

Но теперь вопрос заключается в том, что если мы добавим сходство между ребрами из двух графиков, как мы можем вычислить максимальное соответствие веса. Это означает, что таблица стать этим:

АА означает узел А, АВ означает край от А до В. Ограничения, что если конечный результат в том, что узел А соответствует узлу 1, край AB должен соответствовать 12 или 13. Можно ли использовать такой алгоритм, как Kuhn-Munkras, для решения этой проблемы? Если нет, как мы можем найти максимальное соответствие веса в полиномиальное время?

Answer 1

Предположим, что мы хотим знать, являются ли два графика изоморфными, например. два в вашем примере.

В первом графике мы имеем края AC и CB, а во втором графике мы кромки 13 и 32.

Мы можем установить весовую матрицу таким образом, что существует высокая награда для отображения любого края в сначала до края во втором.

То есть AC-> 13 и AC-> 32 и CB-> 13 и CB-> 32 будут иметь вес 1, тогда как все остальные соответствия имеют нулевой вес.

Существует изоморфизм между графиками тогда и только тогда, когда существует максимальное соответствие веса с весом, равным числу ребер.

Поэтому ваша проблема по крайней мере такая же сложная, как изоморфизм графа, поэтому маловероятно, что алгоритм Куна может быть эффективно распространен на этот случай.