Informatika1-2013/HF6

6. Házi Feladat

Döntsd el egy tetszőleges, irányítatlan gráfról, hogy páros gráf-e, vagy nem.

Instrukciók:

• A feladat egy SAGE-ben írt függvény megírása.
• 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ések:
  • 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. Másképp fogalmazva a gráf csúcsai kiszínezhetőek két színnel úgy, hogy élek csak különböző színű csúcsok között futnak.
• 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.

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.
• 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, mely még nincs benne egyik halmazban sem.