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: csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal; A 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.. Korábbi, polinom idejű algoritmusok itt találhatók: és . 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.

Példák Két él Descartes-szorzata a négy hosszúságú körgráf: K2 K2 = C4. K2 é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:

Így két hiperkockagráf Descartes-szorzata is egy hiperkocka: Qi Qj = Qi+j. Két mediángráf Descartes-szorzata mediángráf. Az n-szög alapú hasáb poliédergráfja a K2 Cn 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.; . 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: (K1 + K2 + K22) (K1 + K23) = (K1 + K22 + K24) (K1 + K2), 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., Theorem 4.19.

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)}. 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 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 gráf csúccsal rendelkezik, és -es szomszédsági mátrixa , a gráf pedig csúccsal rendelkezik és -es szomszédsági mátrixa , akkor a két gráf Descartes-szorzatának szomszédsági mátrixa: , ahol a mátrixok Kronecker-szorzata és az -es egységmátrix.

Történet 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: .

Fordítás

Jegyzetek

. . . . . . . . . .

További információk

Kategória:Gráfszorzatok