Föreläsning 8
Tid: Måndag 28 november 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:
Eulergrafer, Hamiltongrafer, planära grafer
Böiers 9.2, 9.3, 9.4
Mål
att kunna redogöra och tillämpa för följande begrepp:
- Eulergraf, Eulercykel, Eulerväg
- Hamiltongraf, Hamiltoncykel, Hamiltonväg
- planär graf
- Eulers polyederformel
- homeomorfa grafer
att kunna
- tillämpa ovanstående begrepp i problemlösning
A-uppgifter:
- Vad menas med Eulergraf, Hamiltongraf, Planär graf?
- Vilka av graferna i uppgift 9.22 är Eulergrafer?
- Ge exempel på en graf med minst fem hörn som har en Hamiltonväg men ingen Eulerväg?
- En öglefri sammanhängande planär graf med 16 kanter. Om alla hörn har grad 4, hur många delytor avgränsas av grafen?
- Vad menas med att två grafer är homeomorfa?