21 Grafteori Flashcards
graf
En graf (eng: graph) G består av en endeling, ikke-tom mengde V av noder (eng: vertex/vertices) og en mengde E av kanter (eng: edges). 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 (eng: incident) u og v. To noder kalles naboer (eng: adjacent) hvis de forbindes av en kant.
løkker og parallelle kanter
En kant som går fra en node til seg selv i en multigraf kalles en løkke (eng: loop).
To eller flere kanter som forbinder de samme nodene kalles parallelle kanter (eng: multiple/parallell edges).
En multigraf kalles enkel (eng: simple) hvis den hverken har løkker eller parallelle kanter.
rettet graf
En rettet graf (eng: directed graph) er definert som en graf, men hvor kantene er ordenede par ⟨u, v⟩ i stedet for mengder {u, v}.
tom graf
En graf uten kanter kalles en tom graf (eng: empty graph) eller en nullgraf (eng: null graph).
komplett graf
En enkel graf er komplett (eng: complete) hvis hver node er nabo med enhver annen node. Den komplette grafen med n noder kalles Kn.
komplement
Hvis G er en graf, er komplementet (eng: complement) 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 \hat{G} for komplementet til G.
graden til en node
Graden (eng: degree) 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 (eng: isolated).
ismorfi
La G og H være to grafer. En isomorfi (eng: isomorphism) 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.
