En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.
Grafo completo | ||
---|---|---|
K7, grafo completo de 7 vértices. | ||
Vértices | n | |
Aristas | n (n-1)/2 | |
Diámetro | 1 | |
Cintura | 3, si n ≥ 3 | |
Automorfismos | n! (Sn) | |
Número cromático | n | |
Índice cromático |
n, si n es impar n-1, si n es par | |
Propiedades |
(n-1)-regular Simétrico Vértice transitivo Arista transitivo Distancia unidad Fuertemente regular Integral | |
Un grafo completo de n vértices tiene aristas, y se denota . Es un grafo regular con todos sus vértices de grado . La única forma de 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 (o el grafo bipartito completo ) y todo incluye a , entonces ningún grafo completo con es plano.
Los grafos completos de 1 a 12 nodos son los siguientes:
K1: 0 | K2: 1 | K3: 3 | K4: 6 |
---|---|---|---|
K5: 10 | K6: 15 | K7: 21 | K8: 28 |
K9: 36 | K10: 45 | K11: 55 | K12: 66 |
KJPIH0UH9YBHBBYUIPIOIJUHU