Grafo completo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Grafo completo
Complete graph K7.svg
K7, grafo completo de 7 vértices.
Vértices n
Aristas n (n-1)/2
Diámetro 1
Cintura (girth) 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

En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n-1)/2 aristas, y se nota K_n. Es un grafo regular con todos sus vértices de grado n-1. 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 planar no puede contener K_5 (ó 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 es planar

Ejemplos[editar]

Los grafos completos de 1 a 12 nodos son los siguientes:

K1: 0 K2: 1 K3: 3 K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

Véase también[editar]

Referencias[editar]