3. FEJEZET: Fák, favázak

Feladat: 3.1.
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.
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.
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.
Oldjuk meg . feladatot a szélességi faváz segítségével!
 

Feladat: 3.5.
Mi lehet a teljes gráf szélességi faváza?
 

Feladat: 3.6.
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.
Mi lehet egy n pontú kör szélességi faváza?
 

Feladat: 3.8.
Van-e több olyan faváza Cn -nek, amely teljesíti a 3.2. feladat feltételét?
 

Feladat: 3.9.
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.
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.
* 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.
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.
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.
Rajzoljuk fel a szabályos dodekaéder minden szélességi favázát!
 

Feladat: 3.15.
Rajzoljuk fel a kocka gráfja komplementerének minden szélességi favázát!
 

Feladat: 3.16.
Bizonyítsuk be, hogy egy gráf pontosan akkor páros gráf, ha nincs benne páratlan kör.
 

Feladat: 3.17.
Egy n pontú egyszerű gráfban nincs páratlan kör. Legfeljebb hány éle lehet?
 

Feladat: 3.18.
** 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.
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.
* 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.
 

Feladat: 3.21.
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.
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.
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.
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.
Mélységi faváz!!
 

Feladat: 3.26.
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.
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.
Mi lehet a teljes gráf mélységi faváza?
 

Feladat: 3.29.
Mi lehet egy n pontú kör mélységi faváza?
 

Feladat: 3.30.
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.
Rajzoljuk fel az ikozaéder minden mélységi favázát!
 

Feladat: 3.32.
Igaz-e, hogy ha egy gráfban van Hamilton-kör, akkor minden mélységi faváza Hamilton-út?