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
- 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!
- 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