Tenzorový součin grafů - Tensor product of graphs

Tenzorový produkt grafů.

v teorie grafů, tenzorový produkt G × H grafů G a H je graf takový, že

• množina vrcholů G × H je kartézský součin PROTI(G) × PROTI(H); a
• vrcholy (g, h) a (g ', h') sousedí s G × H kdyby a jen kdyby
  • G sousedí s G'
  • h sousedí s h '.

Tenzorový produkt se také nazývá přímý produkt, Produkt Kronecker, kategorický produkt, světový produkt, relační produkt, slabý přímý produktnebo spojení. Jako operaci na binárních relacích představil tenzorový produkt Alfred North Whitehead a Bertrand Russell v jejich Principia Mathematica (1912 ). Je to také ekvivalentní s Produkt Kronecker z matice sousedství grafů.^[1]

Zápis G × H je také (a dříve normálně byl) používán k reprezentaci další konstrukce známé jako Kartézský součin grafů, ale dnes se běžněji odkazuje na tenzorový produkt. Symbol kříže vizuálně zobrazuje dvě hrany, které jsou výsledkem tenzorového součinu dvou hran.^[2] Tento produkt by neměl být zaměňován s silný produkt grafů.

Příklady

• Tenzorový produkt G × K.₂ je bipartitní graf, volal dvojdílný dvojitý kryt z G. Bipartitní dvojitý kryt Petersenův graf je Desargues graf: K.₂ × G(5,2) = G(10,3). Dvojdílný dvojitý kryt a kompletní graf K._n je korunový graf (A kompletní bipartitní graf K._n,n minus a perfektní shoda ).
• Tenzorový produkt úplného grafu, který je sám o sobě, je doplněk a Rookův graf. Jeho vrcholy lze umístit do n podle n mřížka, takže každý vrchol sousedí s vrcholy, které nejsou ve stejné řadě nebo sloupci mřížky.

Vlastnosti

Tenzorový produkt je teoretický produkt kategorie v kategorii grafů a homomorfismy grafů. To znamená homomorfismus s G × H odpovídá dvojici homomorfismů G a do H. Zejména graf Já připouští homomorfismus do G × H právě tehdy, když připouští homomorfismus do G a do H.

Chcete-li vidět, že v jednom směru pozorujte dvojici homomorfismů F_G : Já → G a F_H : Já → H poskytuje homomorfismus

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

V opačném směru homomorfismus F: Já → G × H lze skládat s projekcemi homomorfismů

${ displaystyle { 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 _ {H} ((u, u ')) = u' end {cases}}}$

poskytnout homomorfismy G a do H.

Matice sousedství G × H je tenzorový produkt sousedních matic G a H.

Pokud lze graf reprezentovat jako tenzorový produkt, může existovat několik různých reprezentací (tenzorové produkty nesplňují jedinečnou faktorizaci), ale každá reprezentace má stejný počet neredukovatelných faktorů. Imrich (1998) dává polynomiální časový algoritmus pro rozpoznávání grafů tenzorových produktů a hledání faktorizace jakéhokoli takového grafu.

Pokud ano G nebo H je bipartitní, pak také jejich tenzorový produkt. G × H je spojen tehdy a jen tehdy, jsou-li oba faktory spojeny a alespoň jeden faktor je nebipartitní.^[3] Zejména bipartitní dvojitý kryt G je připojen právě tehdy G je propojený a nestranný.

The Hedetniemi domněnka, který dal vzorec pro chromatické číslo tenzorového produktu, vyvrátil Yaroslav Shitov (2019 ).

Tenzorový součin grafů vybavuje kategorii grafů a homomorfismů grafů strukturou a symetrický uzavřená monoidní kategorie. Nechat ${ displaystyle G_ {0}}$ označuje podkladovou sadu vrcholů grafu ${ displaystyle G}$. Vnitřní hom ${ displaystyle [G, H]}$ má funkce ${ displaystyle f: G_ {0} až H_ {0}}$ jako vrcholy a hrana z ${ displaystyle f: G_ {0} až H_ {0}}$ na ${ displaystyle f ': G_ {0} do H_ {0}}$ kdykoli hrana ${ displaystyle {x, y }}$ v ${ displaystyle G}$ naznačuje ${ displaystyle {f (x), f '(y) }}$ v ${ displaystyle H}$^[4].

Viz také

• Grafový produkt
• Silný produkt grafů

Poznámky

Reference

• Brown, R .; Morris, I .; Shrimpton, J .; Wensley, C. D. (2008), „Graphs of Morphisms of Graphs“, Electronic Journal of Combinatorics, 15: A1.
• Hahn, Geňa; Sabidussi, Gert (1997), Symetrie grafů: algebraické metody a aplikace, Series Advanced Science Institutes Series NATO, 497, Springer, str. 116, ISBN  978-0-7923-4668-5.
• Imrich, W. (1998), „Factoring cardinal product graphs in polynomial time“, Diskrétní matematika, 192: 119–144, doi:10.1016 / S0012-365X (98) 00069-7, PAN  1656730
• Imrich, Wilfried; Klavžar, Sandi (2000), Grafy produktů: Struktura a rozpoznáváníWiley, ISBN  0-471-37039-8
• Shitov, Yaroslav (květen 2019), Protiklady k Hedetniemiho domněnce, arXiv:1905.02167
• Weichsel, Paul M. (1962), „The Kronecker product of graphs“, Proceedings of the American Mathematical Society, 13 (1): 47–52, doi:10.2307/2033769, JSTOR  2033769, PAN  0133816
• Whitehead, A. N.; Russell, B. (1912), Principia Mathematica, Cambridge University Press, roč. 2, s. 384

externí odkazy

• Nicolas Bray. „Graf kategorický produkt“. MathWorld.