Tensorprodukt av grafer

Tensorprodukten av grafer och är en graf vars uppsättning av hörn är en kartesisk produkt , och olika hörn och är angränsande om och endast om ligger intill och gränsar till . $G\ gånger H$ $G$ $H$ $V(G)\ gånger V(H)$ $(u,u')$ $(v,v')$ $G\ gånger H$ $u$ $v$ $u'$ $v'$

Andra titlar

Tensorprodukten kallas även direktprodukt , kategoriprodukt , relationsprodukt , Kroneckerprodukt , svag direktprodukt eller konjunktion . Alfred North Whitehead och Bertrand Russell i Principia Mathematica [1] introducerade tensorprodukten som en binär relationsoperation. Tensorprodukten av grafer är också ekvivalent med Kronecker-produkten av närliggande matriser för dessa grafer [2] .

Notationen används ibland för att hänvisa till en annan konstruktion som är känd som den direkta produkten av grafer , men betecknar mer vanligt tensorprodukten. Korssymbolen visar visuellt två kanter som härrör från tensorprodukten av två kanter [3] . Denna produkt ska inte förväxlas med den starka produkten av grafer . $G\ gånger H$

Exempel

Tensorprodukten är en tvådelad graf , som kallas den tvådelade grafens dubbla täckningsgraf . Den dubbeltäckande tvådelade grafen i Petersen -grafen är Desargues-grafen . Den dubbla täckande tvådelade grafen för en komplett graf är kronan , en komplett tvådelad graf utan en perfekt matchning ). ${\displaystyle G\times K_{2))$ $G$ $K_{2}\ gånger G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Tensorprodukten av en komplett graf med sig själv är komplementet till ett torns graf . Dess hörn kan placeras i ett kvadratiskt gitter så att varje vertex ligger intill alla hörn som inte är i samma rad eller kolumn. $n\ gånger n$

Egenskaper

En tensorprodukt är en kategoriteoretisk produkt i kategorin grafer och homomorfismer , det vill säga en homomorfism i motsvarar ett par homomorfismer i och i . I synnerhet medger en graf en homomorfism till om och endast om den medger en homomorfism för båda faktorerna. $G\ gånger H$ $G$ $H$ $jag$ $G\ gånger H$

Å ena sidan, paret homomorfismer och ger en homomorfism: $f_{G}:I\to G$ $f_{H}:I\to H$

{\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases }}~,

å andra sidan kan homomorfism tillämpas på projektionshomomorfismer: $f\colon I\to G\times H$

{\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \ qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{G}((u,u'))=u'\end{cases}}~,

vilket ger homomorfismer till och till . $G$ $H$

Närliggande matris i en graf är tensorprodukten av närliggande matriser och . $G\ gånger H$ $G$ $H$

Om en graf kan representeras som en tensorprodukt, kanske representationen inte är unik, men varje representation har samma antal irreducerbara faktorer. Wilfried Imrich [4] gav en polynomisk tidsalgoritm för att känna igen tensorprodukten av grafer och hitta sönderdelningen av en sådan graf.

Om antingen , eller är bipartit , är deras tensorprodukt också bipartit. Grafen är kopplad om och endast om båda faktorerna är sammankopplade och minst en faktor inte är tvådelad [5] . I synnerhet är en dubbel täckning av en tvådelad graf av en graf kopplad om och endast om den är sammankopplad och inte tvådelad. $G$ $H$ $G\ gånger H$ $G$ $G$

Hedetniemis gissning ger en formel för det kromatiska talet för en tensorprodukt.

Se även

Anteckningar

↑ Whitehead, Russell, 1912 .
↑ Weichsel, 1962 .
↑ Hahn, Sabidussi, 1997 .
↑ Imrich, 1998 .
↑ Imrich, Klavžar, 2000 , sid. Sats 5.29.

Litteratur

Gena Hahn, Gert Sabidussi. Grafsymmetri: algebraiska metoder och tillämpningar . - Springer, 1997. - T. 497. - S. 116. - (NATO Advanced Science Institutes Series). - ISBN 978-0-7923-4668-5 .
Imrich W. Factoring kardinalproduktgrafer i polynomtid // Diskret matematik . - 1998. - T. 192 . — S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Produktdiagram: Struktur och erkännande. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. Kronecker-produkten av grafer // Proceedings of the American Mathematical Society . - 1962. - T. 13 , nr. 1 . — s. 47–52 . - doi : 10.2307/2033769 . — .
Whitehead A.N., Russell B. Principia Mathematica . — Cambridge University Press, 1912.

Länkar

Nicholas Bray. Grafisk kategorisk produkt på Wolfram MathWorlds webbplats .