Informatika1-2012/HF5
A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „'''5. Házi Feladat''' (kitűző/javító: Pálovics Róbert) Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, i…”) |
|||
3. sor: | 3. sor: | ||
Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, instrukciók: | Döntsd el egy '''tetszőleges, irányítatlan gráfról''', hogy páros gráf-e, vagy nem. Segítség, instrukciók: | ||
+ | |||
+ | Instrukciók: | ||
+ | |||
* A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre. | * A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre. | ||
* A függvény '''bemenete''' egy tetszőleges, irányítatlan (Graph) gráf. | * A függvény '''bemenete''' egy tetszőleges, irányítatlan (Graph) gráf. | ||
9. sor: | 12. sor: | ||
** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1''' | ** A csúcsok száma a gráfban '''N''', a csúcsok indexelése: '''0..N-1''' | ||
** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek. | ** Ha a gráf páros, akkor a csúcsai kettéoszthatók '''A''' és '''B''' diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek. | ||
− | * A program minden esetben adjon vissza ('''return''') egy listát ('''colors'''): | + | * A program minden esetben adjon vissza ('''"return"''') egy listát ('''colors'''): |
** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen. | ** Ha a gráf '''nem''' páros, akkor ez egy '''üres''' lista legyen. | ||
**Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét": | **Ha a gráf páros, akkor ez a lista legyen '''N hosszúságú''', és colors[i] adja meg az i-edik csúcs "színét": | ||
*** colors[i]=1, ha az i. csúcs az A halmazba tartozik. | *** colors[i]=1, ha az i. csúcs az A halmazba tartozik. | ||
*** colors[i]=0, ha az i. csúcs a B halmazba tartozik. | *** colors[i]=0, ha az i. csúcs a B halmazba tartozik. | ||
+ | * A program legyen képes '''nem összefüggő''' gráfok kezelésére is! | ||
+ | |||
+ | Segítség: | ||
+ | |||
+ | * A megoldáshoz az egyszerű, irányított gráf paritását meghatározó algoritmust, és a szélességi keresés algoritmusát kell végiggondolni. | ||
+ | * Kezdetben mindenki színe legyen -1, azaz minden i esetén colors[i]=-1 | ||
+ | * A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak. | ||
+ | * A nem összefüggő gráfok esetén a BFS algoritmust mindig újra kell indítani, legyen ez mindig a colors[] listában az első olyan csúcs, aki még nincs benne egyik halmazban sem. | ||
+ | * Példa: A gráf: {0:[1,2], 1:[2,3]} | ||
+ | ** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes" | ||
+ | ** 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes". | ||
+ | ** 2. lépés: a BFS ezután megvizsgálja az 1. csúcsot. Mivel colors[1]=1, ezért colors[2]=0 és colors[3]=0 kéne legyen. Azonban a 2. csúcs már az 1. lépés miatt színes: colors[2]=1 ellentétes színű, mint amilyenre most kéne színezni --> az elgoritmus leáll, ez a gráf nem lehet páros gráf. | ||
+ | |||
+ | * A fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség. |
A lap 2012. október 23., 11:05-kori változata
5. Házi Feladat (kitűző/javító: Pálovics Róbert)
Döntsd el egy tetszőleges, irányítatlan gráfról, hogy páros gráf-e, vagy nem. Segítség, instrukciók:
Instrukciók:
- A feladat egy SAGE-ben írt függvény megírása, mely képes válaszolni a fenti kérdésre.
- A függvény bemenete egy tetszőleges, irányítatlan (Graph) gráf.
- A program "print" függvénnyel írja ki a kimenetre a gráf párosságát ("A gráf páros", vagy "A gráf nem páros gráf").
- Jelölés a továbbiakhoz:
- A csúcsok száma a gráfban N, a csúcsok indexelése: 0..N-1
- Ha a gráf páros, akkor a csúcsai kettéoszthatók A és B diszjunkt halmazokra úgy, hogy csak ezen két halmaz között vannak élek.
- A program minden esetben adjon vissza ("return") egy listát (colors):
- Ha a gráf nem páros, akkor ez egy üres lista legyen.
- Ha a gráf páros, akkor ez a lista legyen N hosszúságú, és colors[i] adja meg az i-edik csúcs "színét":
- colors[i]=1, ha az i. csúcs az A halmazba tartozik.
- colors[i]=0, ha az i. csúcs a B halmazba tartozik.
- A program legyen képes nem összefüggő gráfok kezelésére is!
Segítség:
- A megoldáshoz az egyszerű, irányított gráf paritását meghatározó algoritmust, és a szélességi keresés algoritmusát kell végiggondolni.
- Kezdetben mindenki színe legyen -1, azaz minden i esetén colors[i]=-1
- A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak.
- A nem összefüggő gráfok esetén a BFS algoritmust mindig újra kell indítani, legyen ez mindig a colors[] listában az első olyan csúcs, aki még nincs benne egyik halmazban sem.
- Példa: A gráf: {0:[1,2], 1:[2,3]}
- 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes"
- 1. lépés: A BFS elindul a 0. csúcsból, elkezd színezni: colors[0]=0, colors[1]=1, colors[2]=1. Ezt azért teheti meg, mert a 0,1,2 csúcsok közül még egyik sem "színes".
- 2. lépés: a BFS ezután megvizsgálja az 1. csúcsot. Mivel colors[1]=1, ezért colors[2]=0 és colors[3]=0 kéne legyen. Azonban a 2. csúcs már az 1. lépés miatt színes: colors[2]=1 ellentétes színű, mint amilyenre most kéne színezni --> az elgoritmus leáll, ez a gráf nem lehet páros gráf.
- A fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség.