Гомоморфизм графов с использованием Python

Question

Моя идея состоит в том, чтобы написать программу на Python, которая будет принимать в качестве аргументов два конечных простых неориентированных графа, например G, H, и возвращать число hom(G,H) гомоморфизмов графов из G в H.

Примеры: Если G = K_1 (граф с одной вершиной), то hom(G,H) равно количеству вершин в H. Если G =K_2 (или, что то же самое, P_2), то hom(G,H) = двукратное количество ребер H.

Кто-нибудь может мне помочь? Спасибо.

Answer 1

В общем, NP-сложно. Если граф G имеет n вершин, а граф H имеет m вершин, наивный подход может заключаться в проверке всех n ^ m возможных функций присваивания между двумя графами.

Это эквивалентно выполнению m цепочечных циклов по .

Я знаю два способа сделать это на Python:

1) Вы можете создать m списков [1 ... n] и использовать чтобы получить декартово произведение между этими списками.

2) Вы можете сгенерировать строку с этим кодом связанных циклов и выполнить ее на python с встроенная функция.

Если вы используете первое решение, оно хорошо распараллеливается. Так что вы можете немного ускориться.