Tensorprodukt af grafer

Tensorproduktet af grafer og er en graf, hvis sæt af hjørner er et kartesisk produkt , og forskellige hjørner og er tilstødende, hvis og kun hvis er støder op til og støder op til . $G\ gange H$ $G$ $H$ $V(G)\ gange V(H)$ $(u,u')$ $(v,v')$ $G\ gange H$ $u$ $v$ $u'$ $v'$

Andre titler

Tensorproduktet kaldes også direkte produkt , kategoriprodukt , relationelt produkt , Kronecker-produkt , svagt direkte produkt eller konjunktion . Alfred North Whitehead og Bertrand Russell i Principia Mathematica [1] introducerede tensorproduktet som en binær relationsoperation. Tensorproduktet af grafer er også ækvivalent med Kronecker-produktet af tilstødende matricer af disse grafer [2] .

Notationen bruges nogle gange til at henvise til en anden konstruktion kendt som det direkte produkt af grafer , men betegner mere almindeligt tensorproduktet. Krydssymbolet viser visuelt to kanter, der stammer fra tensorproduktet af to kanter [3] . Dette produkt må ikke forveksles med det stærke produkt af grafer . $G\ gange H$

Eksempler

Tensorproduktet er en todelt graf , som kaldes den todelte grafs dobbelte dækningsgraf . Den dobbeltdækkende todelte graf af Petersen -grafen er Desargues-grafen . Den dobbeltdækkende todelte graf af en komplet graf er kronen , en komplet todelt graf uden en perfekt matchning ). ${\displaystyle G\ gange K_{2))$ $G$ $K_{2}\ gange G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Tensorproduktet af en komplet graf med sig selv er komplementet til et tårns graf . Dens toppunkter kan placeres i et firkantet gitter , således at hvert toppunkt støder op til alle toppunkter, der ikke er i samme række eller kolonne. $n\ gange n$

Egenskaber

Et tensorprodukt er et kategoriteoretisk produkt i kategorien grafer og homomorfier , det vil sige, at en homomorfi i svarer til et par homomorfier i og i . Især en graf indrømmer en homomorfi til hvis og kun hvis den indrømmer en homomorfi for begge faktorer. $G\ gange H$ $G$ $H$ $jeg$ $G\ gange H$

På den ene side, parret af homomorfismer og give en homomorfi: $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 }}~,

på den anden side kan homomorfi anvendes på projektionshomomorfismer: $f\colon I\to G\ gange H$

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

giver således homomorfier til og til . $G$ $H$

Adjacency-matricen af en graf er tensorproduktet af tilstødende matricer og . $G\ gange H$ $G$ $H$

Hvis en graf kan repræsenteres som et tensorprodukt, er repræsentationen muligvis ikke unik, men hver repræsentation har det samme antal irreducerbare faktorer. Wilfried Imrich [4] gav en polynomisk tidsalgoritme til at genkende tensorproduktet af grafer og finde nedbrydningen af enhver sådan graf.

Hvis enten , eller er bipartite , så er deres tensorprodukt også bipartite. Grafen er forbundet, hvis og kun hvis begge faktorer er forbundet, og mindst én faktor ikke er todelt [5] . Især er en dobbelt afdækning af en todelt graf af en graf forbundet, hvis og kun hvis den er forbundet og ikke todelt. $G$ $H$ $G\ gange H$ $G$ $G$

Hedetniemis formodning giver en formel for det kromatiske tal for et tensorprodukt.

Se også

Noter

↑ Whitehead, Russell, 1912 .
↑ Weichsel, 1962 .
↑ Hahn, Sabidussi, 1997 .
↑ Imrich, 1998 .
↑ Imrich, Klavžar, 2000 , s. Sætning 5.29.

Litteratur

Gena Hahn, Gert Sabidussi. Grafsymmetri: algebraiske metoder og anvendelser . - Springer, 1997. - T. 497. - S. 116. - (NATO Advanced Science Institutes Series). - ISBN 978-0-7923-4668-5 .
Imrich W. Faktorisering af kardinalproduktgrafer i polynomisk tid // Diskret matematik . - 1998. - T. 192 . — S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Produktgrafer: Struktur og anerkendelse. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. Kronecker-produktet af grafer // Proceedings of the American Mathematical Society . - 1962. - T. 13 , no. 1 . — s. 47–52 . - doi : 10.2307/2033769 . — .
Whitehead A.N., Russell B. Principia Mathematica . — Cambridge University Press, 1912.