3. FEJEZET: Fák, favázak{mchap:alg_ii_favazak}
A fejezet még fejlesztés alatt áll.
. feladat jó ,,bemelegítő feladat" a szélességi favázhoz! L. a
3.4. és feladatot is!
Szélességi faváz
Feladat: 3.1. {k_ii_100101sl_grut41}
Legyen
G összefüggő gráf. Létezik-e
G-nek olyan faváza, amely ,,megőrzi" minden pontpár távolságát? Ezen azt értjük, hogy
x és
y távolsága
G-ben és a favázban bármely két pontra ugyanannyi.
Feladat: 3.2. {k_ii_100101sl_grut42}
Legyen
G összefüggő egyszerű gráf és legyen
x a gráf egy tetszőleges pontja. Létezik-e
G-nek olyan faváza, amelyben az
x-től való távolságot ,,megőrzi"? Ezen azt értjük, hogy bármely
y pontra
x és
y távolsága
G-ben és a favázban azonos.
Feladat: 3.3. {k_ii_100101sl_grut43}
A szélességi faváz definíciója. Legyen
G egy összefüggő gráf és legyen
x a gráf egy pontja. Legyenek a gráf pontjai megszámozva:
x=
x1
,
x2
,…,
xn
. A faváz textitnulladik emelete egyetlen pontból, az
x pontból áll. Az
első emeletére
x szomszédai kerülnek. Mindegyiküket össze is kötjük
x-szel.
Általában az
i-edik emeletre az
i-1-edik emeleti pontok szomszédai kerülnek, feltéve, hogy még nem szerepelnek korábbi emeleten. Lehetséges azonban, hogy egy ilyen pont több,
i-1-edik emeleti ponttal is össze van kötve. Ilyenkor azzal a szomszédjával kötjük össze, amelyiknek legkisebb az indexe.
Bizonyítsuk be, hogy az így kapott részgráf
G faváza, amelynek minden éle két, szomszédos emeleten levő pontot köt össze. A
G gráf minden éle vagy két, azonos emeleten levő pontot köt össze, vagy két szomszédos emeleten levő pontot.
Feladat: 3.4. {k_ii_sl_petersen00}
Oldjuk meg . feladatot a szélességi faváz segítségével!
Feladat: 3.5. {k_ii_100101sl_grut54b}
Mi lehet a teljes gráf szélességi faváza?
Feladat: 3.6. {k_ii_100101sl_grut64b}
Van-e több olyan, egymással nem izomorf faváza a teljes gráfnak, amely teljesíti a
3.2. feladat feltételét?
Feladat: 3.7. {k_ii_100101sl_grut54c}
Mi lehet egy
n pontú kör szélességi faváza?
Feladat: 3.8. {k_ii_100101sl_grut64c}
Van-e több olyan faváza
Cn
-nek, amely teljesíti a
3.2. feladat feltételét?
Feladat: 3.9. {k_ii_100105sl_grut01}
Mutassunk példát olyan gráfra, amelynek több, egymással nem izomorf
x gyökerű szélességi faváza van!
Feladat: 3.10. {k_ii_100105sl_grut02}
Nyilvánvaló, hogy ha egy összefüggő egyszerű gráf két pontjának a fokszáma különbözik, akkor a belőlük induló szélességi favázak nem lehetnek izomorfak.
Mutassunk példát olyan reguláris gráfra, amelynek több, egymással nem izomorf szélességi faváza van!
Feladat: 3.11. {k_ii_100105sl_grut03}
* Van-e olyan csúcstranzitív gráf, amelynek több, egymással nem izomorf szélességi faváza van?
Megjegyzés. A csúcstranzitivitás definícióját lásd . fejezetben.
Feladat: 3.12. {k_ii_100101sl_grut54a}
Igazoljuk, hogy az oktaéder minden szélességi faváza izomorf!
Igaz-e, hogy ugyanez a kockára? És az ikozaéderre?
Feladat: 3.13. {k_ii_100101sl_grut64a}
Van-e több olyan, a szélességi favázzal nem izomorf faváza
a) az oktaédernek,
b) a kockának,
amely teljesíti a
3.2. feladat feltételét?
Feladat: 3.14. {k_ii_100101sl_grut54}
Rajzoljuk fel a szabályos dodekaéder minden szélességi favázát!
Feladat: 3.15. {k_ii_100106sl_grut03}
Rajzoljuk fel a kocka gráfja komplementerének minden szélességi favázát!
Feladat: 3.16. {k_ii_090806sl_parosgr01}
Bizonyítsuk be, hogy egy gráf pontosan akkor páros gráf, ha nincs benne páratlan kör.
Feladat: 3.17. {k_ii_100109sl_paros02}
Egy
n pontú egyszerű gráfban nincs páratlan kör. Legfeljebb hány éle lehet?
Feladat: 3.18. {k_ii_100109sl_paros01}
** Adott
n≥5 egész szám. Minden lehetséges módon számpárokat képeztünk belőlük, s vettük minden számpárban a számok összegét. Az így kapott
(
n2
-n)/2 összeg közül legalább
(
n2
-3n+4)/2 racionális. Bizonyítandó, hogy akkor az összes összeg racionális.
Következik-e a feltételből az is, hogy minden megadott szám racionális?
Feladat: 3.19. {k_ii_090822sl_grut02}
Bizonyítsuk be, hogy egy tetszőleges gráf szélességi favázában a gyökérből induló minden út geodetikus útvonal a gráfban.
Feladat: 3.20. {k_ii_090822sl_grut03}
* Bizonyítsuk be, hogy ha egy végtelen összefüggő gráfban minden pont foka véges, akkor van benne (egy irányban végtelen) geodetikus útvonal.
Mélységi faváz
Feladat: 3.21. {k_ii_melysegisl_01}
Van-e olyan faváza
a) az
n pontú teljes gráfnak,
b) az
n pontú körnek,
c) a Petersen-gráfnak,
d) . feladat gráfjának
amelyre igaz, hogy a gráf minden éle a faváz egy elődjét és utódját köti össze?
Feladat: 3.22. {k_ii_melysegisl_02}
Van-e olyan faváza . feladat gráfjának, amelynek gyökere az ötödfokú pont és amelyre igaz, hogy a gráf minden éle a faváz egy elődjét és utódját köti össze?
Feladat: 3.23. {k_ii_melysegisl_03}
Legyen
G az alábbi gráf:
Van-e ennek a gráfnak olyan faváza amelyre igaz, hogy a gráf minden éle a faváz egy elődjét és utódját köti össze?
Van-e ilyen faváza akkor is, ha megköveteljük, hogy annak gyökere a gráf egy másodfokú pontja legyen.
Feladat: 3.24. {k_ii_melysegisl_04}
Legyen
G az alábbi gráf:
Van-e ennek a gráfnak olyan faváza amelyre igaz, hogy a gráf minden éle a faváz egy elődjét és utódját köti össze, s amelynek gyökere a gráf egyik negyedfokú pontja?
Feladat: 3.25. {k_ii_melysegi}
Mélységi faváz!!
Feladat: 3.26. {k_ii_melysegisl_05}
Igaz-e, hogy minden összefüggő gráfnak van olyan faváza, amelyre igaz, hogy a gráf minden éle a faváz egy elődjét és utódját köti össze?
Feladat: 3.27. {k_ii_091207sl_grut01}
Legyen
G egy összefüggő véges egyszerű gráf, amelynek
k éle van. Bizonyítsuk be, hogy az élei megszámozhatók az
1,2,…,k számokkal úgy, hogy minden, legalább másodfokú pontra igaz, hogy a belőle induló élekre írt számok legnagyobb közös osztója 1. (NMO, 1991)
Feladat: 3.28. {k_ii_100101sl_grut55b}
Mi lehet a teljes gráf mélységi faváza?
Feladat: 3.29. {k_ii_100101sl_grut55c}
Mi lehet egy
n pontú kör mélységi faváza?
Feladat: 3.30. {k_ii_100101sl_grut55a}
Igazoljuk, hogy a tetraéder minden mélységi faváza izomorf!
Igaz-e ugyanez a kockára? És az oktaéderre?
Feladat: 3.31. {k_ii_100101sl_grut55}
Rajzoljuk fel az ikozaéder minden mélységi favázát!
Feladat: 3.32. {k_ii_100109sl_favaz01}
Igaz-e, hogy ha egy gráfban van Hamilton-kör, akkor minden mélységi faváza Hamilton-út?