4. FEJEZET: Páros gráfok
A gráfelméleti alapfogalmak bevezetését egy fontos gráfosztály, a páros gráfok bevezetésével folytatjuk. Bebizonyítunk pár velük kapcsolatos elemi tételt. A páros gráfokra vonatkozó további tételek, így a König-tételek a K.III.3. fejezetben kerülnek majd sorra.
A fejezet néhány feladata most is az előző kötet
Gráfok című fejezetének feladataihoz kapcsolódik. Ezekre az adott helyen fogunk hivatkozni és jelezni fogjuk, hol melyiket érdemes átismételni.
A páros gráf fogalma
Feladat: 4.1.
Egy táncestély végén megkérdeztük a lányokat, hány fiúval táncoltak és megkérdeztük a fiúkat, hány lánnyal táncoltak.
Ábrázoljuk gráfokkal az estély táncospárjait és keressünk összefüggést a fiúk által mondott számok és a lányok által mondott számok között. Próbáljuk bizonyítani a megsejtett összefüggést!
Feladat: 4.2.
Egy másik táncestély végén csak a lányokat kérdeztük meg, hány fiúval táncoltak. Erre egyesével nem akartak válaszolni, de ha kettesével kérdeztük őket, annyi azért kiderült, hogy bármelyik két lány együtt legfeljebb hat fiúval táncolt (ha két lány táncolt ugyanazzal a fiúval, mindkettőjük számolja a táncpartnerei között). Vajon legalább hány különböző táncospárt számolhattunk volna össze, ha végignézzük az estélyt?
Feladat: 4.3.
Mit mondhatunk, ha a
4.2. feladatban szereplő táncestélyen azt tudjuk meg, hogy
a) ha bármely két lány összeszámolja táncpartnereit (a közös táncpartnereket mindketten számolják), akkor legalább hét jön ki?
b) ha bármely három lány összeszámolja táncpartnereit (a közös táncpartnereket annyian számolják, ahányan táncoltak vele), és összeadja a kapott számokat, akkor legalább tíz jön ki?
B) Kommentár és definíciók
A
4.1. és
4.2. feladatban - és a korábbi feladatok közül például a
K.I.18.8. feladatban, valamint a
K.I.18.9. feladat a) részében - egy speciális gráffajta szerepel, aminek kitüntetett szerepe volt és van a gráfelméleti vizsgálódásokban:
Definíció. Az olyan gráfokat, amelyeknek pontjai két osztályba sorolhatók úgy, hogy a gráf minden éle a két osztály pontjait köti össze - tehát az olyan gráfokat, amelyekben azonos osztálybeli pontok között nem fut él -,
páros gráfoknak nevezzük.
Ez szemléletesen úgy is megfogalmazható, hogy egy gráf pontosan akkor páros, ha a pontjai kiszínezhetők két színnel úgy, hogy (minden pontot a két szín valamelyikére színezzük és) azonos színű pontok között nem fut él.
Ha a páros gráf olyan egyszerű gráf, amelyben a két osztály között futó összes él be van húzva, akkor a gráfot
teljes páros gráfnak nevezzük. Azt a teljes páros gráfot, amelynek két osztályában a pontok száma
n és
k, így jelöljük:
Kn,k
.
A
K1,k
gráfokat, ahol tehát egy pont az összes többivel össze van kötve és több él nincsen,
csillagnak nevezzük.
A páros gráfok egy fontos alternatív jellemzését a
4.22. feladat tartalmazza.
C) Feladatok
Feladat: 4.4.
Írjuk le másképp a
K2,2
és a
K3,3
teljes páros gráfot.
Feladat: 4.5.
Döntsük el a következő gráfokról, hogy páros gráfok-e:
a) Az a gráf, amelynek csúcsai egy kocka csúcsai, élei a kocka élei. (Lásd az
5.3a. feladat ábráját.)
b) Az a gráf, amelynek csúcsai egy ötszög csúcsai, élei az ötszög oldalai.
c) Az a gráf, amelynek csúcsai egy oktaéder csúcsai, élei az oktaéder élei.
d) Az a gráf, amelynek csúcsai egy szabályos hatszög csúcsai, élei a hatszög oldalai valamint leghosszabb átlói.
Feladat: 4.6.
Igaz-e, hogy páros gráf minden részgráfja is páros?
Feladat: 4.7.
Hogyan szól ,,gráfelméleti nyelven" a
K.I.18.8. feladat szövege? És a
K.I.18.9. feladat a) részének a szövege?
Feladat: 4.8.
Hogyan szól gráfelméleti nyelven a
4.1. feladatban kapott eredmény?
Feladat: 4.9.
Maximálisan hány éle lehet egy tízpontú páros gráfnak? És egy 11 pontúnak?
Feladat: 4.10.
Maximálisan hány éle lehet egy
n pontú páros gráfnak?
Feladat: 4.11.
Milyen
n-ekre van olyan
n pontú páros gráf, amelynek a komplementere is páros? Keressük meg az összes ilyen gráfot!
Feladat: 4.12.
Van-e olyan egyszerű páros gráf, amelyben a csúcsok fokszáma rendre 3,3,3,3,4,4,4,4?
Vagy bizonyítsuk be, hogy nincs ilyen, vagy adjuk meg az összeset!
Feladat: 4.13.
Van-e olyan egyszerű páros gráf, amelyben a csúcsok fokszáma rendre 3,3,3,3,3,4,4,5,6?
Feladat: 4.14.
Kutató munka:
Fogalmazzuk meg a
4.2. feladat eredményét páros gráfokkal!
* Fogalmazzunk meg áltánosabb állítást és próbáljuk bizonyítani! Melyik korábbi feladat gondolatmenetét alkalmazhatnánk?
Feladat: 4.15.
* Egy egyszerű gráfról azt tudjuk, hogy bármely három pontja között páros sok él fut. Mit mondhatunk még erről a gráfról? Adjunk szükséges és elégséges feltételt arra, hogy egy gráfnak meglegyen ez a tulajdonsága!
Reguláris páros gráfok
Feladat: 4.16.
[
176]
Legyen a sakktábla 64 mezejéből 16 mező oly módon kijelölve, hogy mind a 8 sor és mind a 8 oszlop éppen 2-2 kijelölt mezőt tartalmaz. Bebizonyítandó, hogy a kijelölt mezőkre mindenkor úgy lehet egy-egy bábut - éspedig 8 fehér és 8 fekete bábut - elhelyezni, hogy minden sorban és minden oszlopban pontosan 1 fehér és 1 fekete bábu álljon. (Kürschák-verseny, 1933.)
Feladat: 4.17.
Kutató munka:
A
Kn,n
teljes páros gráfok nyilván regulárisak. 2-reguláris páros gráfok a
2n-szögek csúcsai, illetve élei által alkotott gráfok. Rajzoljunk fel másfajta reguláris páros gráfokat, például 3-reguláris, 4-reguláris páros gráfokat! Mi mondható egy reguláris páros gráf osztályainak pontszámáról?
Feladat: 4.18.
Kutató munka:
a) Rajzoljunk olyan páros gráfot, amelynek tíz pontja van és 3-reguláris.
b) Milyen
n és
k számokra van
k-reguláris,
n-pontú páros gráf?
A reguláris páros gráfokra vonatkozó tételek később fognak sorra kerülni. A reguláris páros gráfok teljes párosításairól szóló általános tételt majd a K.III.3. fejezetben tárgyaljuk. De egy speciális esete már ebben a kötetben a 10.11. feladatban sorra kerül.
Páros gráfok és páros körök
Feladat: 4.19.
Kutató munka:
Állapítsuk meg, milyen
n-ekre páros gráf az a gráf,
a) amelynek csúcsai egy
n-szög csúcsai, élei a sokszög oldalai,
b) amelynek csúcsai egy
n-szög alapú hasáb, élei a hasáb élei?
Feladat: 4.20.
Definíció. Ha egy gráf egy részgráfja izomorf a
4.19. feladatban szereplő gráffal, azaz azzal a gráffal, amelynek csúcsai egy
n-szög csúcsai, élei a sokszög szomszédos csúcsait kötik össze, akkor ezt a részgráfot a gráf egy
n hosszúságú
körének nevezzük. Az
n hosszú kör jele:
Cn
.
Megjegyzés. A körre az
5. fejezet elején adni fogunk egy alternatív, tisztán gráfelméleti definíciót. Jelen céljainkra azonban ez a definíció is megfelel és jól mutatja a fogalom szemléletes jelentését.
Fogalmazzuk meg e definíció segítségével a
4.19. feladatban kapott állítást.
Feladat: 4.21.
Bizonyítsuk be, hogy páros gráfban nem lehet páratlan kör.
Feladat: 4.22.
Kutató munka:
A
4.21. feladat szerint páros gráfban nincs páratlan kör.
Vajon igaz-e az állítás megfordítása? Igaz-e, hogy ha egy gráfban minden kör páros, akkor a gráf páros gráf?
Páros gráfok és irányított gráfok
Feladat: 4.23.
Milyen összefüggéshez hasonlít a
4.8. feladatban kapott eredmény?
Megjegyzés. A 4.23. feladatban talált analógia a páros gráfok és az irányított gráfok között nem véletlen, vagy felszíni analógia. Erre utalt már a K.I.18.9. feladat is. Egy
n pontú irányított gráfot ugyanis mindig könnyen kódolhatunk egy olyan páros gráffal, amelynek mindkét osztályban
n pont van. Gondolatban megszámozzuk egytől
n-ig az irányított gráf pontjait is, a páros gráf
A osztályának a pontjait is,
B osztályának a pontjait is. Az
A osztály
i-edik pontját akkor és csak akkor kötjük össze a
B osztály
j-edik pontjával, ha az irányított gráfban van
i-ből
j-be mutató él.
Hasonlóan egy irányított gráffal kódolható minden olyan páros gráf is, amelynek két osztályában azonos számú pont van. Ha az irányított gráfban többszörös élek vannak, akkor a páros gráfban is lesznek és viszont. Némileg ,,ront" a helyzeten, hogy ebben az esetben az irányított gráfban keletkezhetnek hurokélek (ha a páros gráf két osztályának két azonos számú pontja között fut él).
Ennek a megfeleltetésnek a jelentősége majd később fog kidomborodni.
Feladat: 4.24.
Számozzuk meg egy négypontú tournament pontjait és legyenek pontosan azok az élek behúzva, amelyek kisebb számú pontból nagyobb számúba mutatnak. Rajzoljuk meg ennek az irányított gráfnak a páros gráf megfelelőjét!
Mit jelent az az irányított gráfban, ha a neki megfelelő páros gráfban van izolált pont?
Feladat: 4.25.
Rajzoljuk fel a következő páros gráfoknak megfelelő irányított gráfot:
a)
K2,2
,
b)
K3,3
,
c) a hatszög csúcsai a gráf csúcsai, a hatszög oldalai a gráf élei,
d) a kocka gráfja, lásd az
5.3a. feladatot.
Mit vehetünk észre a c) és d) feladatnál?
További, páros gráfokról szóló feladat például a 8.4., a 8.5., a 8.7., a 8.20. feladat.
Az egész
ALG.II.3. fejezet páros gráfokkal (illetve feszítő páros részgráfokkal) foglalkozik. A páros gráfokra vonatkozó König-tételeket pedig a 11-12. osztályos kötetben tárgyaljuk majd.