Föreläsning 7

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.

1. Kur många bågar har den kompletta grafen med 10 noder?
2. Vad menas med att två grafer är isomorfa?
3. 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?
4. Bestäm incidensmatrisen till grafen på sidan 264.
5. Bestäm grannmatrisen till grafen på sidan 264.