Erdősova-Gallayova věta

Erdős-Gallayův teorém ( Erdős-Gallayovo kritérium ) je výrok v teorii grafů , který specifikuje podmínku, za níž může být konečná posloupnost přirozených čísel spojena se stupni vrcholů nějakého grafu . Takové posloupnosti čísel se nazývají grafické. Větu dokázali maďarští matematici Pal Erdős a Tibor Gallai ( maď . Gallai Tibor ) [1] v roce 1960 .

Formulace

Pro formulaci tvrzení jsou zavedeny následující definice:

správná posloupnost je posloupnost přirozených čísel délky splňující tyto podmínky: $n$
1. $n-1\geq d_{{1}}\geq d_{{2}}\geq \ldots \geq d_{{n}}$ ,
2. $\sum _{{i=1}}^{{n}}d_{{i}}$ - sudé číslo;
grafická posloupnost čísel je posloupnost nezáporných celých čísel, takže existuje graf, jehož posloupnost vrcholových stupňů se s ním shoduje. $(d_{{1}},d_{{2}},\ldots ,d_{{n}})$

Věta říká, že pravidelná posloupnost je grafická tehdy a jen tehdy, když pro každé , , je nerovnost pravdivá: $(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}}}\}

Algoritmizace

Graf můžete sestavit z grafické sekvence pomocí polynomiálního algoritmu , který je postaven na základě Havel-Hakimiho kritéria [2] .

Poznámky

↑ 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 > Archi kopie ze dne 20. ledna 2022 na Wayback Machine
↑ Hakimi, S. L. (1962), O realizovatelnosti množiny celých čísel jako stupňů vrcholů lineárního grafu. I, Journal of the Society for Industrial and Applied Mathematics vol. 10: 496–506

Literatura

Přednášky o teorii grafů / V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. — M.: Nauka, 1990.