Szimmetrikus gráf

A matematika, azon belül a gráfelmélet területén egy G gráf akkor szimmetrikus vagy ívtranzitív (symmetric / arc-transitive) ha G bármely két, u1v1 és u2v2 csúcsszomszéd-párjára létezik olyan automorfizmus,

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus
A Petersen-gráf egy 3-reguláris szimmetrikus gráf. Bármegy két szomszédos csúcs átvihető egy másik szomszédos csúcspárba, mivel bármelyik öt csúcsból álló gyűrű átvihető bármely másikba.
f : V(G) → V(G),

melyre

f(u1) = u2 és f(v1) = v2.[1]

Más szavakkal egy gráf akkor szimmetrikus, ha automorfizmus-csoportja tranzitívan hat szomszédos csúcsok rendezett párjaira (tehát olyan éleken, melyeknek irányt tulajdonítunk).[2] Az ilyen gráfot néha 1-arc-transitive („1-ív-tranzitív”)[2] vagy flag-transitive néven is leírják.[3]

A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak csúcstranzitívnak is kell lennie.[1] Mivel a fenti definíció egy élt egy másikba visz át, a(z összefüggő) szimmetrikus gráfok szükségképpen éltranzitívak is. Egy éltranzitív gráf azonban nem feltétlenül szimmetrikus, hiszen előfordulhat, hogy ab-t átviszi cd-be, de dc-be nem. A félszimmetrikus gráfok például éltranzitívak és regulárisak, de nem csúcstranzitívak.

Minden összefüggő szimmetrikus gráf tehát csúcs- és éltranzitív egyszerre, páratlan fokszámú gráfokra ennek a megfordítása is igaz.[3] A páros fokszámú gráfok között azonban léteznek olyan él- és csúcstranzitív összefüggő gráfok, melyek nem szimmetrikusak.[4] Ezek a féltranzitív gráfok.[5] A legkisebb összefüggő féltranzitív a 4 fokszámú, 27 csúcsú Holt-gráf.[1][6] Egyes szerzők félreérthető módon a „szimmetrikus gráf” kifejezést az összes csúcs- és éltranzitív gráfra használják, nem csak az ívtranzitív gráfokra – ez a definíció a féltranzitív gráfokat is magába foglalná. A távolságtranzitív gráfoknál az automorfizmusnál nem szomszédos (tehát 1 távolságra lévő) csúcspárokat, hanem megegyező távolságra lévő két csúcspárt veszükn figyelembe. Az ilyen gráfok a definíció alapján autommatikusan szimmetrikusak is.[1]

Egy t-ív (t-arc) t+1 csúcs olyan sorozata, melyben bármely két egymást követő csúcs szomszédos, és az ismétlődő csúcsok mindig 2-nél nagyobb távolságra vannak. Egy t-tranzitív gráf vagy t-ívtranzitív gráf (t-transitive graph, t-arc-transitive graph) olyan gráf, melynek automorfizmus-csoportja tranzitíven hat a t-ívekre, de (t+1)-ívekre nem. Mivel az 1-ívek egyszerűen a gráf élei, ezért minden legalább 3 fokszámú szimmetrikus gráf t-tranzitív valamely t-re, t értéke segítségével pedig osztályozni lehet a szimmetrikus gráfokat. A kocka például 2-tranzitív.[1]

PéldákSzerkesztés

A szimmetriafeltételt a 3-regularitás elvárásával társítva már kellően erős feltételt kapunk ahhoz, hogy ezeket a ritka gráfokat listázni legyen érdemes. A Foster census („Foster-féle népszámlálás”) és kiterjesztései ilyen listákat hoztak létre.[7] Az első Foster censust 1930-ban kezdte meg az akkor a Bell Labsnál dolgozó Ronald M. Foster,[8] 1988-ban (amikor Foster 92 éves volt[1]) az akkori naprakész Foster census eredményeit (512 csúcsig az összes 3-reguláris szimmetrikus gráfot) könyv formájában is kiadták.[9] A következő listában a Foster census első tizenhárom eleme szerepel, avagy a legfeljebb 30 csúcsú 3-reguláris szimmetrikus gráfok[10][11] (ezek közül tíz egyben távolságtranzitív is, a kivételeket jelezzük):

Csúcsok Átmérő Girth Gráf Megjegyzés
4 1 3 A K4 teljes gráf távolságtranzitív, 2-tranzitív
6 2 4 A K3,3 teljes páros gráf távolságtranzitív, 3-tranzitív
8 3 4 A kocka csúcsai és élei távolságtranzitív, 2-tranzitív
10 2 5 A Petersen-gráf távolságtranzitív, 3-tranzitív
14 3 6 A Heawood-gráf távolságtranzitív, 4-tranzitív
16 4 6 A Möbius–Kantor-gráf 2-tranzitív
18 4 6 A Papposz-gráf távolságtranzitív, 3-tranzitív
20 5 5 A dodekaéder csúcsai és élei távolságtranzitív, 2-tranzitív
20 5 6 A Desargues-gráf távolságtranzitív, 3-tranzitív
24 4 6 A Nauru-gráf (a G(12,5) általánosított Petersen-gráf) 2-tranzitív
26 5 6 Az F26A-gráf[11] 1-tranzitív
28 4 7 A Coxeter-gráf távolságtranzitív, 3-tranzitív
30 4 8 A Tutte–Coxeter-gráf távolságtranzitív, 5-tranzitív

További ismert 3-reguláris szimmetrikus gráfok a Dyck-gráf, a Foster-gráf és a Biggs–Smith-gráf. A fenti tíz távolságtranzitív gráfon, továbbá a Foster-gráfon és a Biggs–Smith-gráfon kívül nem létezik több 3-reguláris távolságtranzitív gráf. A nem 3-reguláris szimmetrikus gráfok közé tartoznak a körgráfok (fokszám: 2), a teljes gráfok (fokszám>3), hiperkockagráfok (fokszám>3), valamint az oktaéder, ikozaéder, a kuboktaéder és az ikozidodekaéder gráfjai. A Rado-gráf példa a végtelen számú csúccsal és fokszámmal rendelkező szimmetrikus gráfra.

TulajdonságokSzerkesztés

Egy szimmetrikus gráf mindig d-szeresen összefüggő, ahol d a fokszám.[3] Csúcstranzitív gráfokról általában csak annyi mondható el, hogy összefüggőségük alsó korlátja 2(d+1)/3.[2] Egy legalább 3 fokszámú t-tranzitív gráf girthe legalább 2(t–1). Nem létezik viszont véges, legalább 3 fokszámú t-tranzitív gráf a t ≥ 8 értékekre. Ha a fokszám pontosan 3, akkor már t ≥ 6-ra sem.

Kapcsolódó szócikkekSzerkesztés

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Symmetric graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. a b c d e f Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118–140. o. (1993). ISBN 0-521-45897-8 
  2. a b c Algebraic Graph Theory. New York: Springer, 59. o. (2001). ISBN 0-387-95220-9 
  3. a b c Babai, L. Handbook of Combinatorics. Elsevier (1996) 
  4. Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
  5. Handbook of Graph Theory. CRC Press, 491. o. (2004). ISBN 1-58488-090-2 
  6. Holt, Derek F. (1981). „A graph which is edge transitive but not arc transitive”. Journal of Graph Theory 5 (2), 201–204. o. DOI:10.1002/jgt.3190050210.  .
  7. Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
  8. Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
  9. "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
  10. Biggs, p. 148
  11. a b Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

További információkSzerkesztés