Universal graf

En universel graf er en uendelig graf, der indeholder enhver endelig (eller højst tællig ) graf som en genereret undergraf . En universel graf af denne type blev først konstrueret af R. Rado [1] [2] og denne graf kaldes nu Rado-grafen eller tilfældig graf. Nyere værker [3] [4] fokuserer på universelle grafer for graffamilien F . Det vil sige en uendelig graf, der tilhører F , der indeholder alle endelige grafer i familien F. For eksempel er Hanson-grafer universelle i denne forstand for grafer udenjeg -klikker.

En universel graf for en graffamilie F kan også forstås som et medlem af en række af endelige grafer, der indeholder alle grafer fra F . For eksempel er ethvert endeligt træ en undergraf af en tilstrækkelig stor hyperkubegraf [5] til at hyperkuben kan siges at være en universel graf for træer. Dette er dog ikke den mindste sådan graf - det er kendt, at der er en universel graf for træer med n toppunkter, der kun indeholder n toppunkter og O( n  log  n ) kanter, og denne graf er optimal [6] . En konstruktion baseret på planar partitionssætningen kan bruges til at vise, at plane grafer med n toppunkter har universelle grafer med O( n 3/2 ) kanter, og at plane grafer af afgrænset grad har universelle grafer med O( n  log  n ) kanter [7] [8] [9] . Sumners formodning siger, at turneringer er universelle for polytræer i den forstand, at enhver turnering med 2n  − 2 hjørner indeholder et hvilket som helst polytræ med n hjørner som et undertræ [10] .

En graffamilie F har en universel graf i polynomisk størrelse, der indeholder enhver graf med n hjørner som en genereret undergraf, hvis og kun hvis den har et tilstødende mærkningsskema , hvor hjørnerne kan mærkes med O (log  n ) -bit strenge sådan på en sådan måde, at algoritmen kan bestemme, om knudepunkter støder op til etiketterne for disse knudepunkter. Hvis der findes en graf af denne type, kan hjørnerne af enhver graf i F mærkes med etiketter af de tilsvarende spidser på den universelle graf, og omvendt, hvis der findes et mærkningsskema, kan en universel graf konstrueres indeholdende alle mulige etiketter [ 11] .

I ældre matematisk terminologi blev udtrykket "universel graf" nogle gange brugt til en komplet graf .

Noter

  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 Arkiveret 27. februar 2014 på Wayback Machine , Douglas B. West, hentet 2010-09-17.
  11. ↑ Kannan, Naor, Rudich, 1992 , s. 596-603.

Litteratur

Links