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

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