Informatika1-2012/HF5
A MathWikiből
(Változatok közti eltérés)
| (egy szerkesztő 4 közbeeső változata nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
| − | '''5. Házi Feladat''' | + | ===='''5. Házi Feladat'''==== |
(kitűző/javító: Pálovics Róbert) | (kitűző/javító: Pálovics Róbert) | ||
| 12. 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 | + | * A függvény 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 | + | * A függvény legyen képes '''nem összefüggő''' gráfok kezelésére is! |
| + | * '''A házit most is a következőképp küldjétek:''' A sage worksheetet a szokásos konvenció alapján (T2_HF5_kovacspisti) nevezzétek el, majd osszátok meg a sage szerveren palovics felhasználóval. | ||
Segítség: | Segítség: | ||
| 25. sor: | 26. sor: | ||
* A szomszédoknak mindig ellentétes színűeknek kell lennie, mint a vizsgált csúcsnak. | * 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. | * 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]} | + | * Példa: A gráf: {0:[1,2], 1:[2,3]}, az algoritmus lépései: |
** 0. lépés: minden csúcsra colors[i]=-1, egyik csúcs sem "színes" | ** 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". | ** 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 | + | ** 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 algoritmus 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 fentitől eltérő, egyéb megoldásokat is elfogadok, mindez csak segítség. | ||
A lap jelenlegi, 2012. október 23., 12:03-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 függvény 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 függvény legyen képes nem összefüggő gráfok kezelésére is!
- A házit most is a következőképp küldjétek: A sage worksheetet a szokásos konvenció alapján (T2_HF5_kovacspisti) nevezzétek el, majd osszátok meg a sage szerveren palovics felhasználóval.
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]}, az algoritmus lépései:
- 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 algoritmus 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.
