Razlika između inačica stranice »Automorfizam grafa«
(Bot: Automatski unos stranica) |
m (bnz) |
||
| Redak 1: | Redak 1: | ||
'''Automorfizam grafa''', svojstvo [[graf (teorija grafova)|grafa]] u [[teorija grafova|teoriji grafova]]. Predstavlja [[permutacija|permutaciju]] skupa [[vrh (teorija grafova)|vrhova]] <math>V(G)</math> koja čuva [[Susjednost (teorija grafova)|susjednost]]. Grupa automorfizama <math>Aut(P)</math> [[Petersenov graf|Petersenova grafa]] je [[simetričnost (teorija grafova)|simetrična]] grupa <math>S_{5}</math> te je ukupan broj automorfizama jednak 120. Po [[Lovaszova slutnja|Lovaszoj slutnji]], graf <math>G</math> je [[tranzitivnost (teorija grafova)|tranzitivan]] po vrhovima ako za svaki par vrhova <math>u</math> i <math>v</math> iz <math>G</math> postoji [[automorfizam]] na <math>G</math> koji [[preslikavanje|preslikava]] <math>u</math> u <math>v</math>. Još uvijek nije otkriven niti jedan graf koji je tranzitivan po vrhovima, a da nema [[Hamiltonov put|Hamiltonov]] [[Put (teorija grafova)|put]]. Slutnja se pokazala točnom za razne klase grafova, no još uvijek nije pronađen dokaz. <ref name="Majstorović, Boras">[http://e.math.hr/vol27/majstorovic math.e] Snježana Majstorović i Luka Boras: ''Petersenov graf'', br. 27. (pristupljeno 25. svibnja 2020.)</ref> | |||
== Vidi == | == Vidi == | ||
Trenutačna izmjena od 10:42, 8. svibnja 2022.
Automorfizam grafa, svojstvo grafa u teoriji grafova. Predstavlja permutaciju skupa vrhova [math]\displaystyle{ V(G) }[/math] koja čuva susjednost. Grupa automorfizama [math]\displaystyle{ Aut(P) }[/math] Petersenova grafa je simetrična grupa [math]\displaystyle{ S_{5} }[/math] te je ukupan broj automorfizama jednak 120. Po Lovaszoj slutnji, graf [math]\displaystyle{ G }[/math] je tranzitivan po vrhovima ako za svaki par vrhova [math]\displaystyle{ u }[/math] i [math]\displaystyle{ v }[/math] iz [math]\displaystyle{ G }[/math] postoji automorfizam na [math]\displaystyle{ G }[/math] koji preslikava [math]\displaystyle{ u }[/math] u [math]\displaystyle{ v }[/math]. Još uvijek nije otkriven niti jedan graf koji je tranzitivan po vrhovima, a da nema Hamiltonov put. Slutnja se pokazala točnom za razne klase grafova, no još uvijek nije pronađen dokaz. [1]