Direkt produkt av grafer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2021; kontroller kräver 2 redigeringar .

En kartesisk eller direkt produkt [1] G H av graferna G och H är en graf sådan att $\fyrkant$

uppsättningen av hörn i grafen G H är den direkta produkten V(G) × V(H) $\fyrkant$
vilka två hörn som helst (u,u') och (v,v') är angränsande i G H om och endast om $\fyrkant$
- eller u = v och u' ligger intill v' i H
- eller u' = v' och u ligger intill v i G .

Den kartesiska produkten kan identifieras effektivt i linjär tid [2] . Operationen är kommutativ som en operation på grafisomorfismklasser , och mer strikt är graferna G H och H G naturligt isomorfa , men operationen är inte kommutativ som en operation på märkta grafer. Operationen är också associativ , eftersom graferna ( F G ) H och F ( GH ) är naturligt isomorfa. $\fyrkant$ $\fyrkant$ $\fyrkant$ $\fyrkant$ $\fyrkant$ $\fyrkant$

Notationen G × H används ibland för den kartesiska produkten av grafer också, men oftare används den för en annan konstruktion som kallas tensorprodukten av grafer . Den fyrkantiga symbolen är mer vanligt förekommande och är entydig för den kartesiska produkten av grafer. Den visar visuellt de fyra kanterna som härrör från den kartesiska produkten av två kanter [3]

Exempel

Den kartesiska produkten av två kanter är en cykel med fyra hörn: K 2 K 2 =C 4 . $\fyrkant$
Den kartesiska produkten av K 2 och stigen är en stege .
Den kartesiska produkten av två banor är ett gitter .
Den kartesiska produkten av n kanter är en hyperkub:

(K_{2})^{\square n}=Q_{n}.

Således är den kartesiska produkten av två hyperkubgrafer en annan hyperkub — Q i Q j =Q i+j .

\fyrkant

Den kartesiska produkten av två mediangrafer är en annan mediangraf.
Grafen över hörn och kanter på ett n-gonalt prisma är en kartesisk produkt K 2 C n . $\fyrkant$
En torngraf är den kartesiska produkten av två kompletta grafer .

Egenskaper

Om en sammankopplad graf är en kartesisk produkt, kan den dekomponeras unikt till en produkt av primtalsfaktorer, grafer som inte kan dekomponeras till en produkt av grafer [4] [5] . Emellertid beskrev Imrich och Klavzhar [6] en frånkopplad graf, som kan representeras på två olika sätt som en kartesisk produkt av enkla grafer:

(K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 )=(K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),

\fyrkant

\fyrkant

där plustecknet betyder en disjunkt förening och det upphöjda betyder en multipel kartesisk produkt.

En kartesisk produkt är en vertextransitiv graf om och endast om var och en av dess faktorer är vertextransitiv [7] .

En kartesisk produkt är tvådelad om och endast om var och en av dess faktorer är tvådelad. Mer generellt uppfyller det kromatiska numret för en kartesisk produkt ekvationen

χ( GH)=max {χ(G), χ(H)} [8] .

\fyrkant

Hedetniemis gissning anger en relaterad likhet för tensorprodukten av grafer . Oberoendetalet för kartesiska produkter är inte lätt att beräkna, men som Vizing [5] visade , tillfredsställer oberoendetalet ojämlikheterna

α( G )α( H ) + min{|V( G )|-α( G ),|V( H )|-α( H )} ≤ α( GH ) ≤ min{α( G ) |V ( H )|, a( H ) |V( G )|}.

\fyrkant

Vizings gissning säger att dominanstalet för en kartesisk produkt tillfredsställer ojämlikheten

y( GH ) ≥ y( G )y( H ) .

\fyrkant

Algebraisk grafteori

Algebraisk grafteori kan användas för att analysera den kartesiska produkten av grafer. Om en graf har hörn och en närliggande matris , och en graf har hörn och en närliggande matris , så ges närliggande matris för den kartesiska produkten av två grafer av $G_{1}$ $n_{1}$ ${\displaystyle n_{1}\times n_{1))$ $\mathbf {A} _{1}$ $G_{2}$ $n_{2}$ $n_{2}\times n_{2}$ ${\displaystyle \mathbf {A} _{2))$

\mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {E} _{n_{2}}+\mathbf {E} _{n_{1 }}\otimes \mathbf {A} _{2}

där betecknar Kronecker-produkten av matriser, och betecknar identitetsmatrisen [9] . $\ ibland$ $\mathbf {E} _{n}$ $n\ gånger n$

Historik

Enligt Imrich och Klavzhar [6] definierades kartesiska produkter av grafer 1912 av Whitehead och Russell . Produkten av grafer återupptäcktes upprepade gånger senare, i synnerhet av Gert Sabidoussi [4] .

Anteckningar

↑ Vizing använde termen "kartesisk produkt", i artikeln " direkt produkt " kallas samma produkt direkt.
↑ ( Imrich och Peterin 2007 ). För tidigare polynomtidsalgoritmer , se Feigenbaum, Hershberger , Schäffer 1985 och Aurenhammer, Hagauer, Imrich 1992 .
↑ Hahn, Sabidussi, 1997 .
↑ 1 2 Sabidussi, 1960 .
↑ 1 2 Vizing, 1963 .
↑ 1 2 Imrich, Klavžar, 2000 .
↑ Imrich, Klavžar, 2000 , sid. Sats 4.19.
↑ Sabidussi, 1957 .
↑ Kaveh, Rahami, 2005 .

Litteratur

F. Aurenhammer, J. Hagauer, W. Imrich. Kartesisk graffaktorisering till logaritmisk kostnad per kant // Computational Complexity. - 1992. - Vol. 2 , nummer. 4 . - S. 331-349 . - doi : 10.1007/BF01200428 .
Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer. En polynomisk tidsalgoritm för att hitta primtalsfaktorerna för kartesiska produktgrafer // Diskret tillämpad matematik . - 1985. - T. 12 , nr. 2 . - S. 123-138 . - doi : 10.1016/0166-218X(85)90066-6 .
Gena Hahn, Gert Sabidussi. Grafsymmetri: algebraiska metoder och tillämpningar. - Springer, 1997. - T. 497. - P. 116. - ISBN 978-0-7923-4668-5 .
Wilfried Imrich, Sandi Klavzar. Produktdiagram: Struktur och erkännande. - Wiley, 2000. - ISBN 0-471-37039-8 .
Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Grafer och deras kartesiska produkter. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
Wilfried Imrich, Iztok Peterin. Att känna igen kartesiska produkter i linjär tid // Diskret matematik . - 2007. - T. 307 , nr. 3-5 . - S. 472-483 . - doi : 10.1016/j.disc.2005.09.038 .
A. Kaveh, H. Rahami. En enhetlig metod för egennedbrytning av grafprodukter // Kommunikation i numeriska metoder inom teknik med biomedicinska tillämpningar. - 2005. - T. 21 , nr. 7 . - S. 377-388 . - doi : 10.1002/cnm.753 .
G. Sabidussi. Grafer med given grupp och givna grafteoretiska egenskaper // Canadian Journal of Mathematics . - 1957. - T. 9 . - S. 515-525 . - doi : 10.4153/CJM-1957-060-7 .
G. Sabidussi. Grafmultiplikation // Mathematische Zeitschrift . - 1960. - T. 72 . - S. 446-457 . - doi : 10.1007/BF01162967 .
V. G. Vizing. Kartesisk produkt av grafer // Beräkningssystem. - 1963. - T. 9 . - S. 30-43 .

Länkar

Weisstein, Eric W. Graph Cartesian Product på Wolfram MathWorld .