Reduktioner, omvänd föreläsning

Förberedelser inför föreläsningen

Titta på följande video:

Läs i kursboken KT: sida 451-459.

Uppgifter under föreläsningen

  1. Generell viktad matchning
    Det finns en polynomisk algoritm som löser problemet maximal maxmatchning, som definieras så här:
    Indata: oriktad graf G=(V,E), kantvikter c(e) som är naturliga tal
    Utdata: matchning M (en delmängd av E) som dels innehåller så många kanter som möjligt och dels har så stor sammanlagd vikt som möjligt.
    Beskriv en algoritm för problemet minimal maxmatchning, som är motsvarande problem där den sammanlagda vikten av kanterna i maxmatchningen ska vara minimal.
    Använd en reduktion av minimal maxmatchning till maximal maxmatchning!

  2. Problemet maximal klick definieras så här:
    Indata: oriktad graf G
    Utdata: antal hörn i den största klicken (fullständiga delgrafen) i G
    Problemet maximal oberoende mängd definieras så här:
    Indata: oriktad graf G
    Utdata: antal hörn i den största oberoende mängden (hörn utan kanter emellan) i G

Lösning till uppgift 1 Download Lösning till uppgift 1

Lösning till uppgift 2 Download Lösning till uppgift 2