Informatika1-2012/HF5

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:

• 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.