Iloczyn modułowy grafów
W teorii grafów iloczynem modułowym grafów G i H jest graf utworzony przez połączenie G i H , który ma zastosowania do izomorfizmu podgrafów . Jest to jeden z kilku różnych rodzajów produktów grafowych , które zostały zbadane, na ogół przy użyciu tego samego zestawu wierzchołków (iloczyn kartezjański zbiorów wierzchołków dwóch grafów G i H ), ale z różnymi zasadami określania, które krawędzie mają zostać uwzględnione.
Definicja
Zbiór wierzchołków iloczynu modułowego G i H to iloczyn kartezjański V ( G ) × V ( H ). Dowolne dwa wierzchołki ( u , v ) i ( u' , v' ) sąsiadują w iloczynie modułowym G i H wtedy i tylko wtedy, gdy u jest różne od u' , v jest różne od v' oraz albo
- u sąsiaduje z u' i v sąsiaduje z v ' lub
- u nie sąsiaduje z u' i v nie sąsiaduje z v' .
Zastosowanie do izomorfizmu podgrafowego
Kliki na grafie iloczynu modułowego odpowiadają izomorfizmom indukowanych podgrafów G i H . Dlatego modułowy graf produktu może być użyty do zredukowania problemów indukowanego izomorfizmu podgrafu do problemów znajdowania klik na grafach. W szczególności maksymalny wspólny indukowany podwykres zarówno G , jak i H odpowiada maksymalnej kliki w ich produkcie modułowym. Chociaż problemy ze znalezieniem największych wspólnych podgrafów indukowanych i znalezieniem maksymalnych klik są oba NP-zupełna , ta redukcja pozwala na zastosowanie algorytmów wyszukiwania klik do wspólnego problemu podgrafów.
- Barrow, H.; Burstall, R. (1976), „Izomorfizm subgrafu, dopasowywanie struktur relacyjnych i maksymalne kliki”, Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190 (76) 90049-1 .
- Levi, G. (1973), „Uwaga na temat wyprowadzania maksymalnych wspólnych podwykresów dwóch grafów skierowanych lub nieskierowanych”, Calcolo , 9 (4): 341–352, doi : 10.1007 / BF02575586 .
- Vizing, VG (1974), „Redukcja problemu izomorfizmu i izomorficznego wejścia do zadania znalezienia niegęstości wykresu”, Proc. 3. Ogólnounijna Konf. Problemy Cybernetyki Teoretycznej , s. 124 .