Erdős-Gallay tétel

Az Erdős-Gallay-tétel ( Erdős-Gallay-kritérium ) egy gráfelméleti állítás, amely megadja azt a feltételt, amely mellett természetes számok véges sorozata társítható valamely gráf csúcsainak fokaihoz . Az ilyen számsorozatokat grafikusnak nevezzük. A tételt Erdős Pál és Gallai Tibor ( Hung. Gallai Tibor ) [1] magyar matematikusok bizonyították 1960 - ban .

Megfogalmazás

Az állítás megfogalmazásához a következő definíciókat vezetjük be:

a helyes sorozat a természetes számok hosszúságú sorozata, amely megfelel a következő feltételeknek: $n$
1. $n-1\geq d_{{1}}\geq d_{{2}}\geq \ldots \geq d_{{n}}$ ,
2. $\sum _{{i=1}}^{{n}}d_{{i}}$ - páros szám;
a grafikus számsorozat nemnegatív egész számok sorozata úgy, hogy létezik olyan gráf, amelynek csúcsfokozata egybeesik vele. $(d_{{1}},d_{{2}},\ldots ,d_{{n}})$

A tétel kimondja, hogy egy szabályos sorozat akkor és csak akkor grafikus, ha minden , , egyenlőtlenség igaz: $(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}}}\}

Algoritmizálás

Grafikus sorozatból egy polinomiális algoritmus segítségével készíthet gráfot, amely a Havel-Hakimi kritérium alapján [2] épül fel .

Jegyzetek

↑ Erő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 > Archivált 2022. január 20-án kelt példány a Wayback Machine -nél
↑ Hakimi, S.L. (1962), Egész számok halmazának realizálhatóságáról lineáris gráf csúcsainak fokaiként. I, Journal of the Society for Industrial and Applied Mathematics, 10. kötet: 496–506

Irodalom

Előadások a gráfelméletről / V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. — M.: Nauka, 1990.