Informatika1-2012/HF5
A MathWikiből
A lap korábbi változatát látod, amilyen Rpalovics (vitalap | szerkesztései) 2012. október 23., 12:03-kor történt szerkesztése után volt.
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.