Buňka (teorie grafů)
N-buňka je kubický graf obvodu n s nejmenším možným počtem vrcholů. Graf se nazývá kubický , pokud z každého jeho vrcholu vystupují 3 hrany. Obvod grafu je délka nejmenšího cyklu v grafu.
Pro každé 2 < n < 9 existuje jedinečná n-buňka a všechny tyto grafy jsou vysoce symetrické ( jednotranzitivní ). Navíc, když jsou zobrazeny v rovině, často dávají extrémní počet vlastních průniků, dále jen index samoprůniků .
- 3-článkový - K 4 , páteř čtyřstěnu , 4 vrcholy.
- 4-buňkový - K 3,3 , jeden ze dvou minimálních nerovinných grafů, 6 vrcholů.
- 5-článkový - Petersenův graf , 10 vrcholů. Minimální kubický graf s indexem vlastního průniku 2.
- 6-článkový - Heawoodův graf , 14 vrcholů. Rozložený do 1-faktorů (tj. obarvených hranou) tvoří jakýkoli součet dvou faktorů hamiltonovský cyklus . Minimální kubický graf s indexem vlastního průniku 3.
- 7-článkový - Count McGee , 24 vrcholů. Minimální kubický graf s indexem vlastního průniku 8.
- 8článkový - Count Tatta - Coxeter , 30 vrcholů.
Zobecněná definice
( r , n )-buňka je pravidelný graf stupně r (to znamená, že každý vrchol má právě r hran) a obvodu n s nejmenším možným počtem vrcholů.
Triviální rodiny
- (2, n )-buňky jsou zjevně cyklické grafy C n
- ( r -1,3)-buňky jsou úplné grafy K r r vrcholů
- ( r ,4)-buňky jsou úplné bipartitní grafy К r , r , které mají v každé části r vrcholů
Netriviální představitelé
- (7,5)-buňka - Hoffman-Singletonův graf , 50 vrcholů.
Některé další buňky jsou známy. Níže uvedená tabulka ukazuje počet vrcholů v ( r , n )-buňkách stupně 3≤ r ≤7 a obvodu 3≤ n ≤12 . Buňky pro tyto a větší r a n jsou popsány zde: [1] (v angličtině).
| n : | 3 | čtyři | 5 | 6 | 7 | osm | 9 | deset | jedenáct | 12 |
| r = 3: | čtyři | 6 | deset | čtrnáct | 24 | třicet | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | osm | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r = 5: | 6 | deset | třicet | 42 | 152 | 170 | 2730 | |||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r = 7: | osm | čtrnáct | padesáti | 90 |
Counts of Moore
Počet vrcholů v ( r , n )-buňce je větší nebo roven
pro liché n a pro dokonce.
Pokud platí rovnost, pak se odpovídající graf nazývá Mooreův graf . Zatímco buňka existuje pro libovolné r > 2 an > 2, existuje mnohem méně netriviálních Moorových grafů. Z výše uvedených buněk jsou Mooreovy grafy Petersenův graf, Heawoodův graf , Tutt -Coxeterův graf a Hoffman-Singletonův graf. Bylo prokázáno [1] [2] [3] , že všechny liché případy jsou vyčerpány o n = 5, r = 2, 3, 7 a případně 57 a sudé případy o n = 6, 8, 12.
Poznámky
- ↑ Bannai, E. a Ito, T. "On Moore Graphs." J. Fac. sci. Univ. Tokyo Ser. A 20, 191-208, 1973
- ↑ Damerell, R. M. "On Moore Graphs." Proč. Cambridge Philos. soc. 74, 227-236, 1973
- ↑ Hoffman, AJ a Singleton, RR "O Moore Graphs of Diameter 2 and 3." IBM J. Res. Rozvíjet. 4, 497-504, 1960
Literatura
- F. Harari teorie grafů . - M .: URSS , - 2003. - 300 s - ISBN 5-354-00301-6 .
Odkazy
- Weisstein, Eric W. Cell Graph ve společnosti Wolfram MathWorld .
- https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/ _