10. FEJEZET: Vegyes gráfelméleti feladatok
A gráfelméleti alapfogalmak lezárásaként csokorba gyűjtöttünk néhány - olykor komolyabb ötletet is igénylő, olykor inkább gyakorló jellegű - feladatot, amelyek csak elemi gráfelméleti fogalmakat használnak.
Vegyes feladatok
Feladat: 10.1.
Egy egyszerű véges gráfról a következőket tudjuk: bármely két össze nem kötött pontjának van közös szomszédja, semely két összekötött pontjának nincs közös szomszédja. Következik-e ebből, hogy a gráf reguláris?
Feladat: 10.2.
(
10.1. feladat folytatása.)
Egy egyszerű véges gráfról a következőket tudjuk: bármely két össze nem kötött pontjának van közös szomszédja, semely két összekötött pontjának nincs közös szomszédja. Tudjuk továbbá, hogy nincs benne telített pont. Következik-e ebből, hogy a gráf reguláris?
Feladat: 10.3.
* Bizonyítsuk be, hogy ha egy
n pontú,
e élű gráfban összeadjuk a fokszámok négyzetösszegét, a kapott eredmény legalább
4
e2
/n. Egyenlőség csak reguláris gráfra van.
Feladat: 10.4.
Egy
3n tagú társaságban bármely két embernek van közös ismerőse. Bizonyítsuk be, hogy kiválasztható közülük
n+1 ember, akik együtt a társaság minden tagját ismerik.
Feladat: 10.5.
Egy egyszerű poliéder minden csúcsára egy-egy egész számot akarunk írni úgy, hogy ha két csúcs élszomszédos, akkor a rájuk írt számoknak legyen egynél nagyobb közös osztójuk, ha két csúcs nem élszomszédos, akkor ne legyen. (Vagyis két csúcson álló szám pontosan akkor legyen relatív prím, ha a két csúcs nem élszomszéd.)
Megtehető-e ez mindig?
Mi a helyzet, ha fordított eredményt akarok, tehát ha azt akarom, hogy két csúcson álló szám pontosan akkor legyen relatív prím, ha a két csúcs élszomszédos?
Feladat: 10.6.
Kutató munka:
Hogyan általánosítható a
8.15. feladatban megfogalmazott állítás?
Feladat: 10.7.
Kutató munka:
Felbontható-e három teljes párosítás uniójára a
8.19. feladat ábrájának három gráfja? És a
8.13. feladat megoldásában szereplő ábra gráfja?
Feladat: 10.8.
** Mutassuk meg, hogy minden gráf csúcsai két részre vághatók úgy, hogy a pontoknak a saját osztályukban páros sok szomszédjuk van. (Vagyis a két osztály által feszített két részgráfban minden pont foka páros.)
Néhány egyszerűen bizonyítható tétel
Feladat: 10.9.
Bizonyítsuk be, hogy ha egy hurokél nélküli, véges, összefüggő gráfban pontosan akkor van zárt Euler-séta, ha minden pont foka páros.
Feladat: 10.10.
Bizonyítsuk be, hogy egy 4-reguláris gráf élei két csoportba oszthatók úgy, hogy mindkét csoport egy 2-reguláris feszítő részgráfot határozzon meg.
Feladat: 10.11.
* Bizonyítsuk be, hogy egy 4-reguláris egyszerű páros gráf élei négy színnel színezhetők úgy, hogy minden szín egy 1-faktort (a gráf pontjainak egy teljes párosítását) adja.
Megjegyzés. Az általános tételt majd a
K.III.3. fejezetben tárgyaljuk.
Feladat: 10.12.
Van-e hiba a következő bizonyításban:
Ha egy egyszerű páros gráfban minden pont foka legalább négy, akkor van benne teljes párosítás. Hagyjunk el ugyanis a gráfból éleket addig, amíg van négynél magasabb fokú pont. Így kapunk egy 4-reguláris gráfot, s erre a
10.11. feladatban már bebizonyítottuk az állítást.
Feladat: 10.13.
* Egy
n pontú egyszerű gráf csúcsainak fokszáma nagyság szerint csökkenő sorrendben
d1
≥
d2
≥…
dn
. Bizonyítsuk be, hogy minden 1 és
n közötti
i-re igaz, hogy
di+1
+
di+2
+…
dn
≥
d1
+
d2
+…+
di
-i(i-1)/2.
|
Megjegyzés. Ez tehát egy szükséges feltétel ahhoz, hogy legyen olyan
n pontú gráf, amelynek
i-edik pontja pontosan
di
fokú. Erdős és Gallai bebizonyították, hogy ugyanez a feltétel elégséges is ahhoz, hogy legyen ilyen egyszerű gráf, ennek bizonyítása azonban lényegesen nehezebb.
A tétel az itt szereplő bizonyítással az első gráfelméleti könyvből, König Die Theorie der Graphen c. könyvéből való.
Feladat: 10.14.
* A
10.4. feladatban beláttuk, hogy ha egy
3n tagú társaságban bármely két embernek van közös ismerőse, akkor van közöttük
n+1 ember, aki együtt mindenkit ismer. Mi a helyzet akkor, ha a feltételt némileg gyengítjük és csak annyit feltételezünk, hogy a társaság ismeretség-gráfja 2-átmérőjű, azaz csak annyit feltételezünk, hogy bármely két egymást nem ismerő embernek van közös ismerőse?
Feladat: 10.15.
* Bizonyítsuk be, hogy páros sok olyan egyszerű gráf van, amelynek pontjai 1-től
n-ig vannak számozva, s amelyben nincs sem telített pont, sem izolált pont. Itt tehát nem egyszerűen pontokról, hanem
számozott pontokról van szó. Így
nem tekintjük azonosnak például
n=3-ra azt a két gráfot, amelyek közül az egyikben csak a kettes és a hármas nins összekötve, a másikban csak az egyes és a kettes nincs összekötve - bár ezek a gráfok a számozástól eltekintve izomorfak.
Néhány Hamilton-körrel kapcsolatos feladat
Feladat: 10.16.
Van-e olyan összefüggő 4-reguláris gráf, amelynek nincs Hamilton-köre?
Milyen
k-ra van összefüggő
k-reguláris gráf, amelynek nincs Hamilton-köre?
Feladat: 10.17.
a) Egy ötpontú gráfban legfeljebb hány él lehet, ha nincs benne ötpontú kör?
b) Egy hatpontú gráfban legfeljebb hány él lehet, ha nincs benne hatpontú kör?
Megjegyzés. Az általános kérdést tárgyalja a következő
10.18. feladat.
Feladat: 10.18.
a) Egy
n pontú egyszerű gráfban legfeljebb hány él lehet, ha nincs benne Hamilton-út?
b) Egy
n pontú egyszerű gráfban legfeljebb hány él lehet, ha nincs benne Hamilton-kör?
Néhány versenyfeladat
Megjegyezzük, hogy az itt szereplő feladatok korántsem egyforma nehézségűek. A nehezebbeket itt is *-gal jelöltük.
Feladat: 10.19.
Egy sakkversenyen
n nő és
2n férfi vett részt. Mindenki mindenkivel pontosan egyszer játszott. Nem volt döntetlen és a nők által megnyert játszmák aránya úgy viszonyult a férfiak által megnyert játszmák számához, mint 7:5. Hány nő vett részt a játékban? (Arany Dániel-verseny 1984K)
Feladat: 10.20.
Három házaspár vacsorán vesz részt. Mindenki más-más időpontban érkezik a vacsora helyszínére. Minden újonnan érkező ember kezet fog a már ott tartózkodókkal, kivéve saját házastársával. Miután mindenki leült vacsorázni, az egyik ember megkérdezte az összes többitől, hogy hány emberrel fogott kezet érkezésekor. Hányadikként érkezhetett az illető, ha kérdésére öt különböző választ kapott? (Arany Dániel-verseny, 1995H)
Feladat: 10.21.
* Egy előadáson ötven személy vett részt. Tudjuk, hogy bármely négy résztvevő között van olyan, aki a másik három személy mindegyikével találkozott már korábban. Bizonyítandó, hogy bármely négy résztvevő között van olyan személy, aki korábban már mindegyik résztvevővel találkozott. (Arany Dániel-verseny, 2004H)
Feladat: 10.22.
* Egy elektronikus levelezőtársaságnak 2004 tagja van. Közülük néhányan személyesen is ismerik egymást (az ismeretség kölcsönös). Bizonyítsa be, hogy a 2004 tag két csoportba osztható úgy, hogy a csoportokon belül személyes ismeretségek számának összege nem több, mint a két csoport tagjai közötti ismeretségek száma! (OKTV, 2005)