Gráfok Descartes-szorzata

A matematika, azon belül a gráfelmélet területén a G és H gráfok Descartes-szorzata 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 ${\displaystyle \square }$ H Descartes-szorzat olyan gráf, melyre a következők igazak:

• ${\displaystyle G\square H}$ csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
• A ${\displaystyle G\square H}$ két csúcsa, (u,u' ) és (v,v' ) pontosan akkor szomszédos egymással, ha az alábbi két feltétel bármelyike teljesül:
  • u = v és u' szomszédos v' -vel H-ban vagy
  • u' = v' és u szomszédos v-vel G-ben.

A Descartes-szorzatként előálló gráfok hatékonyan, lineáris időben felismerhetők.^[1] A gráfok izomorfizmus ekvivalenciaosztályain értelmezett művelet kommutatív, ráadásul G ${\displaystyle \square }$ H és H ${\displaystyle \square }$ G természetesen izomorfak, címkézett gráfokon végzett műveletként azonban nem kommutatív. A művelet asszociatív is, hiszen az (F ${\displaystyle \square }$ G) ${\displaystyle \square }$ H és F ${\displaystyle \square }$ (G ${\displaystyle \square }$ H) gráfok természetesen izomorfak.

Néha a G × H jelölést is használják a gráfok Descartes-szorzatára, de ez a jelölés általában inkább a gráfok tenzorszorzatára utal. A négyzet szimbólum gyakoribb és egyértelműbb jelölése a Descartes-szorzatnak, mivel vizuálisan is jelzi a két él Descartes-szorzatául eredményül kapott négy élt.^[2]

• Két él Descartes-szorzata a négy hosszúságú körgráf: K₂ ${\displaystyle \square }$ K₂ = C₄.
• K₂ és egy útgráf Descartes-szorzata egy létragráf.
• Két útgráf Descartes-szorzata egy rácsgráf.
• n él Descartes-szorzata egy hiperkocka:

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

Így két hiperkockagráf Descartes-szorzata is egy hiperkocka: Q_i ${\displaystyle \square }$ Q_j = Q_i+j.

• Két mediángráf Descartes-szorzata mediángráf.
• Az n-szög alapú hasáb poliédergráfja a K₂ ${\displaystyle \square }$ C_n Descartes-szorzataként áll elő.
• A bástyagráf két teljes gráf Descartes-szorzata.

Ha egy összefüggő gráf Descartes-szorzat, létezik egyedi prímfelbontása, azaz olyan gráftényezőkre való felbontása, melyek maguk nem bonthatók tovább gráfok szorzataira.^[3] (Imrich & Klavžar 2000) azonban leír egy olyan, nem összefüggő gráfot, ami két különböző módon is felírható prím gráfok Descartes-szorzataként:

(K₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

ahol a plusz jelek a diszjunkt unió műveletét jelölik, a felső indexek pedig a Descartes-szorzat szerinti hatványozást.

Egy Descartes-szorzat pontosan akkor csúcstranzitív, ha mindkét tényező az.^[4]

Egy Descartes-szorzat pontosan akkor páros gráf, ha mindkét tényező az. Általánosabban, a Descartes-szorzat kromatikus száma eleget tesz a következő egyenletnek:

χ(G ${\displaystyle \square }$ H) = max {χ(G), χ(H)}.^[5]

A Hedetniemi-sejtés hasonló egyenlőséget állít fel gráfok tenzorszorzatára. Egy Descartes-szorzat függetlenségi száma nem ilyen könnyen számítható, de ahogy (Vizing 1963) megmutatta, kielégíti a következő egyenlőtlenségeket:

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G ${\displaystyle \square }$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

A Vizing-sejtés szerint egy Descartes-szorzat dominálási számára a következő egyenlőtlenség áll fenn:

γ(G ${\displaystyle \square }$ H) ≥ γ(G)γ(H).

Az algebrai gráfelmélet lehetővé teszi a gráfok Descartes-szorzatának tanulmányozását. Ha ${\displaystyle G_{1}}$ gráf ${\displaystyle n_{1}}$ csúccsal rendelkezik, és ${\displaystyle n_{1}\times n_{1}}$-es szomszédsági mátrixa ${\displaystyle \mathbf {A} _{1}}$, a ${\displaystyle G_{2}}$ gráf pedig ${\displaystyle n_{2}}$ csúccsal rendelkezik és ${\displaystyle n_{2}\times n_{2}}$-es szomszédsági mátrixa ${\displaystyle \mathbf {A} _{2}}$, akkor a két gráf Descartes-szorzatának szomszédsági mátrixa:

${\displaystyle \mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$,

ahol ${\displaystyle \otimes }$ a mátrixok Kronecker-szorzata és ${\displaystyle \mathbf {I} _{n}}$ az ${\displaystyle n\times n}$-es egységmátrix.^[6]

(Imrich & Klavžar 2000) szerint a gráfok Descartes-szorzatát 1912-ben definiálta Whitehead és Russell. Több alkalommal újra felfedezték őket, köztük itt: Gert Sabidussi (1960).

• Ez a szócikk részben vagy egészben a Cartesian 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.

• Aurenhammer, F.; Hagauer, J. & Imrich, W. (1992), "Cartesian graph factorization at logarithmic cost per edge", Computational Complexity 2 (4): 331–349, DOI 10.1007/BF01200428.
• Feigenbaum, Joan; Hershberger, John & Schäffer, Alejandro A. (1985), "A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics 12 (2): 123–138, DOI 10.1016/0166-218X(85)90066-6.
• 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, Wilfried & Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8.
• Imrich, Wilfried; Klavžar, Sandi & Rall, Douglas F. (2008), Graphs and their Cartesian Products, A. K. Peters, ISBN 1-56881-429-1.
• Imrich, Wilfried & Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics 307 (3-5): 472–483, DOI 10.1016/j.disc.2005.09.038.
• Kaveh, A. & Rahami, H. (2005), "A unified method for eigendecomposition of graph products", Communications in Numerical Methods in Engineering with Biomedical Applications 21 (7): 377–388, DOI 10.1002/cnm.753.
• Sabidussi, G. (1957), "Graphs with given group and given graph-theoretical properties", Canadian Journal of Mathematics 9: 515–525, DOI 10.4153/CJM-1957-060-7.
• Sabidussi, G. (1960), "Graph multiplication", Mathematische Zeitschrift 72: 446–457, DOI 10.1007/BF01162967.
• Vizing, V. G. (1963), "The Cartesian product of graphs", Vycisl. Sistemy 9: 30–43.

• Weisstein, Eric W.: Graph Cartesian Product (angol nyelven). Wolfram MathWorld