Komplet graf

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

En Komplet Graf er et begreb inden for grafteorien og betegner en simpel graf, hvor alle par af knuder er forbundet med én kant. Disse grafer spiller en vigtig rolle inden for grafteorien.

En komplet graf Kn er en uorienteret graf med n knuder og {n \choose 2}=\frac{n(n-1)}{2} kanter.

Eksempler[redigér | redigér wikikode]

Tabellen herunder viser afbildninger af komplette grafer Kn for n mellem 1 og 8, samt antallet af kanter i hver.

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg