Grafikonok lexikográfiai terméke

A gráfok lexikográfiai szorzata vagy szuperpozíciója egy gráf felépítése kettővel. Ha két gráfban az élhivatkozások sorrendi relációk , akkor a lexikográfiai termékükben az élhivatkozás a megfelelő lexikográfiai sorrend – innen a név.

A lexikográfiai munkával először Felix Hausdorff [1] foglalkozott .

Definíció

$G\cdot H$ grafikonok G és H egy olyan gráf, hogy

A gráf csúcsainak halmaza ; vagyis a gráfok és a csúcshalmazok direkt szorzata . $G\cdot H$ $V(G)\times V(H)$ $G$ $H$
Bármely két csúcs ( u , v ) és ( x , y ) akkor és csak akkor szomszédos a - ban , ha u szomszédos x - vel G - ben , vagy és v szomszédos y - vel H - ban . $G\cdot H$ $u=x$

Tulajdonságok

A lexikográfiai termék általában nem kommutatív : . Ez azonban kielégíti a diszjunktív unió elosztási törvényt : . $G\cdot H\neq H\cdot G$ $(A+B)\cdot C=A\cdot C+B\cdot C$

A kiegészítéseknél a következőket kell végrehajtani: . $\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$

Egy lexikográfiai termék függetlenségi száma könnyen kiszámítható tényezőiből [2] : $\alpha (G\cdot H)=\alpha (G)\alpha (H)$ .

Egy lexikográfiai termék klikkszáma multiplikatív: $\omega (G\cdot H)=\omega (G)\omega (H)$ .

A lexikográfiai termék kromatikus száma egyenlő a G gráf b - szeres kromatikus számával , egyenlő H kromatikus számával : $\chi (G\cdot H)=\chi _{b}(G)$ , hol . $b=\chi (H)$

Két gráf lexikográfiai szorzata akkor és csak akkor tökéletes gráf , ha mindkét tényező tökéletes [3] .

Az a feladat, hogy felismerjük, hogy egy gráf lexikográfiai termék-e, összetettségében egyenértékű a gráfizomorfizmus problémájával . [négy]

Jegyzetek

↑ Felix Hausdorff . Grundzuge der Mengenlehre. - Lipcse, 1914. Fordítás: F. Hausdorff. Halmazelmélet. - Moszkva, Leningrád: A Szovjetunió NKTP Egyesült Tudományos és Műszaki Kiadója. Műszaki és elméleti irodalom főkiadása., 1937.
↑ Geller D., Stahl S. A lexikográfiai termék kromatikus száma és egyéb funkciói // Journal of Combinatorial Theory . - 1975. - T. 19 . – S. 87–95 . - doi : 10.1016/0095-8956(75)90076-3 .
↑ Ravindra G., Parthasarathy KR Perfect product graphs // Discrete Mathematics. - 1977. - T. 20 , sz. 2 . – S. 177–186 . - doi : 10.1016/0012-365X(77)90056-5 .
↑ Feigenbaum J., Schäffer AA Az összetett gráfok felismerése egyenértékű a gráfizomorfizmus tesztelésével // SIAM Journal on Computing . - 1986. - T. 15 , sz. 2 . – S. 619–627 . - doi : 10.1137/0215045 .

Irodalom

Wilfried Imrich, Sandi Klavzar. Termékgrafikonok: Struktúra és felismerés. - Wiley, 2000. - ISBN 0-471-37039-8 .

Linkek

Weisstein, Eric W. Graph Lexicographic Product (angol nyelven) a Wolfram MathWorld webhelyén .