„Szimmetrikus gráf” változatai közötti eltérés

Adjon hozzá 1 könyvet a forráshoz (20210114)) #IABot (v2.0.7) (GreenC bot
a (gondolatjel javítása (checkwiki [050]) AWB)
(Adjon hozzá 1 könyvet a forráshoz (20210114)) #IABot (v2.0.7) (GreenC bot)
:''f''(''u''<sub>1</sub>) = ''u''<sub>2</sub> és ''f''(''v''<sub>1</sub>) = ''v''<sub>2</sub>.<ref name="biggs">{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | pages=118–140 | isbn=0-521-45897-8}}</ref>
 
Más szavakkal egy gráf akkor szimmetrikus, ha automorfizmus-csoportja [[csoporthatás|tranzitívan hat]] szomszédos csúcsok rendezett párjaira (tehát olyan éleken, melyeknek irányt tulajdonítunk).<ref name="godsil">{{cite book |first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|url=https://archive.org/details/algebraicgraphth00gods| location=New York| publisher=Springer | year=2001 | page=[https://archive.org/details/algebraicgraphth00gods/page/n79 59] | isbn=0-387-95220-9}}</ref> Az ilyen gráfot néha '''1-arc-transitive''' („1-ív-tranzitív”)<ref name="godsil"/> vagy '''flag-transitive''' néven is leírják.<ref name="babai">{{Cite book | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last = Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = Handbook of Combinatorics | contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps | year = 1996 | publisher = Elsevier}}</ref>
 
A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak [[csúcstranzitív gráf|csúcstranzitívnak]] is kell lennie.<ref name="biggs" /> Mivel a fenti definíció egy élt egy másikba visz át, a(z összefüggő) szimmetrikus gráfok szükségképpen [[éltranzitív gráf|éltranzitívak]] is. Egy éltranzitív gráf azonban nem feltétlenül szimmetrikus, hiszen előfordulhat, hogy ''a''—''b''-t átviszi ''c''—''d''-be, de ''d''—''c''-be nem. A [[félszimmetrikus gráf]]ok például éltranzitívak és [[reguláris gráf|regulárisak]], de nem csúcstranzitívak.
297 325

szerkesztés