Folkmanov graf: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina
m Bot: Popravljanje preusmeritev
m m/dp/slog
Vrstica 11:
| chromatic_number = 2
| chromatic_index = 4
| properties = 4-[[regularni graf|regularen]] <br /> ([[kvartični graf|kvartičen]]) <br /> [[dvodelni graf|dvodelen]] <br /> [[polsimetrični graf|polsimetričen]] <br /> [[Eulerjev graf|Eulerjev]] <br /> [[Hamiltonova pot|Hamiltonov]] <br /> [[popolni graf|popoln]]
}}
 
'''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|povezan]] in [[po povezavah k-povezani graf|4-povezavno-povezan]] [[popolni graf]].
Vrstica 20:
== 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 poezavno-prehoden.<ref>{{sktxt|Skiena (|1990), str. |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 moremoda preslikati v rdeče z nobenim avtomorfizmom. Lahko pa preslikamose preslika katerokoli rdečo točko v drugo rdečo točko, ter enako tudi zelene točke.
 
Folkmanov graf ima 8 različnih posplošenih [[zapis LCF|zapisov LCF]], tri z eksponentom 5 in pet z eksponentom 1.
Vrstica 33:
 
<gallery>
Slika:Folkman graph.svg|[[Kromatično število]] Folkmanovega grafa je 2.
Slika:Folkman graph 4color edge.svg|[[Kromatični indeks]] Folkmanovega grafa je 4.
Slika:Folkman graph hamiltonian.svg|Folkmanov graf je [[Hamiltonova pot|Hamiltonov graf]].
</gallery>
 
== Opombe in skliciSklici ==
 
{{opombesklici|2}}
 
== Viri ==
 
* {{navedi revijocitat|lastlast1= Folkman|firstfirst1= Jon|authorlinkauthorlink1= Jon Folkman|title= Regular line-symmetric graphs|journal= [[Journal of Combinatorial Theory|J. Combin. Th.]]|date= 1967|volume= 3|yearissue=1967 |pages= 215–232|doi= 10.1016/S0021-9800(67)80069-3|ref= harv}}
* {{navedi knjigocitat|lastlast1= Skiena|firstfirst1= S.|title= Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica|date= 1990|publisher= Addison-Wesley|location= Reading, MA|yearref=1990 harv}}
 
== Zunanje povezave ==
 
{{kategorija v Zbirki|Folkman graph}}
* [http://mathworld.wolfram.com/{{MathWorld|id=FolkmanGraph.html |title=Folkman Graph] na [[MathWolrd]] {{ikona en}}
 
{{math-stub}}