Kompletan graf
Kompletan graf | |
K7, kompletan graf sa 7 čvorova | |
Čvorovi | n |
Grane | n(n − 1) / 2 |
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
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.