Tenzorový součin grafů

Tenzorový součin grafů a je graf , jehož množina vrcholů je kartézský součin a různé vrcholy a jsou sousedící právě tehdy, když sousedí a sousedí s . $G\krát H$ $G$ $H$ $V(G)\times V(H)$ $(u,u')$ $(v,v')$ $G\krát H$ $u$ $proti$ $u'$ $proti'$

Další názvy

Tenzorový součin se také nazývá přímý součin , součin kategorie , relační součin , Kroneckerův součin , slabý přímý součin nebo konjunkce . Alfred North Whitehead a Bertrand Russell v Principia Mathematica [1] představili tenzorový součin jako operaci binárního vztahu. Tenzorový součin grafů je také ekvivalentní Kroneckerovu součinu matic sousednosti těchto grafů [2] .

Zápis se někdy používá k označení dalšího konstruktu známého jako přímý produkt grafů , ale běžněji označuje produkt tenzoru. Symbol kříže vizuálně ukazuje dvě hrany, které jsou výsledkem tenzorového součinu dvou hran [3] . Tento produkt by neměl být zaměňován se silným produktem grafů . $G\krát H$

Příklady

Tenzorovým součinem je bipartitní graf , který se nazývá dvojitý krycí graf bipartitního grafu . Dvojitý krycí bipartitní graf Petersenova grafu je Desarguesův graf . Dvojitý krycí bipartitní graf úplného grafu je koruna , úplný bipartitní graf bez dokonalé shody ). ${\displaystyle G\times K_{2))$ $G$ $K_{2}\times G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Tenzorový součin úplného grafu sám se sebou je doplňkem rookova grafu . Jeho vrcholy lze umístit do čtvercové mřížky tak, že každý vrchol sousedí se všemi vrcholy, které nejsou ve stejném řádku nebo sloupci. $n\krát n$

Vlastnosti

Tenzorový součin je kategorie-teoretický součin v kategorii grafů a homomorfismů , to znamená, že homomorfismus v odpovídá dvojici homomorfismů v a v . Konkrétně graf připouští homomorfismus tehdy a pouze tehdy, pokud připouští homomorfismus oběma faktorům. $G\krát H$ $G$ $H$ $já$ $G\krát H$

Na jedné straně dvojice homomorfismů a dává homomorfismus: $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 }}~,

na druhé straně lze homomorfismus použít na projekční homomorfismy: $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\krát H\to H\\\pi _{G}((u,u'))=u'\end{cases}}~,

tedy dává homomorfismy k a . $G$ $H$

Matice sousednosti grafu je součin tenzoru matic sousednosti a . $G\krát H$ $G$ $H$

Pokud lze graf reprezentovat jako tenzorový součin, pak zobrazení nemusí být jedinečné, ale každé zobrazení má stejný počet neredukovatelných faktorů. Wilfried Imrich [4] dal polynomiální časový algoritmus pro rozpoznání tenzorového součinu grafů a nalezení rozkladu každého takového grafu.

Pokud je buď , nebo bipartitní , pak je jejich tenzorový součin také bipartitní. Graf je souvislý právě tehdy, když jsou oba faktory propojeny a alespoň jeden faktor není bipartitní [5] . Zejména dvojité pokrytí grafu bipartitním grafem je souvislé tehdy a jen tehdy, když je souvislý a není bipartitní. $G$ $H$ $G\krát H$ $G$ $G$

Hedetniemiho dohad dává vzorec pro chromatické číslo tenzorového součinu.

Viz také

Poznámky

↑ Whitehead, Russell, 1912 .
↑ Weichsel, 1962 .
↑ Hahn, Sabidussi, 1997 .
↑ Imrich, 1998 .
↑ Imrich, Klavžar, 2000 , str. Věta 5.29.

Literatura

Gena Hahn, Gert Sabidussi. Symetrie grafů: algebraické metody a aplikace . - Springer, 1997. - T. 497. - S. 116. - (Série NATO Advanced Science Institutes). - ISBN 978-0-7923-4668-5 .
Imrich W. Faktorování grafů hlavních součinů v polynomiálním čase // Diskrétní matematika . - 1998. - T. 192 . — S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Produktové grafy: Struktura a rozpoznávání. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. Kroneckerův produkt grafů // Proceedings of the American Mathematical Society . - 1962. - T. 13 , čís. 1 . — s. 47–52 . - doi : 10.2307/2033769 . — .
Whitehead A.N., Russell B. Principia Mathematica . — Cambridge University Press, 1912.

Odkazy

Nicholas Bray. Graph Categorical Product na webových stránkách Wolfram MathWorld .