Föreläsning 7
Tid: Måndag 21 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
Grafteori
Böiers 9.1
Exempel 5 kan läsas kursivt
Mål
att kunna redogöra för grundläggande terminologi och definitioner i grafteori, såsom:
- G=(V,E)
- riktad, viktad graf, multigraf
- väg, cykel, grad
- kompletta grafen, komplementgraf
- sammanhängande
- isomorfa grafer
- incidensmatris, grannmatris
att kunna
- tillämpa dessa begrepp vid problemlösning
- avgöra om två grafer är isomorfa (ankla fall)
A-uppgifter:
Med graf menas ej multigraf.
- Kur många bågar har den kompletta grafen med 10 noder?
- Vad menas med att två grafer är isomorfa?
- En öglefri sammanhängande graf har 12 kanter. Hur många hörn har grafen om alla hörn har samma grad? Vilken är denna grad?
- Bestäm incidensmatrisen till grafen på sidan 264.
- Bestäm grannmatrisen till grafen på sidan 264.