Grafo completo

Summary

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.

Ejemplos

editar

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
       

Véase también

editar

Referencias

editar


  •   Datos: Q45715
  •   Multimedia: Complete graphs / Q45715

KJPIH0UH9YBHBBYUIPIOIJUHU