Grafo completo
De Wikipedia, la enciclopedia encyclopedia
En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.
Datos rápidos Vértices, Aristas ...
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 | |
Cerrar
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: