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

Из Википедије, слободне енциклопедије
Комплетан граф
Complete graph K7.svg
K7, комплетан граф са 7 чворова
Чворови n
Гране n(n − 1) / 2

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

{n \choose 2} = \frac{n (n-1)}{2}

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

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

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

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg


Извори[уреди]

  1. ^ Неусмерен граф без петљи.
  2. ^ Граф чији су сви чворови истог степена (из сваког излази исти број грана).

Литература[уреди]