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

• $G◻H$ csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
• A $G◻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 $◻$ H és H $◻$ 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 $◻$ G) $◻$ H és F $◻$ (G $◻$ 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.Sablon:Sfnp

Példák

• Két él Descartes-szorzata a négy hosszúságú körgráf: K₂ $◻$ 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{)}^{◻n}=Q_n.$

Így két hiperkockagráf Descartes-szorzata is egy hiperkocka: Q_i $◻$ 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₂ $◻$ 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. Sablon:Harvtxt 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₂²) $◻$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) $◻$ (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 $◻$ H) = max {χ(G), χ(H)}.Sablon:Sfnp

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 Sablon:Harvtxt megmutatta, kielégíti a következő egyenlőtlenségeket:

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G $◻$ 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 $◻$ 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 ${𝐀}_1$, a $G_2$ gráf pedig $n_2$ csúccsal rendelkezik és $n_2\times n_2$-es szomszédsági mátrixa ${𝐀}_2$, akkor a két gráf Descartes-szorzatának szomszédsági mátrixa:

${𝐀}_{1◻2}={𝐀}_1\otimes {𝐈}_{n_2}+{𝐈}_{n_1}\otimes {𝐀}_2$,

ahol $\otimes$ a mátrixok Kronecker-szorzata és ${𝐈}_n$ az $n\times n$-es egységmátrix.Sablon:Sfnp

Történet

Sablon:Harvtxt 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: Sablon:Harvs.

Fordítás

• Sablon:Fordítás

Jegyzetek

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

További információk

• Sablon:Mathworld