Teorema de Erdős-Gallay

El teorema de Erdős-Gallay ( criterio de Erdős-Gallay ) es una declaración en la teoría de grafos que especifica una condición bajo la cual una secuencia finita de números naturales se puede asociar con los grados de vértices de algún gráfico . Tales secuencias de números se llaman gráficas. El teorema fue probado por los matemáticos húngaros Pal Erdős y Tibor Gallai ( Hung. Gallai Tibor ) [1] en 1960 .

Redacción

Para formular la afirmación, se introducen las siguientes definiciones:

una sucesión correcta es una sucesión de números naturales de longitud que satisface las siguientes condiciones: $norte$
1. $n-1\geq d_{{1}}\geq d_{{2}}\geq \ldots \geq d_{{n}}$ ,
2. $\sum_{{i=1}}^{{n}}d_{{i}}$ - número par;
una secuencia gráfica de números es una secuencia de enteros no negativos tales que existe un gráfico cuya secuencia de grados de vértice coincide con él. $(d_{{1}},d_{{2}},\ldots,d_{{n}})$

El teorema establece que una secuencia regular es gráfica si y solo si para cada , , la desigualdad es verdadera: $(d_{{1}},d_{{2}},\ldots,d_{{n}})$ $k$ $1\leq k\leq n-1$

\sum_{{i=1}}^{{k}}{{d_{i}}\leq k(k-1)}+\sum_{{i=k+1}}^{n} }{\min\{k,{d_{i}}}\}

Algoritmización

Puede construir un gráfico a partir de una secuencia gráfica utilizando un algoritmo polinomial , que se construye sobre la base del criterio de Havel-Hakimi [2] .

Notas

↑ Erdős, P. & Gallai, T. (1960), Gráfok előírt fokzámú pontokkal , Matematikai Lapok Vol. 11: 264–274 , < http://www.renyi.hu/~p_erdos/1961-05.pdf > Archivado copia fechada el 20 de enero de 2022 en Wayback Machine
↑ Hakimi, S.L. (1962), Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un gráfico lineal. I, Revista de la Sociedad de Matemáticas Industriales y Aplicadas , volumen 10: 496–506

Literatura

Conferencias sobre teoría de grafos / V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. — M.: Nauka, 1990.