Wikipedija

Folkmanov graf: Razlika med redakcijama

Pregledujte zgodovino interaktivno
← Starejše urejanjeNovejše urejanje →
Izbrisana vsebina Dodana vsebina
VizualnoVikibesedilo
m m/dp/slog
Vrstica 20:
== Algebrske značilnosti ==
 
Folkmanov graf je [[po točkah prehodni grahgraf|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 povezavno-prehoden.<ref>{{sktxt|Skiena|1990|pp=186-187}}.</ref> Takšni grafi se imenujejo [[polsimetrični graf]]i. Prvi jih je raziskoval Folkman leta 1967 in odkril graf z 20-imi točkami, sedaj imenovan po njem.<ref>{{sktxt|Folkman|1967}}.</ref>
 
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.
Pridobljeno iz »https://sl.wikipedia.org/wiki/Folkmanov_graf«