Univerzális grafikon

Az univerzális gráf egy végtelen gráf , amely bármely véges (vagy legfeljebb megszámlálható ) gráfot generált részgráfként tartalmaz . Az ilyen típusú univerzális gráfot először R. Rado [1] [2] szerkesztette meg , és ezt a gráfot ma Rado gráfnak vagy véletlen gráfnak nevezik. Az újabb munkák [3] [4] az F gráfcsalád univerzális gráfjaira összpontosítanak . Vagyis egy F-hez tartozó végtelen gráf, amely tartalmazza az F család összes véges gráfját . Például a Hanson-gráfok ebben az értelemben univerzálisak az i -klikk nélküli gráfokhoz.

Az F gráfcsalád univerzális gráfja úgy is felfogható, mint egy véges gráfok sorozatának tagja, amely tartalmazza az F -ből származó összes gráfot . Például bármely véges fa egy kellően nagy hiperkocka gráf részgráfja [5] ahhoz, hogy a hiperkocka univerzális fák gráfjának mondható legyen. Ez azonban nem a legkisebb ilyen gráf - ismert, hogy létezik egy univerzális gráf n csúcsú fákra, amelyek csak n csúcsot és O( n  log  n ) éleket tartalmaznak, és ez a gráf optimális [6] . A síkbeli felosztási tételen alapuló konstrukció segítségével kimutatható, hogy az n csúcsú síkgráfoknak O ( n 3/2 ) élű univerzális gráfoknak vannak, a korlátos fokú síkgráfoknak pedig O( n  log  n ) élűek univerzális gráfok. [7] [8] [9] . Sumner sejtése szerint a versenyek univerzálisak a polifák számára , abban az értelemben, hogy minden 2n  − 2 csúcsú verseny minden n csúcsú polifát tartalmaz részfaként [10] .

Egy F gráfcsaládnak van egy polinom méretű univerzális gráfja, amely bármely n csúcsú gráfot tartalmaz generált részgráfként, akkor és csak akkor, ha van egy szomszédos címkézési séma , amelyben a csúcsok O (log  n ) bites karakterláncokkal címkézhetők. oly módon, hogy az algoritmus meg tudja határozni, hogy a csúcsok szomszédosak-e az adott csúcsok címkéivel. Ha létezik ilyen típusú gráf, akkor az F -beli bármely gráf csúcsai felcímkézhetők az univerzális gráf megfelelő csúcsainak címkéivel, és fordítva, ha létezik címkézési séma, akkor egy univerzális gráf szerkeszthető, amely az összes lehetséges címkét tartalmazza [ 11] .

A régebbi matematikai terminológiában az "univerzális gráf" kifejezést néha teljes gráfra használták .

Jegyzetek

  1. ↑ Rado, 1964 , p. 331–340.
  2. ↑ Rado, 1967 , p. 83–85.
  3. ↑ Goldstern, Kojman, 1996 , p. 319–326.
  4. ↑ Cherlin, Shelah, Shi, 1999 , p. 454–491.
  5. ↑ Wu, 1985 , p. 238–249.
  6. ↑ Chung, Graham, 1983 , p. 203–211.
  7. ↑ Babai, Chung, Erdős, Graham, Spencer, 1982 , p. 21–26.
  8. ↑ Bhatt, Chung, Leighton, Rosenberg 1989 , p. 145.
  9. ↑ Chung, 1990 , p. 17–34.
  10. ↑ Sumner's Universal Tournament Conjecture archiválva : 2014. február 27., a Wayback Machine , Douglas B. West, letöltve: 2010-09-17.
  11. ↑ Kannan, Naor, Rudich, 1992 , p. 596–603.

Irodalom

Linkek