Számítástudomány elemei gyakorlat
6. feladatsor (2002. okt. 17.)

1. Keressünk maximális párosítást az alábbi gráfban! (Vizsga, 2001. jún.)
   
   
   $$\unitlength 1.2cm \begin{picture}(4,1) \multiput(0,0)(1,0){5... ...ultiput(0,1)(1,0){2}{\line(3,-1){3}} \end{picture}\vspace{1mm}$$
   
   

2. 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?

3. Mekkora a maximális párosítás mérete a következő gráfban? (ZH, 2001. márc.)
   
   $$\unitlength .5cm \begin{picture}(14,8) \put(4,0){\circle*{.4... ...put(4,6){\line(0,1){2}} \put(10,6){\line(0,1){2}} \end{picture}$$
   
   

4. Adott egy $G=(A,B)$ egyszerű páros gráf, ahol az osztályok $\vert A\vert=3,\;\vert B\vert=n\geq3$ méretűek, és az élek száma $\vert E(G)\vert=2n+1$. Bizonyítsuk be, hogy van $G$-nek olyan párosítása, mely lefedi az $A$ osztályt! (ZH, 2000. márc.)

5. A $G=(A,B,E)$ páros gráfra $\vert A\vert=\vert B\vert$, és az $A$ minden valódi $X$ részhalmazára $(X\ne\emptyset,\;X\ne A)$ teljesül, hogy $\vert X\vert<\vert N(X)\vert$, ahol $N(X)$ az $X$ szomszédainak halmazát jelöli. Igazoljuk, hogy ekkor $G$ egy tetszőleges éle kiegészíthető teljes párosítássá! (Vizsga, 1999. máj.)

6. Mutassa meg, hogy egy fának nem lehet két különböző teljes párosítása! (Vizsga, 2001. jún.)

7. Bizonyítsuk be, hogy ha egy $n$ pontú páros gráfban létezik teljes párosítás, akkor $\alpha=\frac{n}2$, ahol $\alpha$ a független pontok maximális számát jelöli. (Pótzh, 2001. dec.)