Grafikon homeomorfizmus

Két gráf és akkor homeomorf , ha van izomorfizmusa a gráf valamilyen felosztásának és a gráf valamilyen felosztásának [1] . Ha egy gráf éleit csúcsokat összekötő szegmensekként értjük (ahogyan az ábrákon általában látható), akkor két gráf homeomorf a gráfelmélet kontextusában, ha topológiai értelemben homeomorf .

Felosztás és kizárás

Általánosságban elmondható, hogy a G gráf felosztása (néha a kiterjesztést [2] vagy felosztást használjuk ) olyan gráf, amelyet G -beli élek elosztásával kapunk . Valamely e élt { u , v } végső csúcsokkal osztva egy gráfot kapunk, amely egy új w csúcsot és két { u , w } és { w , v } élt tartalmaz e él helyett [1] .

Például e él { u , v } végekkel :

két élre osztható, e 1 és e 2 :

Az inverz művelet, kiküszöbölve a w csúcsot a rá eső élekkel ( e 1 , e 2 ), a w csúcsgal szomszédos mindkét élt ( e 1 , e 2 ) egy új élre cseréli, amely összeköti a pár végpontjait. Hangsúlyozni kell, hogy ez a művelet csak olyan csúcsokra alkalmazható, amelyek pontosan két éllel esnek be.

Például egy egyszerű összefüggő gráf két éllel e 1 { u , w } és e 2 { w , v }:

van egy csúcsa ( w ), amely kizárható, ami a következőket eredményezi:

Annak meghatározása, hogy egy H gráf homeomorf-e egy G részgráfhoz , NP-teljes feladat [3] .

Baricentrikus felosztások

A baricentrikus felosztás felosztja a gráf minden élét. Ez egy speciális felosztás, amely mindig egy kétrészes gráfot ad . Ez az eljárás megismételhető úgy, hogy az n- edik baricentrikus felosztás az n-1 felosztás baricentrikus felosztása legyen . A második ilyen felosztás mindig egy egyszerű gráf .

Felületbe ágyazás

Nyilvánvaló, hogy a gráf felosztása megőrzi a síkságot. A Pontrjagin-Kuratovszkij tétel azt állítja

egy véges gráf akkor és csak akkor síkbeli , ha nem tartalmaz K 5 -höz ( teljes gráf öt csúcstal ) vagy K 3,3 -hoz ( teljes kétrészes gráf hat csúcstal, amelyek közül három kapcsolódik a többihez) homeomorf részgráfot . három).

Valójában a K 5 vagy K 3,3 homeomorf gráfot Kuratowski részgráfnak nevezzük .

A Robertson-Seymour- tételből következő általánosítás azt állítja, hogy bármely g egész számra létezik olyan véges akadályozó gráfhalmaz , amely szerint a H gráf akkor és csak akkor ágyazható be a g nemzetség felületébe , ha H nem tartalmaz egy gráfnak homeomorf másolatot. . Például Kuratovsky részgráfokból áll.

Példa

A következő példában a G és H gráfok homeomorfok.

G H

Ha a G' gráf a G gráf külső éleinek felosztásával, a H' gráf pedig a H gráf belső éleinek felosztásával jön létre, akkor G' és H' grafikus ábrázolása hasonló:

G', H'

Így a G' és H' gráfok között izomorfizmus van, ami azt jelenti, hogy G és H homeomorf.

Lásd még

Jegyzetek

  1. ↑ 1 2 Yablonsky, 1986 , p. 225.
  2. ↑ Trudeau, 1993 , p. 76, 20. definíció.
  3. ↑ Az irodalomban egy szélesebb körben vizsgált probléma, az úgynevezett "részgráf homeomorfizmus problémája" azt kérdezi, hogy egy H gráf felosztása izomorf-e egy G részgráfhoz . Ha H egy n csúcsú ciklus, akkor a probléma megegyezik egy Hamilton-ciklus megtalálásával , ezért NP-teljes. Ez a megfogalmazás azonban csak azzal a kérdéssel ekvivalens, hogy egy H gráf homeomorf-e egy G részgráfhoz , amikor H nem tartalmaz második fokú csúcsokat, mivel ez nem tesz lehetővé H -ben a kivételt. A Hamilton-ciklus enyhe módosításával kimutatható, hogy az adott feladat NP-teljes - egy-egy csúcsot adunk hozzá H -ben és G -ben az összes többi csúcs mellett. Ekkor az egy csúcsponttal megnövelt G gráf akkor és csak akkor tartalmaz egy ( n + 1) csúcsú kerék homeomorf részgráfját,  ha G Hamilton. Az algráf homeomorfizmus problémájának összetettségéről lásd LaPaugh és Rivest írását ( LaPaugh, Rivest 1980 ).

Irodalom