Next: About this document ...
Számítástudomány elemei gyakorlat
3. feladatsor (2002. szept. 26.)
Az előző óráról maradt:
- Egy teljes gráf ponthalmaza
. Az
élek költsége (súlya) 1 Ft, az
éleké 2 Ft,
az
éleké pedig 3 Ft. Mennyibe kerül a
legolcsóbb feszítőfa? (ZH, 2000. márc.)
- Hány olyan fa adható meg az
csúcsokon, melynek
van olyan éle, amit elhagya a maradék gráf két komponensének
pontjai rendre az
ill. az
csúcsok?
Új feladatok:
- Van-e az alábbi gráfnak Hamilton-köre ill. -útja? (Vizsga,
2001. jún.)
- Hány Hamilton-köre ill. -útja van a
teljes páros
gráfnak? (Vizsga, 1999. máj.)
- A
3-reguláris egyszerű gráfra teljesül, hogy
. Bizonyítsuk be, hogy
-ben van
Hamilton-kör! (ZH, 1999. márc.)
- A
egyszerű gráf pontjai az
számok. Az
és
pontok pontosan akkor vannak éllel összekötve, ha
. Van-e
-ben Euler-kör ill. Euler-út? (ZH, 2000.
márc.)
- A
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
gráfban Euler- ill. Hamilton-kör? (Pótzh, 1999. máj.)
- 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.)
- A
összefüggő gráfban minden pont foka páros. Bizonyítsa
be, hogy ha
-nek páros sok éle van, akkor létezik
-nek olyan
részgráfja, hogy
, és minden pont
-beli foka
éppen fele a
-beli fokának. (ZH, 2000. máj.)
- Legyen
és legyen a
gráf pontjainak halmaza az
hosszúságú
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
esetén van
-ben
Euler-körséta? (Vizsga, 2000. jún.)
Next: About this document ...
Veto Balint
2002-10-10