Celulă (teoria graficelor)
O celulă n este un grafic cubic de circumferință n cu cel mai mic număr posibil de vârfuri. Un grafic se numește cubic dacă din fiecare dintre vârfurile sale ies 3 muchii. Circumferința unui grafic este lungimea celui mai mic ciclu din acesta.
Pentru fiecare 2 < n < 9 există o celulă n unică, iar toate aceste grafice sunt foarte simetrice ( unitranzitive ). În plus, atunci când sunt reprezentate într-un plan, ele oferă adesea un număr extrem de auto-intersecții, denumite în continuare indicele .
- 3 celule - K 4 , coloana vertebrală a unui tetraedru , 4 vârfuri.
- 4-celule - K 3,3 , unul dintre cele două grafice neplanare minime , 6 vârfuri.
- 5 celule - grafic Petersen , 10 vârfuri. Grafic cubic minim cu indice de auto-intersecție 2.
- 6 celule - grafic Heawood , 14 vârfuri. Descompusă în 1-factori (adică colorate cu marginile), orice sumă a doi factori formează un ciclu hamiltonian . Grafic cubic minim cu indice de auto-intersecție 3.
- 7 celule - Contele McGee , 24 de vârfuri. Grafic cubic minim cu indice de auto-intersecție 8.
- 8 celule - Contele Tatta - Coxeter , 30 de vârfuri.
Definiție generalizată
( r , n )-celula este un grafic regulat de gradul r (adică fiecare vârf are exact r muchii) și circumferința n cu cel mai mic număr posibil de vârfuri.
Familii banale
- Celulele (2, n ) sunt în mod evident grafice ciclice C n
- Celulele ( r -1,3) sunt grafice complete K r ale r vârfuri
- Celulele ( r ,4) sunt grafice bipartite complete К r , r , care au r vârfuri în fiecare parte
Reprezentanți non-triviali
- (7,5)-cell - Graficul Hoffman-Singleton , 50 de vârfuri.
Mai sunt cunoscute câteva celule. Tabelul de mai jos arată numărul de vârfuri din celulele ( r , n ) de gradul 3≤ r ≤7 și circumferința 3≤ n ≤12 . Celulele pentru acestea și mai mari r și n sunt descrise aici: [1] (în engleză).
| n : | 3 | patru | 5 | 6 | 7 | opt | 9 | zece | unsprezece | 12 |
| r =3: | patru | 6 | zece | paisprezece | 24 | treizeci | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r =4: | 5 | opt | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r =5: | 6 | zece | treizeci | 42 | 152 | 170 | 2730 | |||
| r =6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r =7: | opt | paisprezece | cincizeci | 90 |
Conții de Moore
Numărul de vârfuri din celula ( r , n ) este mai mare sau egal cu
pentru n impar și pentru chiar.
Dacă egalitatea este valabilă, atunci graficul corespunzător se numește grafic Moore . În timp ce o celulă există pentru orice r > 2 și n > 2, există mult mai puține grafice Moore non-triviale. Dintre celulele de mai sus, graficele Moore sunt graficul Petersen , graficul Heawood , graficul Tutt-Coxeter și graficul Hoffman-Singleton. S-a dovedit [1] [2] [3] că toate cazurile impare sunt epuizate cu n = 5, r = 2, 3, 7 și eventual 57, iar cazurile pare cu n = 6, 8, 12.
Note
- ↑ Bannai, E. și Ito, T. „On Moore Graphs”. J. Fac. sci. Univ. Tokyo Ser. A 20, 191-208, 1973
- ^ Damerell , R.M. „On Moore Graphs”. Proc. Cambridge Philos. soc. 74, 227-236, 1973
- ^ Hoffman, AJ și Singleton, RR „On Moore Graphs of Diameter 2 and 3.” IBM J. Res. Dezvolta. 4, 497-504, 1960
Literatură
- F. Teoria grafurilor Harari . - M .: URSS , - 2003. - 300 s - ISBN 5-354-00301-6 .
Link -uri
- Weisstein, Eric W. Cell Graph la Wolfram MathWorld .
- https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/ _