Alle fag › Diskret matematikk › Grafer

Grafer

En graf består av noder (hjørner) og kanter mellom dem. Den brukes til å modellere nettverk, veier, rørsystemer og avhengigheter. Graden til en node er antall kanter som går ut fra den.

\sum_v \deg(v) = 2|E|

håndhilselemmaet

|E|_{maks} = \binom{n}{2}

flest mulige kanter i en enkel graf

Symboler

$\deg(v)$	grad til node v
$\|E\|$	antall kanter
$n$	antall noder

Eksempel

5 noder med gradene 2, 3, 3, 2 og 2:

summen er 12, så grafen har $12/2 = 6$ kanter.

Summen av gradene er alltid et partall, fordi hver kant teller to ganger.

Øv på grafer og modulregning gratis →

← Kombinasjoner · Modulregning →

Del av Diskret matematikk: Grafer og modulregning.