Next: About this document ...
Számítástudomány elemei gyakorlat
6. feladatsor (2002. okt. 17.)
- Keressünk maximális párosítást az alábbi gráfban! (Vizsga,
2001. jún.)
- Egy osztályban az iskolai asztalitenisz-bajnokságra
fiúpárosokat szeretnének összeállítani. A tíz pingpongozni tudó
fiúból Andris és Balázs csak Marcival akar egy párban lenni, Csaba
és Dani Norbihoz, Ede és Karcsi pedig Oszihoz ragaszkodik. Laci
szívesen lenne Marcival, Norbival vagy akár Oszival is. Az utóbbi
három bárki oldalán kiállna, aki őket választja. Hány pár
állítható így össze?
- Mekkora a maximális párosítás mérete a következő gráfban?
(ZH, 2001. márc.)
- Adott egy
egyszerű páros gráf, ahol az osztályok
méretűek, és az élek száma
.
Bizonyítsuk be, hogy van
-nek olyan párosítása, mely lefedi az
osztályt! (ZH, 2000. márc.)
- A
páros gráfra
, és az
minden
valódi
részhalmazára
teljesül, hogy
, ahol
az
szomszédainak halmazát jelöli.
Igazoljuk, hogy ekkor
egy tetszőleges éle kiegészíthető teljes
párosítássá! (Vizsga, 1999. máj.)
- Mutassa meg, hogy egy fának nem lehet két különböző teljes
párosítása! (Vizsga, 2001. jún.)
- Bizonyítsuk be, hogy ha egy
pontú páros gráfban létezik
teljes párosítás, akkor
, ahol
a
független pontok maximális számát jelöli. (Pótzh, 2001. dec.)
Next: About this document ...
Veto Balint
2002-10-17