Kletka (teorija grafov)

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

Klétka je v teoriji grafov regularni graf, ki ima za svoj dani notranji obseg najmanjše možno število točk.

Formalno je (r,g)-graf določen kot graf v katerem ima vsaka točka točno r sosednjih točk, in v katerem ima najkrajši cikel dolžino točno g. Znano je, da (r,g)-graf obstaja za vsako kombinacijo r ≥ 2 in g ≥ 3. (r,g)-kletka je (r,g)-graf z najmanjšim možnim številom točk med vsemi (r,g)-grafi.

Če obstaja Mooreov graf stopnje r in notranjim obsegom g, mora biti kletka. Velja še naprej, meje velikosti Mooreovih grafov se posplošijo na kletke. Vsaka kletka z lihim notranjim obsegom g mora imeti vsaj:

 1+r\sum_{i=0}^{(g-3)/2}(r-1)^{i} \!\,

točk, in vsaka kletka s sodim notranjim obsegom g mora imeti vsaj:

 2\sum_{i=0}^{(g-2)/2}(r-1)^{i} \!\,

točk. Vsak (r,g)-graf s točno toliko točkami je po definiciji Mooreov graf in s tem tudi kletka.

Za dano kombinacijo r in g lahko obstaja več kletk. Obstajajo na primer tri neizomorfne (3,10)-kletke, vsaka s 70 točkami: Balabanova 10-kletka, Harriesov graf in Harries-Wongov graf. Obstaja pa le ena (3,11)-kletka: Balabanova 11-kletka (s 112 točkami).

Znane kletke[uredi | uredi kodo]

Graf stopnje 1 nima cikla, notranji obseg povezanih grafov stopnje 2 je enak številu njihovih točk, tako da so zanimive le kletke za r ≥ 3. (r,3)-kletka je polni graf Kr+1 na r+1 točkah, (r,4)-kletka pa je polni dvodelni graf Kr,r na 2r točkah.

Druge pomembne kletke vsebujejo Mooreove grafe:

Število točk v znanih (r,g)-kletkah za vrednosti r > 2 in g > 2, so:

g: 3 4 5 6 7 8 9 10 11 12
r = 3: 4 6 10 14 24 30 58 70 112 126
r = 4: 5 8 19 26 67 80 728
r = 5: 6 10 30 42 170 2730
r = 6: 7 12 40 62 312 7812
r = 7: 8 14 50 90

Zunanje povezave[uredi | uredi kodo]