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

Комплетан граф
K7, комплетан граф са 7 чворова
Чворови	n
Гране	n(n − 1) / 2

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

${n \choose 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 - Комплетан граф