Dado
un cierto numero de vértices y sus grados, ¿Cómo decidir si existe un grafo con
ese número de vértices y con esos grados?
Definición:
Decimos que una secuencia de enteros no negativa es gráfica si
es la secuencia de grados de algún grafo
La
secuencia 4,4,3,2,2,1 es gráfica.
Anteriormente
vimos que 3,3,3,3,3 no es gráfica.
¿Cómo
determinar que una sucesión es gráfica?
Para
que sea gráfica dos condiciones necesarias son:
- grad(vi)
≤ p-1
-
∑ grad(vi)
sea par
Sin
embargo estas condiciones no son suficientes.
(Es
decir si no se cumplen la secuencia no es gráfica pero si se cumplen
puede que lo sea puede que no)
Ejemplo:
Cinco invitados van a una fiesta. ¿Es
posible que cada una de ellas
conozca
a un numero diferente de invitados?
Si
esto fuese posible se tendría que
s: 0,1,2,3,4
Lo
cual es absurdo ya que un invitado no conoce a nadie (grado 0) pero habría
otro de los invitados (grado 4) que si la conocería. Con lo cual esta secuencia
no puede ser gráfica. Sin embargo cumple las dos
condiciones necesarias.
Comentarios
Publicar un comentario