Matkönyv feladatgyűjtemény: Speciális gráfelmĂ©leti tĂ©mák 9--10

5. FEJEZET: Szimmetria és aszimmetria, II.

Bezárás: [ X ]

A fejezet még fejlesztés alatt áll.



A fejezetben a következő definíciókat használjuk:
Definíció. Egy G egyszerű gráf automorfizmusának a pontoknak egy olyan permutációját nevezzük, amely éllel összekötött pontoknak éllel összekötött pontokat feleltet meg és éllel össze nem kötött pontoknak éllel össze nem kötött pontokat feleltet meg. (,,A gráfnak önmagára való izomorf leképezése.")
Megjegyzés. Minden gráfnak van egy triviális automorfizmusa: az, amely minden pontját önmagába viszi.
Megjegyzés. A definíció természetesen terjeszthető ki nem egyszerű gráfokra is, de erre nem lesz szükségünk.
Definíció. Egy egyszerű gráfot pontosan akkor nevezünk csúcstranzitívnak, ha bármely a és b pontjához található olyan automorfizmus, amely az a pontot a b pontba viszi.
Definíció. Egy egyszerű gráfot pontosan akkor nevezünk éltranzitívnak, ha bármely (a,b) és (c,d) éléhez van olyan automorfizmus, amely a-t c-be és b-d d-be viszi.
Megjegyzés. Tehát az éltranzitivitás nem csak azt követeli meg, hogy bármely két él egymásba vihető legyen, hanem azt is ki kell tudnunk jelölni, hogy melyik legyen az él ,,kezdőpontja" és melyik a ,,végpontja". Hogy a gyengébb követelmény elég-e az éltranzitivitáshoz, arra vonatkozóan lásd az 5.37. feladatot.


Gráfok automorfizmusai

Feladat: 5.1.
Igaz-e, hogy minden csúcstranzitív gráf reguláris?
 
Feladat: 5.2.
Hány automorfizmusa van
a) a háromszögnek (három pontú teljes gráfnak);
b) a négy-, öt-, hatpontú teljes gráfnak;
c) az n pontú teljes gráfnak?
 
[  Megoldás  ]
Feladat: 5.3.
Tekintsük a kocka két tetszőleges teljes párosítását. Igaz-e, hogy van a gráfnak olyan automorfizmusa, ami egyiket a másikba viszi?
 
[  Megoldás  ]
Feladat: 5.4.
Tekintsük a Petersen-gráf két tetszőleges teljes párosítását. Igaz-e, hogy van a gráfnak olyan automorfizmusa, ami egyiket a másikba viszi?
 
[  Megoldás  ]
Feladat: 5.5.
Hány automorfizmusa van
a) a négy, az öt és a hat hosszú körnek;
b) a k hosszú körnek?
Határozzuk meg e gráfok orbitjait!
 
[  Megoldás  ]
Feladat: 5.6.
Hány automorfizmusa van
a) annak az ötpontú gráfnak, amely egy öt pontú körből és egy átlójából áll;
b) a K.II.8.24. feladatban definiált gráfnak?
Határozzuk meg e gráfok orbitjait!
 
[  Megoldás  ]
Feladat: 5.7.
Tekintsük a 4.1. feladat c) pontjában definiált gráfot.
a) Hány orbitja van ennek a gráfnak?
b) Hány automorfizmusa van ennek a gráfnak?
 
[  Megoldás  ]
Feladat: 5.8.
Legyen P és Q egy gráf két pontja.
a) Bizonyítsuk be, hogy pontosan annyi automorfizmus viszi a P pontot Q-ba, mint a Q pontot P-be.
b) Bizonyítsuk be az 5.7. feladat megoldásában használt állítást:
Ha a P pontot a helyén hagyó automorfizmusok száma k, akkor ugyanennyi automorfizmus viszi át a gráfot a P-vel egy orbitban levő Q pontba.
 
[  Megoldás  ]
Feladat: 5.9.
Hány automorfizmusa van a szabályos testek gráfjának? Hány orbitja van e gráfoknak?
 
[  Megoldás  ]
Feladat: 5.10.
Hány automorfizmusa van a KG(4,2) Kneser-gráfnak?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.11.
Hány automorfizmusa van
a) a három-ház-három-kút gráfnak;
b) annak a teljes páros gráfnak, amelynek egyik csoportjában három, másik csoportjában öt pont van?
Határozzuk meg a gráfok orbitjait.
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.12.
Határozzuk meg minden n,k számpárra, hogy hány automorfizmusa van annak a páros gráfnak, amelynek egyik csoportjában k, másik csoportjában n pont van? (A Kn,k teljes páros gráfnak.)
Hány orbitja van ezeknek a gráfoknak?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.13.
Hány automorfizmusa van annak a 2n pontú gráfnak, amely n darab független élből áll?
 
