Stark produkt av grafer

Den starka produkten av graferna G och H är en graf sådan att [1] : $G\boxtimes H$

uppsättningen av hörn är en direkt produkt $G\boxtimes H$ $V(G)\ gånger V(H)$
distinkta hörn ( u,u' ) och ( v,v' ) är förbundna med en kant i if och endast if $G\boxtimes H$
- u = v och u' ligger intill v' , eller
- u' = v' och u ligger intill v , eller
- u ligger intill v och u' ligger intill v' .

Den starka produkten är föreningen av den direkta produkten och tensorprodukten .

Den starka produkten kallas även för normalprodukten eller OCH - produkten . Produkten introducerades först av Sabidussi 1960 [2] . Den starka produkten står i kontrast till den svaga produkten , men de två produkterna skiljer sig bara åt när de tillämpas på oändliga grafer.

Till exempel är grafen över kungens drag , en graf där hörnen är schackbrädets celler och kanterna representerar kungens möjliga drag, en stark produkt av två banor [3] .

Försiktighet bör iakttas när termen förekommer i litteraturen, eftersom den starka produkten också används för att referera till tensorprodukten [4] .

Se även

Anteckningar

↑ Imrich, Klavžar, Rall, 2008 .
↑ Sabidussi, 1960 , sid. 446–457.
↑ Berend, Korach, Zucker, 2005 , sid. 335–341.
↑ Lovász, 1979 , sid. 2.

Litteratur

Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Grafer och deras kartesiska produkt. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
Sabidussi, G. Grafmultiplikation // Math. Z .. - 1960. - T. 72 . — S. 446–457 . - doi : 10.1007/BF01162967 .
Daniel Berend, Ephraim Korach, Shira Zucker. Två-antifärgning av plana och relaterade grafer // 2005 International Conference on Analysis of Algorithms. - Nancy: Association for Discrete Mathematics & Theoretical Computer Science, 2005. - S. 335–341. — (Diskret matematik och teoretisk datavetenskap).
Laszlo Lovasz. Om Shannon Capacity of a Graph // IEEE-transaktioner på informationsteori. - 1979. - T. IT-25 , nr. 1 . - doi : 10.1109/TIT.1979.1055985 .