U grani matematike, teoriji grafova, kompletan graf ili potpun graf je prost[1] graf kod koga između svaka dva čvora postoji grana. Kompletan graf sa n čvorova u oznaci Kn ima

Kompletan graf

K7, kompletan graf sa 7 čvorova
Čvorovin
Granen(n − 1) / 2

grane. Kompletan graf je regularan graf[2], i svaki njegov čvor ima stepen n-1 Komplement kompletnog grafa je prazan graf (graf bez grana). U matričnoj reprezentaciji, kompletnom grafu odgovara matrica čiji svi elementi su jedinice.

Kompletan graf je takođe klika. U stvari, problem klike se definiše kao problem pronalaženja najvećeg kompletnog podgrafa nekog grafa.

Slede crteži kompletnih grafova sa od 1 do 8 čvorova, sa naznačenim brojem grana.


Izvori uredi

  1. ^ Neusmeren graf bez petlji.
  2. ^ Graf čiji su svi čvorovi istog stepena (iz svakog izlazi isti broj grana).

Literatura uredi