Informatika1-2012/HF5

A MathWikiből
A lap korábbi változatát látod, amilyen Rpalovics (vitalap | szerkesztései) 2012. október 23., 11: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.
Személyes eszközök