Kletka (teorija grafov)
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:

 

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

 

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 

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:

 (3,5)-kletka: Petersenov graf, 10 točk
 (3,6)-kletka: Heawoodov graf, 14 točk
 (3,8)-kletka: Tutte-Coxetrov graf, 30 točk
 (7,5)-kletka: Hoffman-Singletonov graf, 50 točk.

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

Zunanje povezave 

 Brouwer, Andries Evert, Cages 
 

Družine grafov
Regularni grafi
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 ≥in g ≥ ( 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 : točk , in vsaka kletka s sodim notranjim obsegom g mora imeti vsaj : 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 neizomorfne10) - kletke , vsaka stočkami : Balabanovakletka , Harriesov graf in Harries - Wongov graf. Obstaja pa le ena11) - kletka : Balabanovakletka ( stočkami ) . Znane kletke Graf stopnjenima cikla , notranji obseg povezanih grafov stopnjeje enak številu njihovih točk , tako da so zanimive le kletke za r ≥ ( r ,3 ) - kletka je polni graf Kr+1 na r+1 točkah , ( r ,4 ) - kletka pa je polni dvodelni graf Kr,r na točkah . Druge pomembne kletke vsebujejo Mooreove grafe : 5) - kletka : Petersenov graf ,točk 6) - kletka : Heawoodov graf ,točk 8) - kletka : Tutte - Coxetrov graf ,točk 5) - kletka : Hoffman - Singletonov graf ,točk . Število točk v znanih ( r ,g ) - kletkah za vrednosti r >in g > so : Zunanje povezave Brouwer , Andries Evert , Cages Družine grafov Regularni grafi