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
[editar datos en Wikidata ]

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]