Teorema Erdős-Gallay

Teorema Erdős-Gallay ( criteriul Erdős-Gallay ) este o afirmație din teoria grafurilor care specifică o condiție în care o secvență finită de numere naturale poate fi asociată cu gradele de vârf ale unui graf . Astfel de secvențe de numere sunt numite grafice. Teorema a fost demonstrată de matematicienii maghiari Pal Erdős și Tibor Gallai ( Hung. Gallai Tibor ) [1] în 1960 .

Formulare

Pentru formularea afirmației se introduc următoarele definiții:

o secvență corectă este o secvență de numere naturale de lungime care îndeplinesc următoarele condiții: $n$
1. $n-1\geq d_{{1}}\geq d_{{2}}\geq \ldots \geq d_{{n}}$ ,
2. $\sum _{{i=1}}^{{n}}d_{{i}}$ - număr par;
o secvență grafică de numere este o secvență de numere întregi nenegative astfel încât să existe un grafic a cărui secvență de grade de vârf coincide cu acesta. $(d_{{1}},d_{{2}},\ldots ,d_{{n}})$

Teorema afirmă că o secvență obișnuită este grafică dacă și numai dacă pentru fiecare , , inegalitatea este adevărată: $(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}}}\}

Algoritmizare

Puteți construi un grafic dintr-o secvență grafică folosind un algoritm polinomial , care este construit pe baza criteriului Havel-Hakimi [2] .

Note

↑ 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 > Arhivat copie datată 20 ianuarie 2022 la Wayback Machine
↑ Hakimi, S.L. (1962), Despre realizabilitatea unui set de numere întregi ca grade ale vârfurilor unui graf liniar. I, Journal of the Society for Industrial and Applied Mathematics vol. 10: 496–506

Literatură

Prelegeri despre teoria grafurilor / V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. — M.: Nauka, 1990.