Universaali kaavio

Universaali graafi on ääretön graafi , joka sisältää minkä tahansa äärellisen (tai korkeintaan laskettavan ) graafin generoituna osagraafina . Tämän tyyppisen universaalin graafin rakensi ensin R. Rado [1] [2] ja tätä graafia kutsutaan nykyään Rado-graafiksi tai satunnaisgraafiksi. Uusimmat työt [3] [4] keskittyvät graafiperheen F universaaleihin kuvaajiin . Toisin sanoen ryhmään F kuuluva ääretön graafi, joka sisältää kaikki perheen F äärelliset graafit. Esimerkiksi Hanson -graafit ovat tässä mielessä universaaleja kaavioille, joissa ei ole i -klikejä.

Graafiperheen F universaali graafi voidaan ymmärtää myös äärellisten graafien sarjan jäsenenä, joka sisältää kaikki graafit F :stä . Esimerkiksi mikä tahansa äärellinen puu on riittävän suuren hyperkuutiograafin aligraafi [5] , jotta hyperkuution voidaan sanoa olevan puille universaali graafi. Tämä ei kuitenkaan ole pienin tällainen graafi - tiedetään, että n -pisteisille puille on olemassa universaali graafi , joka sisältää vain n kärkeä ja O( n  log  n ) reunaa, ja tämä graafi on optimaalinen [6] . Tasoosiolauseeseen perustuvaa konstruktiota voidaan käyttää osoittamaan, että tasograafissa , jossa on n kärkeä, on universaaleja graafia, joissa on O( n 3/2 ) reunat, ja että tasograafisilla, joiden aste on rajattu, on universaaleja graafia, joissa on O( n  log  n ) reunat . [7] [8] [9] . Sumnerin olettamus väittää, että turnaukset ovat universaaleja polypuille siinä mielessä, että kaikki turnaukset, joissa on 2n  − 2 kärkeä, sisältävät minkä tahansa polypuun, jossa on n kärkeä alipuuna [10] .

Graafiperheellä F on polynomikokoinen universaali graafi, joka sisältää minkä tahansa graafin, jossa on n kärkeä generoituna osagraafina, jos ja vain, jos sillä on viereinen merkintäkaavio , jossa kärjet voidaan merkitä O (log  n ) -bittillä . siten, että algoritmi voi määrittää, ovatko kärjet vierekkäin näiden kärkien nimillä. Jos tämän tyyppinen graafi on olemassa, minkä tahansa F :n graafin kärjet voidaan merkitä universaalin graafin vastaavien pisteiden nimillä, ja päinvastoin, jos merkintäkaavio on olemassa, voidaan rakentaa universaali graafi, joka sisältää kaikki mahdolliset tunnisteet [ 11] .

Vanhemmassa matemaattisessa terminologiassa ilmaisua "universal graph" käytettiin joskus täydellisestä kaaviosta .

Muistiinpanot

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

Kirjallisuus

Linkit