[kickout]

Buenas tardes,

A ver si alguien puede echarme una mano:

¿Es posible determinar si existe un grafo (conexo o no conexo), dada la información de cuantos vértices tiene, y de qué grado es cada uno?

(Por ejemplo, determinar si existe el grafo con 5 vértices, con los siguientes grados {2,3,1,6,2})


Además del teorema que afirma que existe un número par de vértices con grado impar, ¿hay algún otro teorema aplicable para determinar la existencia o no de un grafo con esa información?

Muchas gracias.
Un saludo.

[Abdulai]

..........
¿Es posible determinar si existe un grafo (conexo o no conexo), dada la información de cuantos vértices tiene, y de qué grado es cada uno?

(Por ejemplo, determinar si existe el grafo con 5 vértices, con los siguientes grados {2,3,1,6,2})
.......

- Por un lado, la suma de los grados debe ser igual al doble de las aristas.  En el caso del ejemplo no se cumple.

- Por otro, aunque la cumpliera no es único (ejemplo con 6 vértices)



(el primero no es plano y el segundo si)

[kickout]

- Por un lado, la suma de los grados debe ser igual al doble de las aristas.  En el caso del ejemplo no se cumple.

- Por otro, aunque la cumpliera no es único (ejemplo con 6 vértices)

Gracias por la respuesta.

¿Por qué en el ejemplo la suma de los grados no podría ser igual al doble de las aristas? (No lo acabo de ver, lo único que veo imposible, de ser un grafo, sería ese vértice de grado 6, ya que solo puede estar unido a otros 4 vértices).

Ahora bien, si tenemos en cuenta que pueda ser un grafo (conexos o no conexos), o también un multigrafo, ¿qué habría que tener en cuenta? (El ejemplo sí podría ser un multigrafo si no me equivoco).



(El problema hace referencia a los enfrentamientos entre varias personas, por ejemplo, partidos de tenis entre los 6 participantes, determinando si unos determinados datos son posibles. El caso del multigrafo haría referencia a participantes que se enfrentan varias veces entre sí).

Muchas gracias.

[Luis Fuentes]

Hola

 La condición necesaria y suficiente es, dados los grados ordenados de menor a mayor \( (d_1,d_2,\ldots,d_n) \) tiene que cumplirse que su suma es par y que \( \displaystyle\sum_{i=1}^{n-1}{}d_i\leq d_n \).

 Lo tienes demostrado en este artículo (que adjunto):

S. L. Hakimi. On the realizability of a set of integers as degrees of the vertices of a graph,
J. SIAM Appl. Math., 10 (1962), 496–506

 En la prueba además se ve el método inductivo para construir un ejemplo: construyes un grafo de \( n-1 \) vértices con grados \( (d_2,\ldots,d_{n-1},d_n-d_1) \) y le añades un vértice con \( d_1 \) aristas sobre el último.

En tu caso si quieres un grafo \( (1,2,2,3,6) \), viene de uno \( (2,2,3,6-1)=(2,2,3,5) \); a su vez de \( (2,3,5-2)=(2,3,3) \) y este lo construyes directamente.



Saludos.