Folkmanov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m m/dp/slog |
m m/dp/slog |
||
Vrstica 16:
'''Folkmanov graf''' je v [[teorija grafov|teoriji grafov]] [[neusmerjeni graf|neusmerjeni]] [[dvodelni graf|dvodelni]] [[regularni graf|regularni graf]] [[kvartični graf|stopnje 4]] z [[20 (število)|20]]-imi [[točka (teorija grafov)|točkami]] in [[40 (število)|40]]-imi [[graf (matematika)|povezavami]]. Imenuje se po [[Jon Folkman|Jonu Folkmanu]].
Folkmanov graf je [[Hamiltonova pot|Hamiltonov graf]] in ima [[kromatično število]] 2, [[kromatični indeks]] 4, [[razdalja (teorija grafov)|premer]] 4, polmer 3 in [[obseg (teorija grafov)|notranji obseg]] 4. Je tudi 4-[[po točkah k-povezani graf|točkovno-povezan]] in [[po povezavah k-povezani graf|4-povezavno-povezan]] [[popolni graf]].
== Algebrske značilnosti ==
Folkmanov graf je [[po točkah prehodni grah|točkovno-prehoden]], ne pa tudi [[po povezavah prehodni graf|povezavno]]. Je najmanjši neusmerjeni graf, ki je točkovno-prehoden in regularen, ne pa tudi
Kot polsimetrični graf je Folkamnov graf [[dvodelni graf]] in ima [[avtomorfizem grafa|avtomorfizme]] za vsak par točk, ne pa za povezave. V spodnji upodobitvi grafa, ki kaže njegovo kromatično število, se zelene točke ne da preslikati v rdeče z nobenim avtomorfizmom. Lahko pa se preslika katerokoli rdečo točko v drugo rdečo točko, ter enako tudi zelene točke.
| |||