Föreläsning 9
Tid: Måndag 5 december 2011 kl 10:00 - 12:00
Plats: Ka-C1 (Isafjordsg 20-26 Trapph. C)
Aktivitet: Föreläsning
Lärare: Göran Andersson ()
Studentgrupper: TAFFK2, TIDAB2, TIEDB2, TKOMK2
Info:
Träd, färgning
Böiers kap 9.5
Mål
att kunna redogöra för följande begrepp:
- träd, uppspännande träd
- kromatiskt tal, kromatiskt polynom
- kontraktion
- fyrfärgssatsen
att kunna:
- använda Kruskal's algoritm
- använda Dijkstra's algoritm
- bestämma kromatiskt tal
- bestämma kromatiskt polynom
- tillämpa färgning i enkla fall
A-uppgifter:
- Vad menas med kromatiskt tal och kromatiskt polynom?
- Vad menas med en kontraktion?
- Vad innebär fyrfärgsproblemet? Vad är lösningen?
- Vad är kromatiska talen för graferna på sidan 256?
- Nämn ett praktiskt problem där färgning kan tillämpas?