| dbo:abstract
|
- 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, u1—v1 és u2—v2 csúcsszomszéd-párjára létezik olyan automorfizmus, f : V(G) → V(G), melyre f(u1) = u2 és f(v1) = v2. 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). Az ilyen gráfot néha 1-arc-transitive („1-ív-tranzitív”) vagy flag-transitive néven is leírják. A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak csúcstranzitívnak is kell lennie. 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 a—b-t átviszi c—d-be, de d—c-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. 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. Ezek a féltranzitív gráfok. A legkisebb összefüggő féltranzitív a 4 fokszámú, 27 csúcsú Holt-gráf. 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. 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. (hu)
- 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, u1—v1 és u2—v2 csúcsszomszéd-párjára létezik olyan automorfizmus, f : V(G) → V(G), melyre f(u1) = u2 és f(v1) = v2. 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). Az ilyen gráfot néha 1-arc-transitive („1-ív-tranzitív”) vagy flag-transitive néven is leírják. A definíció alapján egy izolált csúcsok nélküli szimmetrikus gráfnak csúcstranzitívnak is kell lennie. 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 a—b-t átviszi c—d-be, de d—c-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. 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. Ezek a féltranzitív gráfok. A legkisebb összefüggő féltranzitív a 4 fokszámú, 27 csúcsú Holt-gráf. 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. 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. (hu)
|
