Modulární produkt grafů - Modular product of graphs
v teorie grafů, modulární produkt grafů G a H je graf vytvořený kombinací G a H který má aplikace podgraf izomorfismus Je to jeden z několika různých druhů grafové produkty které byly studovány, obvykle za použití stejné množiny vrcholů (kartézský součin množin vrcholů dvou grafů G a H), ale s různými pravidly pro určování, které hrany mají být zahrnuty.
Definice
Vrcholová sada modulárního součinu G a H je kartézský součin PROTI(G) × PROTI(HJakékoli dva vrcholy (u, proti) a (ty , proti' ) sousedí v modulárním produktu produktu G a H kdyby a jen kdyby u je odlišný od ty , proti je odlišný od proti' , a buď
- u sousedí s ty a proti sousedí s proti' , nebo
- u nesousedí s ty a proti nesousedí s proti' .
Aplikace na podgraf izomorfismus
Kliky v modulárním grafu produktu odpovídají izomorfismy z indukované podgrafy z G a H. Proto lze modulární produktový graf použít ke snížení problémů izomorfismu indukovaného podgrafu na problémy s nalezením kliky v grafech. Konkrétně maximální společný indukovaný podgraf oba G a H odpovídá maximální klika v jejich modulárním produktu. I když problémy s nalezením největších běžných indukovaných podgrafů a hledání maximálních klik jsou obojí NP-kompletní, toto snížení umožňuje algoritmy pro vyhledání klik aplikovat na společný problém podgrafu.
Reference
- Barrow, H .; Burstall, R. (1976), „Subgraph isomorphism, matching relační struktury a maximální kliky“, Dopisy o zpracování informací, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
- Levi, G. (1973), "Poznámka k odvození maximálních společných podgrafů dvou směrovaných nebo neorientovaných grafů", Calcolo, 9 (4): 341–352, doi:10.1007 / BF02575586.
- Vizing, V. G. (1974), „Redukce problému izomorfismu a izomorfního vstupu do úkolu hledání hustoty grafu“, Proc. 3. konfederace všech unií Problémy teoretické kybernetiky, str. 124.