4. FEJEZET: Szimmetria és aszimmetria, I.
Gráfok izomorfiája
Feladat: 4.1.
Izomorf-e egymással . ábrán látható két gráf?
Feladat: 4.2.
Izomorf-e egymással a
4.2. ábrán látható két gráf?
Feladat: 4.3.
Egy hétpontú körbe behúztuk a ,,rövidebb" átlókat, egy másik hétpontú körben pedig behúztuk a ,,hosszabb" átlókat. Izomorf-e az így kapott két hétpontú gráf? L. . ábrát!
Feladat: 4.4.
Izomorf-e egymással ábrán látható két gráf?
Feladat: 4.5.
Van-e két, egymással nem izomorf ötpontú 2-reguláris gráf?
Feladat: 4.6.
Van-e két, egymással nem izomorf 2-reguláris hatpontú gráf?
Feladat: 4.7.
Izomorf-e egymással bármely két hatpontú, 2-reguláris összefüggő gráf?
Feladat: 4.8.
a) Van-e két, egymással nem izomorf 3-reguláris hétpontú gráf?
b) Hány egymással nem izomorf hétpontú 4-reguláris gráf van?
Feladat: 4.9.
Melyik állítások igazak az alábbiak közül: Ha két gráf izomorf, akkor
a) azonos a kromatikus számuk;
b) ugyanakkora az átmérőjük;
c) mindkettőben ugyanannyi a független pontok maximális száma.
Feladat: 4.10.
Izomorf-e egymással a következő három gráf:
a) a kocka gráfja,
b) az a nyolcpontú páros gráf, amelyet úgy kapunk a
K4,4
teljes páros gráfból, hogy elhagyunk egy teljes párosítást (. ábra),
c) az a nyolcpontú gráf, amely egy nyolc hosszú körből áll, ennek pontjai sorban a
Pi
pontok,
i=1,2,…,8, a gráf éle még a következő négy átló:
P1
P3
,
P2
P4
,
P5
P7
,
P6
P8
(
4.10. ábra).
Feladat: 4.11.
Igaz-e, hogy izomorf gráfok komplementerei is izomorfak?
Feladat: 4.12.
Hány különböző, egymással nem izomorf
n pontú egyszerű gráf van, ha
a)
n=3,
b)
n=4?
Feladat: 4.13.
Számoljuk meg, hány egymással nem izomorf 2-reguláris
n pontú egyszerű gráf van az
n=4,5,6,7,8,9 esetben!
Feladat: 4.14.
Igaz-e, hogy ha két összefüggő, hatpontú gráfban a fokszámok rendre 1,1,1,1,3,3, akkor a két gráf izomorf?
Feladat: 4.15.
[
4], 14. old.
Igaz-e, hogy ha két összefüggő, hétpontú gráfban a fokszámok rendre 1,1,1,1,2,3,3, akkor a két gráf izomorf?
Feladat: 4.16.
Hány egymással nem izomorf hétpontú fa van, amelyben van negyedfokú pont?
Feladat: 4.17.
Hány olyan nem-izomorf tízpontú fa van, amelyben van két, legalább ötödfokú pont?
Feladat: 4.18.
Hány olyan nem-izomorf
2k pontú fa van, amelyben van két, legalább
k-adfokú pont?
Feladat: 4.19.
Hány olyan nem-izomorf tízpontú összefüggő gráf van, amelyben van két-két negyed- és másodfokú pont van, a többi pont pedig elsőfokú?
Feladat: 4.20.
Bizonyítsuk be, hogy a
K.II.8.13. feladat megoldásában kapott gráf . ábrán látható Petersen-gráf
Feladat: 4.21.
Melyik ismert gráf a
KG(4,2) Kneser-gráf komplementere?
Feladat: 4.22.
Melyik ismert gráf a
KG(5,2) Kneser-gráf?
Feladat: 4.23.
Adott két
n pontú egyszerű gráf. Az egyik gráf mindegyik
n-1 pontú feszített részgráfjához van a másiknak ezzel izomorf
n-1 pontú feszített részgráfja. Következik-e ebből, hogy a két gráf is izomorf?
Feladat: 4.24.
Két négypontú gráf minden hárompontú feszített részgráfja két élt tartalmaz. Következik-e ebből, hogy a két négypontú gráf izomorf?
Feladat: 4.25.
Egy
G gráfról tudjuk, hogy bármely pontját elhagyva egymással izomorf részgráfokat kapunk. Következik-e ebből, hogy a gráf reguláris?
Feladat: 4.26.
G és
G' azonos pontszámú
d-reguláris gráfok. Tudjuk, hogy
G-nek van olyan
x pontja és
G'-nek van olyan
x' pontja, amelyre
G-x és
G-x' izomorfak. Következik-e ebből, hogy
G és
G' is izomorf?
Komplementerükkel izomorf gráfok
Feladat: 4.27.
[
4], 14. old.
Mely
G páros gráfok izomorfak a komplementerükkel?
Feladat: 4.28.
[
4], 14. old.
Mely fák izomorfak a komplementerükkel?
Feladat: 4.29.
Azt vizsgáljuk, hogy milyen
n-ekre van olyan
n pontú egyszerű gráf, amely izomorf saját komplementerével.
a) Döntsük el a kérdést az
n=1,2,3,4,5,6,7 esetekben!
b) Döntsük el a kérdést
n=8,9 esetben!
Feladat: 4.30.
Döntsük el általában, hogy
n milyen értékeire van olgyan
n pontú egyszerű gráf, amely izomorf a komplementerével!
Feladat: 4.31.
[
4], 14. old.
Legyen
n páratlan egész szám és legyen
G egy
n pontú gráf, amely izomorf a komplementerével. Bizonyítandó, hogy van olyan pontja, amelynek
(n-1)/2 a fokszáma.