Obseg (teorija grafov)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Obseg v teoriji grafov pomeni dva pojma. Notranji obseg (angleško girth) grafa je dolžina njegovega najkrajšega cikla.[1][2] Če graf ne vsebuje ciklov (je aciklični graf), je njegov notranji obseg po definiciji enak neskončnosti. Notranji obseg 4-cikla (kvadrata) je 4. Notranji obseg mreže je tudi enak 4, trikotniške mreže pa enak 3. Graf z notranjih obsegom večjim od 3 nima trikotnikov. Zunanji obseg (angleško circumference) grafa je dolžina njegovega najdaljšega cikla.[2] Obsega predstavljata invarianti grafa.

Kletke[uredi | uredi kodo]

Kubični graf (vse njegove točke imajo stopnjo 3) z notranjim obsegom g, ki je majhen kolikor je mogoče, je znan kot g-kletka (ali kot (3,g)-kletka). Petersenov graf je edina 5-kletka (je najmanjši kubični graf z notranjim obsegom 5), Heawoodov graf je edina 6-kletka, McGeejev graf je edina 7-kletka, Tuttejeva osmera kletka pa je edina 8-kletka.[3] Za dani notranji obseg lahko obstaja več kletk. Obstajajo na primer tri neizomorfne 10-kletke, vsaka s 70-timi točkami: Balabanova 10-kletka, Harriesov graf in Harries-Wongov graf.

Notranji obseg in barvanje grafa[uredi | uredi kodo]

Za poljubni pozitivni celi števili g in χ obstaja graf z notranjim obsegom vsaj g in kromatičnim številom vsaj χ. Grötzschev graf na primer nima trikotnikov, njegovo kromatično število je enako 4. S ponavljanjem konstrukcije Mycielskega lahko iz Grötzschevega grafa dobimo grafe brez trikotnikov s poljubno velikim kromatičnim številom. Paul Erdős je prvi dokazal splošni rezultat s pomočjo verjetnostne metode.[4] Pokazal je, da naključni graf na n točkah, ki je nastal z neodvisno izbiro vsake povezave z verjetnostjo n(1 − g)/g, ima, če verjetnost teži k 1, ko gre n k neskončnosti, največ n/2 ciklov dolžine g ali manj, vendar nima neodvisne množice velikosti n/2k. Če odstranimo eno točko iz vsakega kratkega cikla, zato dobimo manjši graf z notranjim obsegom večjim od g, v katerem mora biti vsak barvni razred barvanja majhen in zaradi tega potrebuje vsaj k barv v vsakem barvanju.

Posplošitve[uredi | uredi kodo]

Lihi notranji obseg in sodi notranji obseg grafa sta dolžini najkrajšega lihega cikla in najkrajšega sodega cikla.

Prek najmanjše dolžine netrivialnega cikla notranji obseg dovoljuje naravne posplošitve 1-sistol ali sistol višjih redov v sistolični geometriji.

Opombe in sklici[uredi | uredi kodo]

  1. ^ Diestel (2010).
  2. ^ 2,0 2,1 Wilson, Watkins (1997), str. 58.
  3. ^ Brouwer (1989).
  4. ^ Erdős (1959).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]