Produsul tensor al graficelor

Produsul tensor al graficelor și este un grafic al cărui set de vârfuri este un produs cartezian și diferite vârfuri și sunt adiacente dacă și numai dacă este adiacent și este adiacent cu . $G\ ori H$ $G$ $H$ $V(G)\time V(H)$ $(u,u')$ $(v,v')$ $G\ ori H$ $u$ $v$ $u'$ $v'$

Alte titluri

Produsul tensor se mai numește și produs direct, produs de categorie , produs relațional , produs Kronecker , produs direct slab sau conjuncție . Alfred North Whitehead și Bertrand Russell în Principia Mathematica [1] au introdus produsul tensor ca operație de relație binară. Produsul tensor al graficelor este, de asemenea, echivalent cu produsul Kronecker al matricelor de adiacență ale acestor grafice [2] .

Notația este uneori folosită pentru a se referi la un alt construct cunoscut ca produsul direct al graficelor , dar mai frecvent denotă produsul tensor. Simbolul crucii arată vizual două muchii rezultate din produsul tensor al două muchii [3] . Acest produs nu trebuie confundat cu produsul puternic al graficelor . $G\ ori H$

Exemple

Produsul tensor este un graf bipartit , care este numit graficul dublu de acoperire al grafului bipartit . Graficul bipartit de acoperire dublă al graficului Petersen este graficul Desargues . Graficul bipartit de acoperire dublă al unui grafic complet este coroana , un grafic bipartit complet fără o potrivire perfectă ). $G\times K_{2)$ $G$ $K_{2}\times G(5,2)=G(10,3)$ $K_n$ $K_{{n,n}}$
Produsul tensor al unui graf complet cu el însuși este complementul grafului unui turn . Vârfurile sale pot fi plasate într-o rețea pătrată astfel încât fiecare vârf să fie adiacent tuturor nodurilor care nu se află în același rând sau coloană. $n\ ori n$

Proprietăți

Un produs tensor este un produs teoretic din categoria graficelor și homomorfismelor , adică un homomorfism în corespunde unei perechi de homomorfisme în și în . În special, un grafic admite un homomorfism dacă și numai dacă admite un homomorfism la ambii factori. $G\ ori H$ $G$ $H$ $eu$ $G\ ori H$

Pe de o parte, perechea de homomorfisme și da un homomorfism: $f_{G}:I\la G$ $f_{H}:I\la H$

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

pe de altă parte, homomorfismul poate fi aplicat homomorfismelor de proiecție: $f\colon I\la 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}}~,

dând astfel homomorfisme către și către . $G$ $H$

Matricea de adiacență a unui grafic este produsul tensor al matricelor de adiacență și . $G\ ori H$ $G$ $H$

Dacă un grafic poate fi reprezentat ca un produs tensor, atunci reprezentarea poate să nu fie unică, dar fiecare reprezentare are același număr de factori ireductibili. Wilfried Imrich [4] a dat un algoritm de timp polinomial pentru recunoașterea produsului tensor al graficelor și pentru a găsi descompunerea oricărui astfel de grafic.

Dacă fie , fie este bipartit , atunci produsul lor tensor este și bipartit. Graficul este conectat dacă și numai dacă ambii factori sunt conectați și cel puțin un factor nu este bipartit [5] . În special, o acoperire dublă de către un graf bipartit a unui graf este conectată dacă și numai dacă este conex și nu bipartit. $G$ $H$ $G\ ori H$ $G$ $G$

Conjectura lui Hedetniemi oferă o formulă pentru numărul cromatic al unui produs tensor.

Vezi și

Note

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

Literatură

Gena Hahn, Gert Sabidussi. Simetria grafică: metode și aplicații algebrice . - Springer, 1997. - T. 497. - S. 116. - (Seria NATO Advanced Science Institutes). - ISBN 978-0-7923-4668-5 .
Imrich W. Factorizarea graficelor produselor cardinale în timp polinomial // Matematică discretă . - 1998. - T. 192 . — S. 119–144 . - doi : 10.1016/S0012-365X(98)00069-7 .
Wilfried Imrich, Sandi Klavzar. Grafice de produs: Structură și recunoaștere. - Wiley, 2000. - ISBN 0-471-37039-8 .
Paul M. Weichsel. Produsul Kronecker al graficelor // Proceedings of the American Mathematical Society . - 1962. - T. 13 , nr. 1 . — p. 47–52 . - doi : 10.2307/2033769 . — .
Whitehead A.N., Russell B. Principia Mathematica . — Cambridge University Press, 1912.

Link -uri

Nicholas Bray. Graficul produsului categoric pe site- ul Wolfram MathWorld .