Teoría de secuencias de grados de Havel y Hakimi

Question

Actualmente estoy empezando un curso sobre Teoría de Grafos, y me han explicado la secuencia de grados de Havel & Hakimi. Sin embargo, todavía no estoy muy seguro de ello. En primer lugar, quiero saber si lo he entendido bien, así que voy a intentar explicar lo que creo que demuestra la teoría.

En primer lugar, he robado descaradamente la siguiente afirmación de la presentación:

Bien, lo que quiero preguntar es lo siguiente.

1. ¿Qué significa exactamente "es gráfico"? ¿Significa que es un gráfico? Sé que es una pregunta estúpida, pero no se me ocurre ninguna secuencia de grados que no sea un gráfico...

2. ¿Para qué sirve esto en la práctica? Qué problemas podrías resolver con esto.

Answer 1

1. Creo que el término suele ser "gráfico". Sólo significa que $s^{*}$ es una secuencia de grados de los vértices de algún grafo $G$ . Así que si se puede crear un gráfico con grados de $s^{*}$ entonces puede crear un gráfico con grados de $s$ y viceversa. Tenga en cuenta que no significa que usted crea el mismo gráfico de $s$ y $s^{*}$ . Sólo necesitamos poder crear gráficos a partir de los conjuntos de grados (por ejemplo, si $s$ es gráfico, entonces podemos crear un gráfico $G$ de $s$ y un gráfico $G'$ de $s^{*}$ ).

2. Puede utilizarse para averiguar si dos grafos son isomorfos. Si las secuencias de grados de dos grafos son diferentes, entonces no pueden ser isomorfo .

Answer 2

Hay un buen tratamiento del teorema de Havel-Hakimi en las páginas 44-46 del libro de Doug West, Introducción a la teoría de grafos (segunda edición). En cuanto a los usos de este tipo de resultado, uno podría utilizar la teoría de grafos para modelar alguna molécula física que uno quisiera construir. Un primer paso podría ser ver si existe un grafo con valencias (grados) especificadas. A menudo uno quiere un grafo con las valencias especificadas y propiedades adicionales como que el grafo con estas valencias es un árbol o puede ser incrustado en el plano donde las aristas se encuentran sólo en los vértices. Se han encontrado muchos resultados especializados adicionales sobre la "realización" de grafos con propiedades específicas y valencias especificadas.

Answer 3

1. Graphic Sequence sólo sirve para gráficos sencillos. Significa que si una secuencia de grados es también una secuencia gráfica, el gráfico es simple.

2. Si se demuestra que un grafo enorme es un grafo simple (utilizando Havel & Hakimi) se pueden utilizar las propiedades de los grafos simples para seleccionar los mejores algoritmos para resolver problemas posteriores en dicho grafo.