Gráfok moduláris szorzata

A matematika, azon belül a gráfelmélet területén a G és H gráfok moduláris szorzata egy gráfszorzás, olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. G és H moduláris szorzata olyan gráf, melyre a következők igazak:

• G és H moduláris szorzatának csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
• két, a moduláris szorzatban található csúcs, (u, v) és (u' , v' ) pontosan akkor szomszédosak, ha
  • u szomszédos u' -vel és v is szomszédos v' -vel, vagy
  • u nem szomszédos u' -vel és v sem szomszédos v' -vel.

Gráfok moduláris szorzata.

A moduláris szorzatgráf klikkjei megfelelnek G és H feszített részgráfjai izomorfizmusainak. Ezért a moduláris szorzatgráf felhasználható egyes feszített részgráf-izomorfizmus problémáknak a gráfokban való klikkek keresésére redukálására. Konkrétabban, G és H maximális közös feszített részgráfja megfelel moduláris szorzatuk maximális elemszámú klikkjének. Bár mindkét probléma NP-teljes, ez a redukció lehetővé teszi a klikk-kereső algoritmusok alkalmazását a közös részgráf-problémára.

Fordítás

• Ez a szócikk részben vagy egészben a Modular product of graphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Barrow, H. & Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters 4 (4): 83–84, DOI 10.1016/0020-0190(76)90049-1.
• Levi, G. (1973), "A note on the derivation of maximal common subgraphs of two directed or undirected graphs", Calcolo 9 (4): 341–352, DOI 10.1007/BF02575586.
• Vizing, V. G. (1974), "Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph", Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics, p. 124.