Lexikografický produkt grafů

Lexikografický produkt nebo superpozice grafů je konstrukce grafu daného dvěma. Jsou-li okrajové vazby ve dvou grafech řádové vztahy , pak okrajové spojení v jejich lexikografickém produktu je odpovídající lexikografické pořadí — odtud název.

Lexikografickým dílem se poprvé zabýval Felix Hausdorff [1] .

Definice

$G\cdot H$ grafy G a H je graf takový, že

Množina vrcholů grafu je ; to znamená přímý součin vrcholových sad grafů a . $G\cdot H$ $V(G)\times V(H)$ $G$ $H$
Libovolné dva vrcholy ( u , v ) a ( x , y ) sousedí v právě tehdy a jen tehdy, když buď u sousedí s x v G nebo av sousedí s y v H . $G\cdot H$ $u=x$

Vlastnosti

Lexikografický produkt obecně není komutativní : . Splňuje však disjunktivní unijní distributivní zákon : . $G\cdot H\neq H\cdot G$ $(A+B)\cdot C=A\cdot C+B\cdot C$

Pro sčítání se provádí následující: . $\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$

Číslo nezávislosti lexikografického produktu lze snadno vypočítat z jeho faktorů [2] : $\alpha (G\cdot H)=\alpha (G)\alpha (H)$ .

Klique číslo lexikografického produktu je multiplikativní: $\omega (G\cdot H)=\omega (G)\omega (H)$ .

Barevné číslo lexikografického produktu se rovná b - násobnému chromatickému číslu grafu G pro b , rovnému chromatickému číslu H : $\chi (G\cdot H)=\chi _{b}(G)$ , kde . $b=\chi (H)$

Lexikografický součin dvou grafů je dokonalým grafem právě tehdy, když jsou oba faktory dokonalé [3] .

Úkol rozpoznat, zda je graf lexikografickým produktem, je co do složitosti ekvivalentní problému izomorfismu grafu . [čtyři]

Poznámky

↑ Felix Hausdorff . Grundzuge der Mengenlehre. - Lipsko, 1914. Překlad: F. Hausdorff. Teorie množin. - Moskva, Leningrad: Spojené vědeckotechnické nakladatelství SSSR NKTP. Hlavní vydání technické a teoretické literatury., 1937.
↑ Geller D., Stahl S. Chromatické číslo a další funkce lexikografického produktu // Journal of Combinatorial Theory . - 1975. - T. 19 . — S. 87–95 . - doi : 10.1016/0095-8956(75)90076-3 .
↑ Ravindra G., Parthasarathy KR Perfektní produktové grafy // Diskrétní matematika. - 1977. - T. 20 , no. 2 . — S. 177–186 . - doi : 10.1016/0012-365X(77)90056-5 .
↑ Feigenbaum J., Schäffer AA Rozpoznávání složených grafů je ekvivalentní testování izomorfismu grafu // SIAM Journal on Computing . - 1986. - T. 15 , no. 2 . — S. 619–627 . - doi : 10.1137/0215045 .

Literatura

Wilfried Imrich, Sandi Klavzar. Produktové grafy: Struktura a rozpoznávání. - Wiley, 2000. - ISBN 0-471-37039-8 .

Odkazy

Weisstein, Eric W. Graf Lexikografický produkt (anglicky) na webových stránkách Wolfram MathWorld .