[  Megoldás  ]
Feladat: 5.14.
Hány automorfizmusa van a következő 9 pontú, 13 élű gráfnak (ez a 2.20. feladat c) részének megoldásában szereplő gráf):
A gráf pontjai legyenek az x,y,z, u1 , u2 , u3 , v1 , v2 , v3 pontok. A gráf egyrészt két összeragasztott ötszögből áll, ezek xyu1 u2 u3 x és xyv1 v2 v3 x. Ezen kívül még négy él van, mind a z pontból indul és azt az u2 , u3 , v2 , v1 pontokkal köti össze.
 
[  Megoldás  ]
Feladat: 5.15.
* Hány automorfizmusa van a Petersen-gráfnak?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.16.
Igaz-e, hogy minden reguláris gráf csúcstranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.17.
Igaz-e, hogy csúcstranzitív gráf komplementere is csúcstranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.18.
Éltranzitív-e az a hatpontú gráf, amelyet a szabályos hatszög gráfjából úgy kapunk, hogy összekötjük a másodszomszéd pontokat is?
 
[  Segítség, útmutatás  ]
Feladat: 5.19.
Csúcstranzitív-e a Petersen-gráf?
 
[  Megoldás  ]
Feladat: 5.20.
* Döntsük el, hogy milyen n és k értékekre csúcstranzitív a KG(n,k) Kneser-gráf.
 
[  Megoldás  ]
Feladat: 5.21.
* Egy G gráfról tudjuk, hogy bármely x pontját elhagyva a kapott G-x gráfok mind izomorfak. Következik-e ebből, hogy G csúcstranzitív?
 
[  Megoldás  ]
Feladat: 5.22.
Éltranzitív-e a Petersen-gráf?
 
[  Megoldás  ]
Feladat: 5.23.
Éltranzitív-e az oktaéder gráfjának komplementere?
 
[  Segítség, útmutatás  ]
Feladat: 5.24.
Az 5.23. és az 5.22. feladatban a KG(4,2) és a KG(5,2) Kneser-gráfok éltranzitivitásáról volt szó. Milyen n és k értékekre igaz, hogy KG(n,k) éltranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.25.
Éltranzitív-e a ,,3-ház-3-kút" gráf komplementere?
 
[  Segítség, útmutatás  ]
Feladat: 5.26.
Igaz-e, hogy minden éltranzitív gráf komplementere is éltranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.27.
Igaz-e, hogy minden összefüggő éltranzitív gráf komplementere is éltranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.28.
Éltranzitív-e a kocka gráfjának komplementere?
 
[  Segítség, útmutatás  ]
Feladat: 5.29.
Éltranzitív-e a Petersen-gráf komplementere?
 
[  Megoldás  ]
Feladat: 5.30.
Bizonyítsuk be, hogy ha egy éltranzitív (egyszerű) gráf komplementere összefüggő, akkor átmérője legfeljebb 2.
 
[  Megoldás  ]
Feladat: 5.31.
* A 4.22. feladatban láttuk, hogy a Petersen-gráf azonos a KG(5,2) gráffal és az 5.29. feladatban láttuk, hogy ennek a gráfnak a komplementere éltranzitív. Az 5.18. feladatban szereplő gráf - amely a KG(4,2) gráf komplementere (lásd a 4.21. feladatot) - szintén éltranzitív. Igaz-e, hogy a KG(n,2) gráf komplementere minden n-re éltranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.32.
* Igaz-e, hogy minden Kneser-gráf komplementere éltranzitív?
 
[  Megoldás  ]
Feladat: 5.33.
Igaz-e, hogy minden éltranzitív gráf komplementere csúcstranzitív?
 
[  Segítség, útmutatás  ]
Feladat: 5.34.
* Az ikozaéder automorfizmuscsoportja és az ötpontú teljes gráf automorfizmuscsoportja is 120 elemű (l. az 5.2. és az 5.9. feladatot) Azonos-e ez a két automorfizmuscsoport?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.35.
* Az 5.15. feladatban láttuk, hogy a Petersen-gráfnak 120 automorfizmusa van. A 4.22. feladat szerint a Petersen-gráf a KG(5,2) gráf, láttuk továbbá, hogy a Petersen-gráf automorfizmusai megegyeznek az ötelemű alaphalmaz 120 permutációjából kapható 120 automorfizmussal.
Igaz-e általában is, hogy a KG(n,k) Kneser-gráfnak pontosan n! automorfizmusa van?
 
[  Megoldás  ]
Feladat: 5.36.
* Mi a Petersen-gráf automorfizmus-csoportja?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 5.37.
Egy gráfról tudjuk, hogy bármely két éléhez van olyan automorfizmus, amely az egyiket a másikba viszi. Következik-e ebből, hogy a gráf éltranzitív?
 
[  Segítség, útmutatás  ]