Symetrický graf - Symmetric graph

The Petersenův graf je (krychlový ) symetrický graf. Libovolný pár sousedních vrcholů může být mapován na jiný pomocí automorfismus, protože jakýkoli kruh pěti vrcholů lze mapovat na jakýkoli jiný.

V matematický pole teorie grafů, a graf G je symetrický (nebo oblouk-tranzitivní) pokud, vzhledem k jakýmkoli dvěma párům sousedních vrcholů u1—proti1 a u2—proti2 z G, tady je automorfismus

F : PROTI(G) → PROTI(G)

takhle

F(u1) = u2 a F(proti1) = proti2.[1]

Jinými slovy, graf je symetrický, pokud je automorfická skupina činy přechodně na uspořádaných párech sousedních vrcholů (tj. na hranách považovaných za mající směr).[2] Takový graf se někdy také nazývá 1-oblouk-tranzitivní[2] nebo vlajka-tranzitivní.[3]

Podle definice (ignorování u1 a u2), symetrický graf bez izolované vrcholy také musí být vrchol-tranzitivní.[1] Protože výše uvedená definice mapuje jednu hranu na druhou, musí být také symetrický graf hrana tranzitivní. Okrajový přechodový graf však nemusí být symetrický A—b může mapovat na C—d, ale ne d—C. Hvězdné grafy jsou jednoduchým příkladem přechodu hrany bez přechodu vrcholem nebo symetrie. Jako další příklad polosymetrické grafy jsou hranové tranzitivní a pravidelný, ale ne vrcholný.

Skupiny grafů definované jejich automorfismy
vzdálenost-tranzitivní→vzdálenost-pravidelná←velmi pravidelné
↓
symetrický (oblouk-tranzitivní)←t-tranzitivní, t ≥ 2šikmo symetrický
↓
(je-li připojen)
vrchol a hrana-tranzitivní		→hrana-tranzitivní a pravidelná→hrana tranzitivní
↓↓↓
vrchol-tranzitivní→pravidelný→(pokud je bipartitní)
biregular
↑
Cayleyův graf←nulově symetrickýasymetrický

Každý připojeno symetrický graf tedy musí být jak vrcholný, tak okrajový, a obráceně platí pro grafy zvláštní stupeň.[3] Nicméně pro dokonce stupně existují propojené grafy, které jsou vrcholné a hraniční, ale nejsou symetrické.[4] Takové grafy se nazývají napůl tranzitivní.[5] Nejmenší připojený poloviční tranzitivní graf je Holtův graf, s vrcholy stupně 4 a 27.[1][6] Matoucím způsobem někteří autoři používají termín „symetrický graf“ ve smyslu grafu, který je vrcholný a přechodný, spíše než obloukový. Taková definice by zahrnovala poloviční tranzitivní grafy, které jsou z výše uvedené definice vyloučeny.

A vzdálenost-tranzitivní graf je jeden, kde namísto uvažování párů sousedních vrcholů (tj. vrcholů ve vzdálenosti 1 od sebe) definice pokrývá dva páry vrcholů, každý se stejnou vzdáleností od sebe. Takové grafy jsou automaticky symetrické, podle definice.[1]

A t-arc je definován jako a sekvence z t + 1 vrcholy, takže libovolné dva po sobě jdoucí vrcholy v sekvenci sousedí a jakékoli opakované vrcholy jsou od sebe vzdáleny více než 2 kroky. A t- přechodný graf je graf, na který skupina automorfismu působí přechodně t-arcs, ale ne na (t + 1) -arcs. Protože 1-oblouky jsou jednoduše hrany, musí být každý symetrický graf stupně 3 nebo více t- pro některé přechodné ta hodnota t lze použít k další klasifikaci symetrických grafů. Kostka je například 2-tranzitivní.[1]

Příklady

Kombinace podmínky symetrie s omezením, které grafy mají krychlový (tj. všechny vrcholy mají stupeň 3) poskytuje poměrně silnou podmínku a takové grafy jsou natolik vzácné, že je lze uvést. The Podporovat sčítání lidu a jeho rozšíření takové seznamy poskytují.[7] Sčítání Foster začalo ve 30. letech 20. století Ronald M. Foster zatímco byl zaměstnán u Bell Labs,[8] a v roce 1988 (když bylo Fosterovi 92[1]) tehdejší aktuální sčítání Fosterů (uvádějící všechny kubické symetrické grafy až do 512 vrcholů) bylo publikováno v knižní podobě.[9] Prvních třináct položek v seznamu jsou kubické symetrické grafy s až 30 vrcholy[10][11] (deset z nich také vzdálenost-tranzitivní; výjimky jsou uvedeny):

