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 per mig 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