Folkmanov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
Nš |
m dp/slog |
||
Vrstica 14:
}}
'''Folkmanov graf''' je v [[teorija grafov|teoriji grafov]] [[neusmerjeni graf|neusmerjeni]] [[dvodelni graf|dvodelni]] [[regularni graf|regularni graf stopnje 4]] z 20 [[točka (teorija grafov)|točkami]] in 40 [[povezava (teorija grafov)|povezavami]]. Imenuje se po [[Jon Folkman|Jonu Folkmanu]].
Folkmanov graf je [[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|povezan]] in [[po povezavah k-povezani graf|po povezavah 4-povezan]] [[popolni graf]].
Vrstica 20:
== Algebrske značilnosti ==
Folkmanov graf je [[po točkah prehodni grah|po točkah prehoden]], ne pa tudi [[po povezavah prehodni graf|po povezavah]]. Je najmanjši
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, zelene točke ne moremo preslikati v rdeče s katerikoli avtomorfizmom. Lahko pa preslikamo katerokoli rdečo točko v drugo rdečo točko, ter enako tudi zelene točke.
| |||