„Éltranzitív gráf” változatai közötti eltérés

[ellenőrzött változat]

Tartalom törölve Tartalom hozzáadva

Sorban

A lap jelenlegi, 2017. március 13., 08:15-kori változata

Ez a szócikk az éltranzitivitás gráfelméleti vonatkozásáról szól. A geometriai éltranzitivitáshoz lásd a sokszög szócikket.

A matematika, azon belül a gráfelmélet területén egy G gráf éltranzitív, ha bármely két e₁ és e₂ élére létezik G-nek olyan automorfizmusa, amely e₁-et e₂-be viszi át.^[1]

Más szavakkal egy gráf akkor éltranzitív, ha automorfizmus-csoportja tranzitívan hat az éleire nézve.

Példák és tulajdonságok[szerkesztés]

Az éltranzitív gráfok közé tartozik az összes $K_{m,n}$ teljes páros gráf, az összes szimmetrikus gráf, pl. a kocka csúcsai és élei is éltranzitív gráfot alkotnak.^[1] A szimmetrikus gráfok csúcstranzitívek is (már ha összefüggőek), de általában véve az éltranzitív gráfok nem szükségképpen csúcstranzitívak. A Gray-gráf példa olyan gráfra, ami éltranzitív, de nem csúcstranzitív. Az összes ilyen gráf páros,^[1] ezért két színnel színezhető.

Az olyan éltranzitív gráfokat, amik regulárisak de nem csúcstranzitívak, félszimmetrikus gráfoknak nevezik. A Gray-gráf erre is példát szolgáltat. Minden éltranzitív gráf, ami nem csúcstranzitív, szükségképpen páros gráf és vagy félszimmetrikus vagy bireguláris.^[2]

Kapcsolódó szócikkek[szerkesztés]

Éltranzitív (mértani jelentése)

Jegyzetek[szerkesztés]

↑ ^a ^b ^c Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118. o. (1993). ISBN 0-521-45897-8
↑ Lauri, Josef & Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, <http://books.google.com/books?id=hsymFm0E0uIC&pg=PA20>.

További információk[szerkesztés]

Weisstein, Eric W.: Edge-transitive graph (angol nyelven). Wolfram MathWorld

[biggs-1] Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118. o. (1993). ISBN 0-521-45897-8

[ls03-2] Lauri, Josef & Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, <http://books.google.com/books?id=hsymFm0E0uIC&pg=PA20>.

[1]

[2]

@@ 9. sor: / 9. sor: @@
 [[Image:Gray graph 2COL.svg|thumb|200px|A [[Gray-gráf]] éltranzitív és [[reguláris gráf|reguláris]], de nem [[csúcstranzitív gráf|csúcstranzitív]].]]
-Az éltranzitív gráfok közé tartozik az összes <math>K_{m,n}</math> [[teljes páros gráf]], az összes [[szimmetrikus gráf]], pl. a [[kocka]] csúcsai és élei is alkotnak.<ref name="biggs" />  A szimmetrikus gráfok [[csúcstranzitív gráf|csúcstranzitívek]] is (már ha összefüggőek), de általában véve az éltranzitív gráfok nem szükségképpen csúcstranzitívak. A [[Gray-gráf]] példa olyan gráfra, ami éltranzitív, de nem csúcstranzitív. Az összes ilyen gráf [[páros gráf|páros]],<ref name="biggs" /> ezért [[gráfok színezése|két színnel színezhető]].
+Az éltranzitív gráfok közé tartozik az összes <math>K_{m,n}</math> [[teljes páros gráf]], az összes [[szimmetrikus gráf]], pl. a [[kocka]] csúcsai és élei is éltranzitív gráfot alkotnak.<ref name="biggs" /> A szimmetrikus gráfok [[csúcstranzitív gráf|csúcstranzitívek]] is (már ha összefüggőek), de általában véve az éltranzitív gráfok nem szükségképpen csúcstranzitívak. A [[Gray-gráf]] példa olyan gráfra, ami éltranzitív, de nem csúcstranzitív. Az összes ilyen gráf [[páros gráf|páros]],<ref name="biggs" /> ezért [[gráfok színezése|két színnel színezhető]].
 Az olyan éltranzitív gráfokat, amik [[reguláris gráf|regulárisak]] de nem csúcstranzitívak, [[félszimmetrikus gráf]]oknak nevezik. A [[Gray-gráf]] erre is példát szolgáltat.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
_{(ha összefüggő)} csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	_(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus