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

[ellenőrzött változat]

← Régebbi szerkesztés Újabb szerkesztés →

Tartalom törölve Tartalom hozzáadva

Sorban

A lap 2016. május 17., 12:59-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 csúcstranzití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

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 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

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

Jegyzetek

↑ ^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

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]

@@ 4. sor: / 4. sor: @@
 A [[matematika]], azon belül a [[gráfelmélet]] területén egy ''G'' gráf '''csúcstranzitív''', ha bármely két ''e''<sub>1</sub> és ''e''<sub>2</sub> élére létezik ''G''-nek olyan [[Gráfautomorfizmus|automorfizmusa]], amely ''e''<sub>1</sub>-et ''e''<sub>2</sub>-be viszi át.<ref name="biggs">{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | page=118 | isbn=0-521-45897-8}}</ref>
-Más szavakkal egy gráf akkor éltranzitív, ha [[Automorfizmus (csoportelmélet)|automorfizmus-csoportja]] tranzitív az éleire nézve.
+Más szavakkal egy gráf akkor éltranzitív, ha [[Automorfizmus (csoportelmélet)|automorfizmus-csoportja]] tranzitívan [[Csoporthatás|hat]] az éleire nézve.
 ==Példák és tulajdonságok==

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