Gráfok tenzorszorzata

A és gráfok tenzorszorzata egy olyan gráf , amelynek csúcsai egy derékszögű szorzat , és a különböző csúcsok és akkor és csak akkor szomszédosak , ha szomszédos és szomszédos . $G\time H$ $G$ $H$ $V(G)\times V(H)$ $(u,u')$ $(v,v')$ $G\time H$ $u$ $v$ $u'$ $v'$

Egyéb címek

A tenzorszorzatot közvetlen terméknek , kategóriaterméknek , relációs szorzatnak , Kronecker-terméknek , gyenge közvetlen szorzatnak vagy konjunkciónak is nevezik . Alfred North Whitehead és Bertrand Russell a Principia Mathematicában [1] vezette be a tenzorszorzatot bináris relációs műveletként. A gráfok tenzorszorzata is ekvivalens ezen gráfok szomszédsági mátrixainak Kronecker-szorzatával [2] .

A jelölést néha egy másik, a gráfok közvetlen szorzataként ismert konstrukcióra is használják , de gyakrabban a tenzorszorzatot jelöli. A kereszt szimbólum vizuálisan két élt mutat két él tenzorszorzatából [3] . Ezt a terméket nem szabad összetéveszteni a grafikonok erős szorzatával . $G\time H$

Példák

A tenzorszorzat egy kétrészes gráf , amelyet a bipartit gráf kettős fedőgráfjának nevezünk . A Petersen -gráf kettős fedésű bipartit gráfja a Desargues-gráf . A teljes gráf kettős fedésű bipartit gráfja a korona , egy teljes kétrészes gráf tökéletes illeszkedés nélkül ). ${\displaystyle G\times K_{2))$ $G$ $K_{2}\times G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Egy teljes gráf tenzorszorzata önmagával a bástya gráf komplementere . Csúcsai elhelyezhetők egy négyzetrácsban úgy, hogy minden csúcs szomszédos minden olyan csúcshoz, amely nem ugyanabban a sorban vagy oszlopban található. $n\szer n$

Tulajdonságok

A tenzorszorzat egy kategóriaelméleti szorzat a gráfok és homomorfizmusok kategóriájában , vagyis egy in homomorfizmus a -ben és -ben lévő homomorfizmusok párjának felel meg . Egy gráf akkor és csak akkor ismer el homomorfizmust , ha mindkét tényező homomorfizmusát elismeri. $G\time H$ $G$ $H$ $én$ $G\time H$

Egyrészt a homomorfizmus és ad homomorfizmus párja: $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 }}~,

másrészt a homomorfizmus alkalmazható a projekciós homomorfizmusokra: $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}}~,

így homomorfizmusokat adva és -nek . $G$ $H$

A gráf szomszédsági mátrixa a szomszédsági mátrixok és a tenzorszorzata . $G\time H$ $G$ $H$

Ha egy gráf tenzorszorzatként ábrázolható, akkor lehet, hogy az ábrázolás nem egyedi, de minden reprezentációnak ugyanannyi irreducibilis tényezője van. Wilfried Imrich [4] adott egy polinomiális idő algoritmust a gráfok tenzorszorzatának felismerésére és bármely ilyen gráf dekompozíciójának megtalálására.

Ha a , vagy kétrészes , akkor a tenzorszorzatuk is bipartit . A gráf akkor és csak akkor kapcsolódik össze, ha mindkét tényező összefügg, és legalább az egyik tényező nem kétoldalú [5] . Konkrétan egy gráf kétrészes gráfjának kettős lefedése akkor és csak akkor kapcsolódik, ha össze van kötve, és nem bipartit. $G$ $H$ $G\time H$ $G$ $G$

Hedetniemi sejtése egy tenzorszorzat kromatikus számának képletét adja meg .

Lásd még

Jegyzetek

↑ Whitehead, Russell, 1912 .
↑ Weichsel, 1962 .
↑ Hahn, Sabidussi, 1997 .
↑ Imrich, 1998 .
↑ Imrich, Klavžar, 2000 , p. 5.29. tétel.

Irodalom

Gena Hahn, Gert Sabidussi. Gráfszimmetria: algebrai módszerek és alkalmazások . - Springer, 1997. - T. 497. - S. 116. - (NATO Advanced Science Institutes Series). - ISBN 978-0-7923-4668-5 .
Imrich W. Kardinális szorzatgráfok faktorálása polinomiális időben // Discrete Mathematics . - 1998. - T. 192 . – S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Termékgrafikonok: Struktúra és felismerés. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. A gráfok Kronecker-szorzata // Proceedings of the American Mathematical Society . - 1962. - T. 13 , sz. 1 . – 47–52 . - doi : 10.2307/2033769 . — .
Whitehead A.N., Russell B. Principia Mathematica . – Cambridge University Press, 1912.

Linkek

Nicholas Bray. Grafikon kategorikus termék a Wolfram MathWorld webhelyen .