Gráfok tenzorszorzata

A matematika, azon belül a gráfelmélet területén a G és H gráfok tenzorszorzata egy gráfszorzás, olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G × H tenzorszorzat olyan gráf, melyre a következők igazak:

G × H csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
két G × H-beli csúcs, (u,u') és (v,v') pontosan akkor szomszédosak, ha
- u' szomszédos v' -vel és
- u szomszédos v-vel.

A tenzorszorzat egyéb megnevezései: direktszorzat, kategóriaszorzat, kardinális szorzat, relációs szorzat, Kronecker-szorzat, gyenge direktszorzat vagy konjunkció. A bináris reláción értelmezett tenzorszorzatot Alfred North Whitehead és Bertrand Russell vezették be Principia Mathematicájukban (1912). A művelet ekvivalens a gráfok szomszédsági mátrixainak Kronecker-szorzatával.^[1]

A G × H jelölést néha egy másik műveletre, a gráfok Descartes-szorzatára használják, de gyakrabban vonatkozik a tenzorszorzatra. A kereszt szimbólum vizuálisan a két él tenzorszorzatából adódó két élre emlékeztet.^[2] Nem tévesztendő össze a gráfok erős szorzatával.

Példák

A G × K₂ tenzorszorzat eredménye egy páros gráf, amit G páros dupla fedésének (bipartite double cover) neveznek. A Petersen-gráf páros dupla fedése a Desargues-gráf: K₂ × G(5,2) = G(10,3). Egy K_n teljes gráf páros dupla fedése koronagráf (egy K_n,n teljes páros gráf mínusz egy teljes párosítás).
Egy teljes gráf önmagával való tenzorszorzata egy bástyagráf komplementere. Csúcsai elhelyezhetők egy n-szer n-es rácsban, ahol minden csúcs szomszédos azon csúcsokkal, melyekkel eltérő sorban és oszlopban van.

Tulajdonságok

A tenzorszorzat a gráfok kategóriáját és a gráfhomomorfizmusokat tekintve kategóriaelméleti szorzat. Tehát egy G × H-ba vivő homomorfizmus megfelel egy G-be, majd H-ba vivő homomorfizmus-párnak. Továbbá egy I gráf pontosan akkor vihető át homomorfizmussal G × H-ba, ha átvihető egy homomorfizmussal G-be, majd H-ba.

Ennek belátásához vegyük észre, hogy az egyik irányban a $f G : I \to G$ és $f H : I \to H$ homomorfizmus-pár kiadja a következő homomorfizmust:

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

A másik irányban egy $f : I \to G \times H$ homomorfizmus előállítható a

{\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}}

projekciós homomorfizmusokból a G-be és H-ba vivő homomorfizmusok elérésére.

A G × H szomszédsági mátrixa megegyezik G és H szomszédsági mátrixainak tenzorszorzatával.

Ha egy gráf előállítható gráfok tenzorszorzataként, akkor előfordulhat, hogy különböző gráfok tenzorszorzataként is előáll (a tenzorszorzatnak nem jellemzője az egyedi faktorizáció), de minden tenzorszorzat-reprezentáció ugyanannyi irreducibilis tényezőből áll elő. (Imrich 1998) megad egy polinom idejű algoritmust a tenzorszorzat-gráfok felismerésére és az ilyen gráfok faktorizációjára.

Ha akár G, akár H páros gráf, akkor tenzorszorzatuk is az. G × H pontosan akkor összefüggő, ha mindkét tényező összefüggő és legalább az egyik tényező nem páros.^[3] A G páros dupla fedése pedig pontosan akkor összefüggő, ha G összefüggő és nem páros.

A Hedetniemi-sejtés a tenzorszorzat kromatikus számát próbálja meghatározni.

Kapcsolódó szócikkek

Fordítás

Ez a szócikk részben vagy egészben a Tensor product of graphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Hahn, Geňa & Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, vol. 497, NATO Advanced Science Institutes Series, Springer, p. 116, ISBN 978-0-7923-4668-5, <https://books.google.com/books?id=-tIaXdII8egC&pg=PA116>.
Imrich, W. (1998), "Factoring cardinal product graphs in polynomial time", Discrete Mathematics 192: 119–144, DOI 10.1016/S0012-365X(98)00069-7
Imrich, Wilfried & Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
Weichsel, Paul M. (1962), "The Kronecker product of graphs", Proceedings of the American Mathematical Society 13 (1): 47–52, DOI 10.2307/2033769
Whitehead, A. N. & Russell, B. (1912), Principia Mathematica, Cambridge University Press, vol. 2, p. 384

További információk

Nicolas Bray: Graph Categorical Product (angol nyelven). Wolfram MathWorld

[FOOTNOTEWeichsel1962-1] Weichsel 1962.

[FOOTNOTEHahnSabidussi1997-2] Hahn & Sabidussi 1997.

[3] Imrich & Klavžar 2000, Theorem 5.29

[1]

[2]

[3]