Számolja a vastagságot

A gráfelméletben a G gráf vastagsága  a legkisebb számú sík részgráf , amelyre a G gráf élei felbonthatók . Vagyis ha van egy k azonos csúcshalmazú síkgráf halmaza, amelyek egyesítése a G gráfot adja , akkor a G gráf vastagsága legfeljebb k [1] [2] [3] [4 ] .

Így egy sík gráf vastagsága 1. A 2 vastagságú gráfokat biplanáris gráfoknak nevezzük . A vastagság fogalma Frank Harari 1962-es sejtéséből ered, miszerint minden 9 csúcsú gráf, akár maga, akár komplementere , nem síkbeli . A probléma egyenértékű annak meghatározásával, hogy a K 9 teljes gráf kétsíkú-e (nem biplanáris, tehát a sejtés igaz) [5] . Mutzel, Odenthal és Scharbrodt [6] átfogó áttekintést ad a gráfvastagság témaköréről (1998-tól) .

Konkrét grafikonok

Egy n csúcsú teljes gráf vastagsága K n

kivéve az n = 9, 10 eseteket , amelyeknél a vastagság három [7] [8] .

Néhány esettől eltekintve a K a,b teljes kétrészes gráf vastagsága [7] [9]

Kapcsolódó feladatok

Bármely erdő síkbeli, és bármely sík gráf három vagy kevesebb erdőre bontható. Így bármely G gráf vastagsága nem nagyobb, mint ugyanazon gráf fásodása (az erdők minimális száma, amelyekre a gráf felbontható), és nem kisebb, mint a fásság osztva hárommal [10] . A G gráf vastagsága összefügg egy másik standard invariánssal , a degenerációval , amely a részgráf minimális fokának G gráf összes részgráfjának maximuma . Ha egy n csúcsú gráf t vastagságú , akkor éleinek száma nem haladja meg a t (3 n − 6) értéket , ami azt jelenti, hogy a degeneráció nem haladja meg a 6 t − 1 értéket . Másrészt, ha egy gráf degeneráltsága egyenlő D -vel, akkor a fája és vastagsága nem haladja meg a D -t .

A vastagság szorosan összefügg az egyidejű beágyazódás problémájával [11] . Ha két vagy több síkgráfnak ugyanaz a csúcskészlete, akkor ezek a gráfok mindegyike beágyazható egy síkba, ahol az élek görbeként vannak ábrázolva, így minden csúcsnak azonos pozíciója lesz az összes rajzon. Azonban kiderülhet, hogy az ilyen rajzok elkészítése lehetetlen vonalszakaszok használata esetén .

Egy másik gráfinvariáns, a G gráf egyenes vonalú vastagsága vagy geometriai vastagsága , a legkisebb számú sík gráfot számolja meg, amelyre G felbontható azzal a megkötéssel, hogy mindegyik egyidejűleg rajzolható szakaszok segítségével. A könyv vastagsága (vagy a könyv vastagsága) hozzáadja azt a kényszert, hogy minden csúcsnak egy hajtáson kell lennie (könyvkötés). A fásodástól és a degeneráltságtól eltérően azonban nincs közvetlen kapcsolat e mennyiségek között [12] .

Számítási összetettség

Egy adott gráf vastagságának kiszámítása NP-nehéz , és annak ellenőrzése, hogy a vastagság legfeljebb kettő, NP-teljes [ 13] . A fássághoz való viszony azonban lehetővé teszi a vastagság közelítését 3-as közelítési tényezővel polinomidőben .

Jegyzetek

  1. ↑ Tutte, 1963 , p. 567-577.
  2. ↑ Mutzel, Odenthal, Scharbrodt, 1998 , p. 59-73.
  3. ↑ Keresztény, 2009 .
  4. ↑ Alekseev, Gonchakov, 1976 , p. 212.
  5. ↑ Mäkinen, Poranen, 2012 , p. 76-87.
  6. ↑ Petra Mutzel, Thomas Odenthal és Mark Scharbrodt, The Thickness of Graphs: A Survey Archivált 2016. március 3. a Wayback Machine -nél
  7. ↑ 1 2 Mutzel, Odenthal, Scharbrodt, 1998 .
  8. ↑ Alekseev, Gonchakov, 1976 , p. 212-230.
  9. ↑ Beineke, Harary, Moon, 1964 , p. 1-5.
  10. ↑ Dean, Hutchinson, Scheinerman, 1991 , p. 147-151.
  11. ↑ Brass et al., 2007 , p. 117-130.
  12. ↑ Eppstein, 2004 , p. 75-86.
  13. ↑ Mansfield, 1983 , p. 9-23.

Irodalom