VrcholyPrůměrObvodGrafPoznámky
413The kompletní graf K.4vzdálenost-tranzitivní, 2-oblouk-tranzitivní
624The kompletní bipartitní graf K.3,3vzdálenost-přechodný, 3-oblouk-přechodný
834Vrcholy a hrany krychlevzdálenost-tranzitivní, 2-oblouk-tranzitivní
1025The Petersenův grafvzdálenost-přechodný, 3-oblouk-přechodný
1436The Heawoodův grafvzdálenost-tranzitivní, 4-oblouk-tranzitivní
1646The Möbius – Kantorův graf2-oblouk-tranzitivní
1846The Pappusův grafvzdálenost-přechodný, 3-oblouk-přechodný
2055Vrcholy a hrany dvanáctistěnvzdálenost-tranzitivní, 2-oblouk-tranzitivní
2056The Desargues grafvzdálenost-přechodný, 3-oblouk-přechodný
2446The Nauru graf (dále jen zobecněný Petersenův graf G (12,5))2-oblouk-tranzitivní
2656The Graf F26A[11]1-oblouk-tranzitivní
2847The Coxeterův grafvzdálenost-přechodný, 3-oblouk-přechodný
3048The Tutte – Coxeterův grafvzdálenost-tranzitivní, 5-oblouk-tranzitivní

Další dobře známé kubické symetrické grafy jsou Dyckův graf, Pěstounský graf a Biggs – Smithův graf. Deset výše uvedených přechodových grafů spolu s Pěstounský graf a Biggs – Smithův graf, jsou jediné kubické vzdálenosti-tranzitivní grafy.

Zahrnují nekubické symetrické grafy cyklické grafy (stupně 2), kompletní grafy (stupně 4 nebo více, pokud je 5 nebo více vrcholů), hyperkrychlové grafy (stupně 4 nebo více, pokud je 16 nebo více vrcholů) a grafy tvořené vrcholy a hranami osmistěn, dvacetistěnu, cuboctahedron, a icosidodecahedron. The Rado graf tvoří příklad symetrického grafu s nekonečně mnoha vrcholy a nekonečným stupněm.

Vlastnosti

The vrchol-konektivita symetrického grafu se vždy rovná stupeň d.[3] Naproti tomu pro vertex-tranzitivní grafy obecně je konektivita vrcholů omezena níže 2 (d + 1)/3.[2]

A t- přechodný graf stupně 3 nebo více má obvod nejméně 2 (t - 1). Neexistují však žádné konečné t- přechodné grafy stupně 3 nebo více prot ≥ 8. V případě, že stupeň je přesně 3 (kubické symetrické grafy), neexistují žádné prot ≥ 6.

Viz také

Reference

  1. ^ A b C d E F Biggs, Norman (1993). Algebraická teorie grafů (2. vyd.). Cambridge: Cambridge University Press. str. 118–140. ISBN  0-521-45897-8.
  2. ^ A b C Godsil, Chris; Royle, Gordone (2001). Algebraická teorie grafů. New York: Springer. p.59. ISBN  0-387-95220-9.
  3. ^ A b C Babai, L (1996). „Automorfické skupiny, izomorfismus, rekonstrukce“. V Graham, R; Grötschel, M; Lovász, L (eds.). Příručka kombinatoriky. Elsevier.
  4. ^ Bouwer, Z. "Vertex and Edge Transitive, but Not 1-Transitive Graphs." Canad. Matematika. Býk. 13, 231–237, 1970.
  5. ^ Gross, J.L. a Yellen, J. (2004). Příručka teorie grafů. CRC Press. p. 491. ISBN  1-58488-090-2.
  6. ^ Holt, Derek F. (1981). Msgstr "Graf, který je přechodný od okraje, ale nikoli přechodový." Journal of Graph Theory. 5 (2): 201–204. doi:10,1002 / jgt.3190050210..
  7. ^ Marston Conder, Trojmocné symetrické grafy až na 768 vrcholech, J. Combin. Matematika. Kombinovat. Comput, roč. 20, s. 41–63
  8. ^ Foster, R. M. „Geometrické obvody elektrických sítí“. Transakce amerického institutu elektrotechniků 51, 309–317, 1932.
  9. ^ „Foster Census: R.M. Foster's Census of Connected Symetric Trivalent Graphs“, Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson a Z. Star (1988) ISBN  0-919611-19-2
  10. ^ Biggs, str. 148
  11. ^ A b Weisstein, Eric W., “Krychlový symetrický graf “, od Wolframa MathWorld.

externí odkazy