From Wikipedia, the free encyclopedia
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:
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 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.[2]
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:
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:
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:
A Vizing-sejtés szerint egy Descartes-szorzat dominálási számára a következő egyenlőtlenség áll fenn:
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.[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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.