Gráfok Descartes-szorzata

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 $\square$ H Descartes-szorzat olyan gráf, melyre a következők igazak:

• $G\square H$ csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
• A $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. A gráfok izomorfizmus ekvivalenciaosztályain értelmezett művelet kommutatív, ráadásul G $\square$ H és H $\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 $\square$ G) $\square$ H és F $\square$ (G $\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.

Példák

• Két él Descartes-szorzata a négy hosszúságú körgráf: K₂ $\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:

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

Így két hiperkockagráf Descartes-szorzata is egy hiperkocka: Q_i $\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₂ $\square$ C_n Descartes-szorzataként áll elő.
• A bástyagráf két teljes gráf Descartes-szorzata.

Tulajdonságok

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. (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₂²) $\square$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) $\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.

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 $\square$ H) = max {χ(G), χ(H)}.

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 $\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 $\square$ H) ≥ γ(G)γ(H).

Algebrai gráfelmélet

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

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

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

Történet

(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).

Fordítás

• 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.

Jegyzetek

• 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.

További információk

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