Számítástudomány elemei gyakorlat
3. feladatsor (2002. szept. 26.)

Az előző óráról maradt:

1. Egy teljes gráf ponthalmaza $\{x_1,x_2,...,x_s,y_1,y_2,...,y_t\}$. Az $\left(x_i,x_j\right)$ élek költsége (súlya) 1 Ft, az $\left(y_i,y_j\right)$ éleké 2 Ft, az $\left(x_i,y_j\right)$ éleké pedig 3 Ft. Mennyibe kerül a legolcsóbb feszítőfa? (ZH, 2000. márc.)

2. Hány olyan fa adható meg az $1,2,...,100$ csúcsokon, melynek van olyan éle, amit elhagya a maradék gráf két komponensének pontjai rendre az $1,2,...,50$ ill. az $51,52,...,100$ csúcsok?

Új feladatok:

1. Van-e az alábbi gráfnak Hamilton-köre ill. -útja? (Vizsga, 2001. jún.)

   
   

   $$\unitlength 1mm \begin{picture}(40,20)(-20,-10) \put(-20,-10... ...-10){\line(0,1){20}} \put(20,-10){\line(0,1){20}} \end{picture}$$
   
   

2. Hány Hamilton-köre ill. -útja van a $K_{n,n}$ teljes páros gráfnak? (Vizsga, 1999. máj.)

3. A $G$ 3-reguláris egyszerű gráfra teljesül, hogy $\vert E(G)\vert=2\cdot \vert V(G)\vert-3$. Bizonyítsuk be, hogy $G$-ben van Hamilton-kör! (ZH, 1999. márc.)

4. A $G$ egyszerű gráf pontjai az $1,2,...,100$ számok. Az $i$ és $j$ pontok pontosan akkor vannak éllel összekötve, ha $\vert i-j\vert\leq2$. Van-e $G$-ben Euler-kör ill. Euler-út? (ZH, 2000. márc.)

5. A $G$ gráf pontjai egy 10 elemű halmaz 2 elemű részhalmazainak felelnek meg. Két pont akkor van összekötve éllel, ha a pontoknak megfelelő két részhalmaz diszjunkt. Van-e a $G$ gráfban Euler- ill. Hamilton-kör? (Pótzh, 1999. máj.)

6. Egy 12 fős társaságban mindenki legalább 6 embert ismer (az ismeretség kölcsönös). Bizonyítsuk be, hogy a társaság leültethető egy kerek asztal köré úgy, hogy mindenki ismerje a szomszédait! (Pótzh, 2001. dec.)

7. A $G$ összefüggő gráfban minden pont foka páros. Bizonyítsa be, hogy ha $G$-nek páros sok éle van, akkor létezik $G$-nek olyan $H$ részgráfja, hogy $V(G)=V(H)$, és minden pont $H$-beli foka éppen fele a $G$-beli fokának. (ZH, 2000. máj.)

8. Legyen $n\geq3$ és legyen a $G$ gráf pontjainak halmaza az $n$ hosszúságú $0-1$ sorozatok halmaza. A gráf két pontja között akkor és csak akkor van él, ha a nekik megfelelő két sorozat legalább 2 helyen eltér. Milyen $n$ esetén van $G$-ben Euler-körséta? (Vizsga, 2000. jún.)