9. FEJEZET: Független pontok és élek
Folytatjuk a gráfelméleti alapfogalmak bevezetését és bebizonyítunk néhány egyszerű, a független pontokkal illetve élekkel kapcsolatos tételt.
Független élek és pontok
A következő feladatokhoz célszerű átismételni a független élek korábban bevezetett fogalmát (lásd az 1.15. feladatot): a
G gráf éleinek egy halmazát akkor nevezzük függetlennek, ha közülük semelyik kettőnek nincs közös végpontja. Ilyenkor gyakran egyszerűen független élekről beszélünk.
Jelölés. A
G gráfban található független élek maximális számát
ν(G)-vel jelöljük.
Feladat: 9.1.
Határozzuk meg
ν(G)-t (vagyis határozzuk meg a független élek maximumát) az
n pontú teljes gráfban!
Feladat: 9.2.
Határozzuk meg
ν(G)-t (vagyis határozzuk meg a független élek maximumát a következő gráfokban),
a) ha
G csúcsai egy kocka csúcsai, élei a kocka élei;
b) ha
G csúcsai egy oktaéder csúcsai, élei az oktaéder élei;
c) ha
G csúcsai egy ikozaéder csúcsai, élei az ikozaéder élei.
Feladat: 9.3.
Határozzuk meg
ν(G)-t (vagyis határozzuk meg a független élek maximumát a következő gráfokban),
a) ha
G egy ötélű kör (
G=
C5
);
b) ha
G egy
n pontú kör (
G=
Cn
);
Feladat: 9.4.
Igaz-e, hogy ha egy
2n pontú gráfban van Hamilton-kör, akkor van
n független éle?
Feladat: 9.5.
a) Mekkora lehet a legnagyobb kör egy olyan gráfban, amelyben nincs
k+1 darab független él?
b) A
G gráfról tudjuk a következőket: nincs benne
k+1 független él, és van benne
C2k+1
. Mit mondhatunk ennek a gráfnak a komponenseiről? Hány éle lehet maximálisan ennek a gráfnak?
Feladat: 9.6.
a) Egy
n pontú egyszerű gráfban nincs két független él. Legfeljebb hány éle lehet?
b) Adjuk meg az összes olyan
n pontú gráfot, amelyben nincs két független él, de erre a tulajdonságra ,,kritikus", azaz bármely él behúzásával már keletkezik két független él.
Feladat: 9.7.
* Egy
n pontú egyszerű gráfban a független élek maximális száma
k. Bizonyítsuk be, hogy ha
n≥2k+2, akkor a gráfnak legfeljebb
kn-k éle van.
Mi a helyzet
n=2k+1 pont esetén?
Megjegyzés. Ez a becslés
k=1-re pontos, de
k>1-re nem az. A maximális élszám kicsit kevesebb, mint
kn-k. A különbség azonban már nem függ
n-től, csak
k-tól. Az élszám pontos felső korlátjának bizonyítása azonban általában körülményes, ezért csak a legegyszerűbb
k=2 esetben adjuk majd fel a
9.9. feladatban.
Feladat: 9.8.
* Legyen egy
n pontú egyszerű gráfban a független élek maximális száma
k és
E={
x1
y1
,
x2
y2
…,
xk
yk
} egy független élrendszer, továbbá jelölje
T a gráf többi pontját. Bizonyítsuk be, hogy ekkor
-
T pontjai között nem fut él,
-
T bármely két pontjából együttesen legfeljebb
2k él indul
E pontjaiba, tehát
-
T bármely két pontjának fokszáma együtt legfeljebb
2k.
Feladat: 9.9.
A
9.7. feladat
k=2-re azt mondja ki, hogy ha
n legalább hat, és egy
n pontú egyszerű gráfban nincs három független él, akkor élszáma legfeljebb
2n-2. Vagyis ha egy
n pontú egyszerű gráfnak legalább
2n-1 éle van, akkor van benne három független él. Ez az állítás egy kicsit javítható:
* Bizonyítuk be, hogy ha egy
n>6 pontú egyszerű gráfban legalább
2n-2 él van, akkor van benne három független él. Ha egy
n pontú egyszerű gráfban
2n-3 él van és nincs benne három független él, akkor van két pontja, amely az összes élt lefogja, a gráf
n-2 darab olyan háromszögből áll, amelyek egy élben illeszkednek.
Teljes párosítások
Feladat: 9.10.
Egy hattagú társaságban, ahol kölcsönösek az ismeretségek, mindenkinek három ismerőse van. Bizonyítsuk be, hogy a hat ember leültethető egy asztal köré úgy, hogy mindenki ismerje a vele szemben ülőt.
Fogalmazzuk meg az állítást gráfelméleti nyelven is!
Feladat: 9.11.
Kutató munka:
Próbáljuk általánosítani a
9.10. feladat állítását!
A
9.11. feladatban - de már a
9.2. feladatban is - fontos szerepe volt az olyan független élrendszernek, amely a gráf minden pontját lefedi. Ha ugyanis találunk független éleket, amelyek a gráf összes pontját lefedik, biztosak lehetünk, hogy ez a független élrendszer maximális. (Maximális a korábban definiált mindkét értelemben:
nem bővíthető további független éllel és
nincsen több élből álló független élrendszer.) Ez is indokolja, hogy az ilyen élrendszereknek kitüntetett szerepe van a gráfelméletben. Külön nevük is van:
Definíció. Ha a gráfban van olyan független élrendszer, amely a gráf összes pontját lefedi, akkor az ilyen élrendszert a gráf pontjai közötti
teljes párosításnak, vagy a gráf 1-
faktorának nevezzük.
Kifejezhetjük ezt úgy is, hogy teljes párosításnak a gráf 1-reguláris feszítő részgráfjait nevezzük (ha van ilyen részgráfja), ám ez sokkal kevésbé szemléletes kifejezésmód.
Nyilvánvaló, hogy teljes párosítás csak páros pontszámú gráfban lehet.
Mint látjuk, fontos szerepe van a gráf pontjait lefedő élrendszereknek is, ezeket egyszerűen lefedő élrendszernek hívjuk:
Definíció. Egy gráf élhalmazának egy részhalmazát akkor és csak akkor nevezzük
lefedő élrendszernek - vagy egyszerűen
lefedő éleknek -, ha végpontjaik kiadják a gráf összes pontját. Nyilván nincs ilyen élhalmaz, ha a gráfban van izolált pont. Minden más esetben van.
A
G gráf pontjait lefedő minimális elemszámú élrendszer jele
ϱ(G).
Érdemes megfontolni még a következőt. Ugyanúgy, ahogy egy összefüggő gráf faváza egyszerre minimális összefüggő és maximális körmentes feszítő részgráf, ugyanúgy a teljes párosítás egyszerre maximális független élrendszer és minimális lefedő élrendszer. Arra a kérdésre, hogy milyen gráfoknak van faváza egyszerű a válasz: az összefüggő gráfoknak. Nem ilyen egyszerű a válasz viszont arra a kérdésre, hogy milyen gráfokban van teljes párosítás. Az erre vonatkozó Tutte-tételt a GR.III. kötetben fogjuk kimondani.
Feladat: 9.12.
Kutató munka
A favázak esetében igaz volt, hogy ha egy összefüggő gráf körmentes feszítő részgráfja nem bővíthető további éllel úgy, hogy körmentes maradjon, akkor a részgráf biztosan faváz. Igaz-e hasonló állítás a maximális független élrendszerekre? Azaz: mi a válasz a következő kérdésre:
A
G gráfnak találtunk egy tovább nem bővíthető független
E élrendszerét, azaz bárhogyan hozzávéve
E-hez a gráf egy további
e élét az
E∪{e} élhalmaz már nem független. Következik-e ebből, hogy
E maximális független élrendszer?
Feladat: 9.13.
Hány teljes párosítás található a kocka gráfjában?
Feladat: 9.14.
Hány teljes párosítása van a
2.16. feladat megoldásánál szereplő
G gráfnak?
Feladat: 9.15.
Hány teljes párosítása van a
8.19. feladat ábráján szereplő gráfoknak?
Feladat: 9.16.
* Hány teljes párosítása van a
8.13. feladat megoldásában szereplő gráfnak?
Feladat: 9.17.
Egy hatpontú körbe behúztuk a szemközti pontokat összekötő éleket. Hány teljes párosítása van az így kapott gráfnak?
Feladat: 9.18.
Igazoljuk, hogy egy 2-reguláris páros gráfban van teljes párosítás.
Igaz-e, hogy egy 2-reguláris gráfban csak akkor van teljes párosítás, ha páros gráf?
A 9.18. feladat az egyik legegyszerűbb esete a reguláris páros gráfok teljes párosításaira vonatkozó általános König-tételnek. Ezt és az általános König-tételt a K.III.3. fejezetben fogjuk tárgyalni. Még egy speciális esetét tárgyalja a 10.11. feladat.
Feladat: 9.19.
Hány teljes párosítása van a
Kk,n
teljes páros gráfnak?
Feladat: 9.20.
Hány teljes párosítása van a
Kn
teljes gráfnak?
Független pontrendszerek és lefogó pontrendszerek
Természetesen nemcsak független élekről, hanem
független pontokról is van értelme beszélni:
Definíció. Egy gráf pontjainak valamely halmazát akkor és csak akkor nevezzük
függetlennek, ha közülük semelyik kettő között nem fut él a gráfban.
Például a teljes gráfok pontosan azok az egyszerű gráfok, amelyekben semelyik két pont nem független, az üres gráfok pedig pontosan azok, amelyekben a gráf egész ponthalmaza független.
A
G gráf független pontjainak maximális számát
α(G)-vel jelöljük.
Feladat: 9.21.
Adjunk új definíciót a páros gráfokra a független pontok segítségével!
Feladat: 9.22.
Bizonyítsuk be, hogy egy
n pontú páros gráfban van legalább
⌈(n+1)/2⌉ független pont.
Feladat: 9.23.
Egy 25 tagú társaságban minden ember legfeljebb öt másikkal fogott kezet. Igazoljuk, hogy kiválasztható a társaság öt tagja úgy, hogy közülük semelyik kettő nem fogott kezet.
Igaz-e ugyanez az állítás minden 24 tagú társaságra is?
Fogalmazzuk meg a feladatot gráfelméleti nyelven és próbáljuk általánosítani.
Feladat: 9.24.
Legalább hány pontot kell elhagyni (a belőle induló élekkel együtt) a kocka gráfjából, hogy a maradó pontok között már ne fusson él?
A 9.24. feladatban olyan ponthalmazt kerestünk, amelynek elhagyása után a maradó pontok között nem fut él a gráfban. Az ilyen ponthalmazokat úgy is jellemezhetjük, hogy a gráf minden élének legalább egy végpontját tartalmazzák. Ez ismét egy fontos fogalom:
Definíció. Ha a
G gráf pontjainak egy
H részhalmaza olyan, hogy minden élnek legalább az egyik végpontja
H-ban van - tehát ha
G-ből elhagyjuk
H-t és a belőle induló éleket, akkor üres részgráfot kapunk -, akkor azt mondjuk, hogy
H lefogja a gráf éleit.
A
G gráf lefogó pontjainak minimális számát
τ(G)-vel jelöljük.
Feladat: 9.25.
Minimálisan hány ponttal lehet lefogni
a) egy
n pontú teljes gráf éleit;
b) azt a gráfot, amelynek pontjai egy kocka csúcsai, élei pedig a kocka élei;
c) az ötpontú kör (
C5
) éleit;
d) a
2n+1-pontú kör (
C2n+1
) éleit?
Feladat: 9.26.
Kutató munka:
Keressünk összefüggést egy gráf független éleinek maximuma és a lefogó pontjainak minimuma között és próbáljuk igazolni sejtésünket! Próbáljuk felhasználni a
9.24. feladat gondolatmenetét.
Feladat: 9.27.
Mutassunk példát olyan gráfra, ahol a független élek maximális száma kisebb a lefogó pontok minimumánál.
Lehet-e akármilyen nagy a különbség a lefogó pontok minimuma és a független élek maximuma között?
Mit mondhatunk a lefogó pontok minimumának és a független élek maximumának különbségéről összefüggő gráfok esetén?
Megjegyzés. Több ilyen fogalompár is van a gráfelméletben, amelyek közül az egyik maximuma alső becslést ad a másik minimumára. A gráfelmélet egyik érdekes területe azzal foglalkozik, hogy milyen gráfokban áll fenn az ilyen fogalompároknál az egyenlőség.
Feladat: 9.28.
Melyik állítás igaz az alábbiak közül:
Ha egy gráfban nincs
k+1 független pont, akkor az élei lefoghatók
a)
k ponttal;
b)
2k-1 ponttal,
c)
2k ponttal.
Feladat: 9.29.
Kutató munka:
a) Keressünk összefüggést egy (hurokél nélküli) gráf lefogó pontjai és független ponthalmazai között. Fogalmazzunk meg sejtést és próbáljuk bizonyítani!
b) Milyen kapcsolat lehet egy (hurokél nélküli) gráf független pontjainak maximális száma és lefogó pontjainak minimális száma között?
Gallai tétele
Feladat: 9.30.
Kutató munka:
Keressünk olyan fogalmat, amely ugyanolyan viszonyban van a független pontokkal, amilyen viszonyban van a független él fogalma a lefogó pontok fogalmával!
Feladat: 9.31.
Állapítsuk meg, hány legalább hány él kell ahhoz, hogy lefedjük
a) a kocka gráfját,
b) egy
n pontú kört,
c) egy
n pontú teljes gráfot,
d) az oktaéder gráfját,
e) a
Kk,l
teljes páros gráfot,
f) a
8.13. feladat megoldásában szereplő gráfot (l. az ottani ábrát),
g) az izokaéder gráfját,
h) az
n pontú csillagot,
i) a
k darab pontdiszjunkt háromszögből álló gráfot?
Feladat: 9.32.
Kutató munka:
Milyen egyszerű összefüggést állapíthatunk meg a független élek és a lefedő élek között a
9.31. feladat alapján?
Feladat: 9.33.
Kutató munka:
Keressünk összefüggést a független élek maximális száma, a lefedő élek minimális száma és a gráf pontszáma között izolált pont nélküli gráfban és próbáljuk bizonyítani sejtésünket.