Kaavioiden tensoritulo

Graafeiden ja tensoritulo on graafi , jonka kärkijoukko on karteesinen tulo , ja eri pisteet ja ovat vierekkäisiä , jos ja vain jos on vieressä ja on vieressä . $G\ kertaa H$ $G$ $H$ ${\näyttötyyli V(G)\times V(H)}$ ${\näyttötyyli (u,u')}$ ${\näyttötyyli (v, v')}$ $G\ kertaa H$ $u$ $v$ $u'$ $v'$

Muut otsikot

Tensorituloa kutsutaan myös suoraksi tuotteeksi , kategoriatuotteeksi , relaatiotuotteeksi , Kronecker-tuotteeksi , heikkoksi suoratuotteeksi tai konjunktioksi . Alfred North Whitehead ja Bertrand Russell Principia Mathematicassa [ 1 ] esittelivät tensoritulon binäärirelaatiooperaationa. Graafeiden tensoritulo vastaa myös näiden graafien vierekkäisyysmatriisien Kronecker -tuloa [2] .

Merkintätapaa käytetään joskus viittaamaan toiseen konstruktiin, joka tunnetaan graafien suorana tulona , mutta se tarkoittaa yleisemmin tensorituloa. Ristisymboli näyttää visuaalisesti kaksi reunaa, jotka johtuvat kahden reunan tensoritulosta [3] . Tätä tuotetta ei pidä sekoittaa kaavioiden vahvaan tuotteeseen . $G\ kertaa H$

Esimerkkejä

Tensoritulo on kaksiosainen graafi , jota kutsutaan kaksiosaisen graafin kaksoispeitekaavioksi . Petersen -graafin kaksinkertainen kaksiosainen graafi on Desargues-graafi . Täydellisen graafin kaksinkertainen kaksiosainen graafi on kruunu , täydellinen kaksiosainen graafi ilman täydellistä vastaavuutta ). ${\displaystyle G\times K_{2))$ $G$ $K_{2}\times G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Täydellisen graafin tensoritulo itsensä kanssa on tornin graafin komplementti . Sen kärjet voidaan sijoittaa nelikulmaiseen hilaan siten, että jokainen kärki on kaikkien muiden kuin samalla rivillä tai sarakkeessa olevien kärkien vieressä. $n\ kertaa n$

Ominaisuudet

Tensoritulo on kategoriateoreettinen tulo graafien ja homomorfismien luokassa , eli homomorfismi in vastaa homomorfismiparia in ja in . Erityisesti graafi myöntää homomorfismin silloin ja vain, jos se myöntää homomorfismin molemmille tekijöille. $G\ kertaa H$ $G$ $H$ $minä$ $G\ kertaa H$

Toisaalta homomorfismien pari ja antaa homomorfismi: $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 }}~,

toisaalta homomorfismia voidaan soveltaa projektiohomomorfismiin: $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}}~,

mikä antaa homomorfismeja ja . $G$ $H$

Graafin viereisyysmatriisi on vierekkäisyysmatriisien tensoritulo ja . $G\ kertaa H$ $G$ $H$

Jos graafi voidaan esittää tensoritulona, esitys ei välttämättä ole ainutlaatuinen, vaan jokaisessa esityksessä on sama määrä redusoitumattomia tekijöitä. Wilfried Imrich [4] antoi polynomin aika-algoritmin graafien tensoritulon tunnistamiseksi ja minkä tahansa sellaisen graafin hajoamisen löytämiseksi.

Jos jompikumpi tai on kaksiosainen , niin niiden tensoritulo on myös kaksiosainen. Graafi on yhdistetty silloin ja vain, jos molemmat tekijät ovat yhteydessä toisiinsa ja ainakin yksi tekijä ei ole kaksiosainen [5] . Erityisesti graafin kaksiosaisen graafin kaksoispeitto on yhdistetty silloin ja vain, jos se on yhdistetty eikä kaksiosainen. $G$ $H$ $G\ kertaa H$ $G$ $G$

Hedetniemen arvelu antaa kaavan tensoritulon kromaattiselle luvulle .

Katso myös

Kirjallisuus

Gena Hahn, Gert Sabidussi. Graafisymmetria: algebralliset menetelmät ja sovellukset . - Springer, 1997. - T. 497. - S. 116. - (NATO Advanced Science Institutes -sarja). - ISBN 978-0-7923-4668-5 .
Imrich W. Kardintulograafien faktorointi polynomiajassa // Diskreetti matematiikka . - 1998. - T. 192 . — S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Tuotekaaviot: rakenne ja tunnistus. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. Graafeiden Kronecker-tulo // 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.

Linkit

Nicholas Bray. Graafinen kategorinen tuote Wolfram MathWorld -verkkosivustolla .