Heawoodov graf
| Heawoodov graf | |
|---|---|
 |
|
| Ime | Percy John Heawood |
| Točke | 14 |
| Povezave | 21 |
| Polmer | 3 |
| Premer | 3 |
| Notranji obseg | 6 |
| Avtomorfizem | 336 (PGL2(7)) |
| Kromatično število | 2 |
| Kromatični indeks | 3 |
| Značilnosti | kubičen kletka razdaljno-prehoden razdaljno-regularen toroiden Hamiltonov simetričen z enotsko razdaljo |
Heawoodov graf je v teoriji grafov neusmerjeni graf s 14 točkami in 21 povezavami. Graf je kubičen, vsi cikli v njem pa imajo šest ali več povezav. Vsak manjši kubični graf ima krajše cikle, tako da je ta graf (3,6)-kletka, najmanjši kubični graf z notranjim obsegom enakim 6. Je tudi Levijev graf Fanojeve ravnine, graf, ki predstavlja incidence med točkami in premicami v tej geometriji. Heawoodov graf je razdaljno-regularen; njegova grupa avtomorfizmov je PGL2(7).[1]
Heawoodov graf se imenuje po britanskem matematiku Percyju Johnu Heawoodu, ki je leta 1890 dokazal, da lahko vsako subdivizijo torusa v mnogokotnike obarvamo z največ sedmimi barvami.[2][3] Heawoodov graf tvori subdivizijo torusa s sedmimi medsebojno sosedskimi območji, in kaže da je ta vez močna.
Opombe in sklici [uredi]
- ^ Brouwer, Andries Evert. Heawood graph. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).
- ^ Brown (2002).
- ^ Heawood (1890).
Viri [uredi]
- Brown, Ezra (2002). "The many names of (7,3,1)". Mathematics Magazine 75 (2): 83–94. doi:10.2307/3219140. http://www.math.vt.edu/people/brown/doc/731.pdf.
- Heawood, Percy John (1890). "Map colouring theorems". Quarterly J. Math. Oxford Ser. 24: 322–339.
Zunanje povezave [uredi]
- Heawood Graph na MathWorld (v angleščini)
 |
Ta matematični članek je škrbina. Pomagaj Wikipediji in ga razširi. |
