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.Sablon:Sfn
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.Sablon:Sfn Nem tévesztendő össze a gráfok erős szorzatával.
Példák
- A G × K2 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: K2 × G(5,2) = G(10,3). Egy Kn teljes gráf páros dupla fedése koronagráf (egy Kn,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 Sablon:Math és Sablon:Math homomorfizmus-pár kiadja a következő homomorfizmust:
A másik irányban egy Sablon:Math homomorfizmus előállítható a
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ő. Sablon:Harvtxt 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.[1] 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.