21 Grafteori Flashcards
21.1 Graf
En graf G består av en endelig, ikke-tom mengde V av noder og en mengde E av kanter. Hver kant i E er en mengde {u, v}, hvor u og v er to forskjellige noder. Vi sier at {u, v} forbinder u og v og at {u, v} ligger inntil u og v. To noder kalles naboer hvis de forbindes av en kant.
21.2 Løkker og parallelle kanter
En kant som går fra en node til seg selv i en multigraf kalles en løkke.To eller flere kanter som forbinder de samme nodene kalles parallelle kanter. En multigraf kalles enkel hvis den hverken har løkker eller parallelle kanter.
21.3 Rettet graf
En rettet graf er definert som en graf, men hvor kantene er ordenede par 〈u, v〉 i stedet for mengder {u, v}.
21.4 Tom graf
En graf uten kanter kalles en tom graf eller en nullgraf.
21.5 Komplett graf
En enkel graf er komplett hvis hver node er nabo med enhver annen node. Den komplette grafen med n noder kalles Kn.
21.6 Komplement
Hvis G er en graf, er komplementet til G grafen som har de samme nodene som G, men hvor to noder er naboer hvis og bare hvis nodene ikke er naboer i G. Vi skriver Ḡ for komplementet til G.
21.7 Graden til en node
Graden til en node v er antall kanter som ligger inntil v. En løkke teller som to kanter. Med deg(v) mener vi graden til v. En node med grad 0 kalles isolert.
21.8 Isomorfi
La G og H være to grafer. En isomorfi fra G til H er en bijektiv funksjon f fra nodene i G til nodene i H som er slik at nodene u og v er naboer i G hvis og bare hvis nodene f(u) og f(v) er naboer i H.
