Lexikografisk produkt av grafer

Den lexikografiska produkten eller överlagringen av grafer är konstruktionen av en graf som ges två. Om kantlänkarna i två grafer är ordningsrelationer , är kantlänken i deras lexikografiska produkt motsvarande lexikografiska ordning — därav namnet.

Det lexikografiska arbetet studerades först av Felix Hausdorff [1] .

Definition

$G\cdot H$ graferna G och H är en graf sådan att

Uppsättningen av hörn i grafen är ; det vill säga den direkta produkten av vertexuppsättningarna av graferna och . $G\cdot H$ $V(G)\ gånger V(H)$ $G$ $H$
Alla två hörn ( u , v ) och ( x , y ) är intilliggande i om och endast om antingen u är intill x i G eller och v är intill y i H. $G\cdot H$ $u=x$

Egenskaper

Den lexikografiska produkten är i allmänhet inte kommutativ : . Den uppfyller emellertid den disjunktiva fackliga fördelningslagen : . $G\cdot H\neq H\cdot G$ $(A+B)\cdot C=A\cdot C+B\cdot C$

För tillägg utförs följande: . $\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$

Oberoendetalet för en lexikografisk produkt kan enkelt beräknas utifrån dess faktorer [2] : $\alpha (G\cdot H)=\alpha (G)\alpha (H)$ .

Klicknumret för en lexikografisk produkt är multiplikativt: $\omega (G\cdot H)=\omega (G)\omega (H)$ .

Det kromatiska numret för den lexikografiska produkten är lika med det b -faldiga kromatiska talet på grafen G för b , lika med det kromatiska talet för H : $\chi (G\cdot H)=\chi _{b}(G)$ , var . $b=\chi (H)$

Den lexikografiska produkten av två grafer är en perfekt graf om och endast om båda faktorerna är perfekta [3] .

Uppgiften att känna igen om en graf är en lexikografisk produkt är likvärdig i komplexitet med grafisomorfismproblemet . [fyra]

Anteckningar

↑ Felix Hausdorff . Grundzuge der Mengenlehre. - Leipzig, 1914. Översättning: F. Hausdorff. Mängdlära. - Moskva, Leningrad: United Scientific and Technical Publishing House of the USSR NKTP. Huvudupplagan av teknisk och teoretisk litteratur, 1937.
↑ Geller D., Stahl S. Den lexikografiska produktens kromatiska tal och andra funktioner // Journal of Combinatorial Theory . - 1975. - T. 19 . — S. 87–95 . - doi : 10.1016/0095-8956(75)90076-3 .
↑ Ravindra G., Parthasarathy KR Perfekta produktgrafer // Diskret matematik. - 1977. - T. 20 , nr. 2 . — S. 177–186 . - doi : 10.1016/0012-365X(77)90056-5 .
↑ Feigenbaum J., Schäffer AA Att känna igen sammansatta grafer är likvärdigt med att testa grafisomorfism // SIAM Journal on Computing . - 1986. - T. 15 , nr. 2 . — S. 619–627 . - doi : 10.1137/0215045 .

Litteratur

Wilfried Imrich, Sandi Klavzar. Produktdiagram: Struktur och erkännande. - Wiley, 2000. - ISBN 0-471-37039-8 .

Länkar

Weisstein, Eric W. Graph Lexicographic Product (engelska) på Wolfram MathWorlds webbplats .