Grafo complet

Grafo complet

En teoria de grafos, un grafo complet és un grafo simple a on cada parell de vèrtiços està conectat per una aresta. Un grafo complet de n vèrtiços té ___*$n(n-1)/2$ aristas, y se denota $K_n$. Es un grafo regular con todos sus vértices de grado $n-1$. La única forma d'hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos. el teorema de Kuratowski dice que un grafo plano no puede contener $K_5$ (o el grafo bipartito completo $K_{3,3}$) y todo $K_n$ incluye a $K_{n-1}$, entonces ningún grafo completo $K_n$ con $n\ge 5$ és pla.

Eixemples

Els grafos complets d'1 a 12 nodos són els següents:

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

Vore també

• Grafo
• Teoria de grafos

Referències

• KJPIH0UH9YBHBBYUIPIOIJUHU