Комплетан граф

Шаблон:Кутијица за графове У грани математике, теорији графова, комплетан граф или потпун граф је прост граф код кога између свака два чвора постоји грана. Комплетан граф са n чворова у ознаци -{K_n}- има

$(\genfrac{}{}{0ex}{}{n}{2})=\frac{n(n-1)}{2}$

гране. Комплетан граф је регуларан граф, и сваки његов чвор има степен -{n-1}- Комплемент комплетног графа је празан граф (граф без грана). У матричној репрезентацији, комплетном графу одговара матрица чији сви елементи су јединице.

Комплетан граф је такође клика. У ствари, проблем клике се дефинише као проблем проналажења највећег комплетног подграфа неког графа.

Следе цртежи комплетних графова са од 1 до 8 чворова, са назначеним бројем грана.

$K_1:0$	$K_2:1$	$K_3:3$	$K_4:6$
$K_5:10$	$K_6:15$	$K_7:21$	$K_8:28$

Литература

• -{MathWorld}- - Комплетан граф