Obseg (teorija grafov)
Obseg v teoriji grafov pomeni dva pojma. Notranji obseg () grafa je dolžina njegovega najkrajšega cikla. Č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. Obsega predstavljata invarianti grafa.

Kletke 

Kubični graf (vse njegove točke imajo stopnjo 3) z notranjim obsegom , ki je majhen kolikor je mogoče, je znan kot -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. 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 

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. 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 

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.

Sklici

Viri 

 . Elektronski dodatek knjigi Distance-Regular Graphs (Brouwer, Cohen in Neumaier 1989, Springer-Verlag).

Zunanje povezave 

 

Invariante grafov
Obseg v teoriji grafov pomeni dva pojma . Notranji obseg ( ) grafa je dolžina njegovega najkrajšega cikla . Če graf ne vsebuje ciklov ( je aciklični graf ) , je njegov notranji obseg po definiciji enak neskončnosti . Notranji obsegcikla ( kvadrata ) je Notranji obseg mreže je tudi enak trikotniške mreže pa enak Graf z notranjih obsegom večjim odnima trikotnikov . Zunanji obseg ( angleško circumference ) grafa je dolžina njegovega najdaljšega cikla . Obsega predstavljata invarianti grafa . Kletke Kubični graf ( vse njegove točke imajo stopnjoz notranjim obsegom , ki je majhen kolikor je mogoče , je znan kot - kletka ( ali kotg ) - kletka ) . Petersenov graf je edinakletka ( je najmanjši kubični graf z notranjim obsegom Heawoodov graf je edinakletka , McGeejev graf je edinakletka , Tuttejeva osmera kletka pa je edinakletka . Za dani notranji obseg lahko obstaja več kletk . Obstajajo na primer tri neizomorfnekletke , vsaka stimi točkami : Balabanovakletka , Harriesov graf in Harries - Wongov graf. Notranji obseg in barvanje grafa 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 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 . 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 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 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šitvesistol ali sistol višjih redov v sistolični geometriji . Sklici Viri \ . Elektronski dodatek knjigi Distance - Regular Graphs ( Brouwer , Cohen in Neumaier Springer - Verlag ) . Zunanje povezave Invariante grafov