Grafikonok közvetlen szorzata

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. február 6-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A G és H gráfok derékszögű vagy direkt szorzata [1] G H olyan gráf, amelyre

A derékszögű szorzat hatékonyan felismerhető lineáris időben [2] . A művelet a gráfizomorfizmus osztályokon végzett műveletként kommutatív , és szigorúbban a G H és H G gráfok természetesen izomorfak , de a művelet nem kommutatív, mint a címkézett gráfokon végzett művelet. A művelet asszociatív is, mivel az ( F G ) H és F ( G H ) gráfok természetesen izomorfak.

A G × H jelölést időnként a gráfok derékszögű szorzatára is használják, de gyakrabban egy másik, a gráfok tenzorszorzataként ismert konstrukcióra is . A négyzet szimbólumot gyakrabban használják, és egyértelmű a gráfok derékszögű szorzatára. Vizuálisan mutatja a két él derékszögű szorzatából származó négy élt [3]

Példák

Így két hiperkocka gráf derékszögű szorzata egy másik hiperkocka — Q i Q j =Q i+j .

Tulajdonságok

Ha egy összefüggő gráf derékszögű szorzat, akkor egyedileg felbontható prímtényezők szorzatára, olyan gráfokra, amelyek nem bonthatók fel gráfok szorzatára [4] [5] . Imrich és Klavzhar [6] azonban leírtak egy szétkapcsolt gráfot, amely kétféleképpen ábrázolható egyszerű gráfok derékszögű szorzataként:

(K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 )= (K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),

ahol a plusz jel diszjunkt egyesülést, a felső index pedig többszörös derékszögű szorzatot jelent.

Egy derékszögű szorzat akkor és csak akkor csúcstranzitív gráf , ha minden tényezője csúcstranzitív [7] .

Egy derékszögű szorzat akkor és csak akkor bipartit , ha minden tényezője kétoldalú. Általánosabban, egy derékszögű szorzat kromatikus száma kielégíti az egyenletet

χ(G H)=max {χ(G), χ(H)} [8] .

Hedetniemi sejtése a gráfok tenzorszorzatára vonatkozó egyenlıséget állít ki . A derékszögű szorzatok függetlenségi számát nem könnyű kiszámítani, de ahogy Vizing [5] kimutatta , a függetlenségi szám kielégíti az egyenlőtlenségeket

α( G )α( H ) + min{|V( G )|-α( G ),|V( H )|-α( H )} ≤ α( G H ) ≤ min{α( G ) |V ( H )|, α( H ) |V( G )|}.

Vining sejtése szerint a derékszögű szorzat dominanciaszáma kielégíti az egyenlőtlenséget .

γ( G H ) ≥ γ( G ) γ( H ).

Algebrai gráfelmélet

Az algebrai gráfelmélet a gráfok derékszögű szorzatának elemzésére használható. Ha egy gráfnak vannak csúcsai és szomszédsági mátrixa , és egy gráfnak vannak csúcsai és szomszédsági mátrixa , akkor két gráf derékszögű szorzatának szomszédsági mátrixa a következőképpen adódik :

,

ahol a mátrixok Kronecker-szorzatát , és az azonosságmátrixot jelöli [9] .

Történelem

Imrich és Klavzhar [6] szerint a gráfok derékszögű szorzatait 1912-ben Whitehead és Russell határozta meg . A gráfok szorzatát később többször is újra felfedezték, különösen Gert Sabidoussi [4] .

Jegyzetek

  1. ↑ A Vizing a „derékszögű termék” kifejezést használta, a „ Közvetlen termék ” cikkben ugyanezt a terméket közvetlennek nevezik.
  2. ↑ ( Imrich és Peterin 2007 ). A korábbi polinomiális idő algoritmusokról lásd Feigenbaum, Hershberger , Schäffer 1985 és Aurenhammer, Hagauer, Imrich 1992 .
  3. ↑ Hahn, Sabidussi, 1997 .
  4. ↑ 1 2 Sabidussi, 1960 .
  5. ↑ 1 2 Vizing, 1963 .
  6. ↑ 1 2 Imrich, Klavžar, 2000 .
  7. ↑ Imrich, Klavžar, 2000 , p. 4.19. tétel.
  8. ↑ Sabidussi, 1957 .
  9. ↑ Kaveh, Rahami, 2005 .

Irodalom

Linkek