Erdős-Gallay-sætning

Erdős-Gallay-sætningen ( Erdős-Gallay-kriteriet ) er et udsagn i grafteori, der specificerer en betingelse, hvorunder en endelig række af naturlige tal kan associeres med en grafs toppunkter . Sådanne talfølger kaldes grafiske. Sætningen blev bevist af de ungarske matematikere Pal Erdős og Tibor Gallai ( Hung. Gallai Tibor ) [1] i 1960 .

Ordlyd

For at formulere påstanden introduceres følgende definitioner:

en korrekt sekvens er en sekvens af naturlige tal af længde, der opfylder følgende betingelser: $n$
1. $n-1\geq d_{{1}}\geq d_{{2}}\geq \ldots \geq d_{{n}}$ ,
2. $\sum _{{i=1}}^{{n}}d_{{i}}$ - lige tal;
en grafisk sekvens af tal er en sekvens af ikke-negative heltal, således at der eksisterer en graf, hvis toppunkts gradsekvens falder sammen med den. $(d_{{1}},d_{{2}},\ldots ,d_{{n}})$

Sætningen siger, at en regulær sekvens er grafisk, hvis og kun hvis for hver , , uligheden er sand: $(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}}}\}

Algoritmisering

Du kan bygge en graf ud fra en grafisk sekvens ved hjælp af en polynomial algoritme , som er bygget på basis af Havel-Hakimi kriteriet [2] .

Noter

↑ Erdős, P. & Gallai, T. (1960), Gráfok előírt fokzámú pontokkal , Matematikai Lapok bind 11: 264–274 , < http://www.renyi.hu/~p_erdos/1961-05.pdf > Archived kopi dateret 20. januar 2022 på Wayback Machine
↑ Hakimi, S.L. (1962), Om realiserbarheden af et sæt heltal som grader af hjørnerne af en lineær graf. I, Journal of the Society for Industrial and Applied Mathematics bind 10: 496–506

Litteratur

Forelæsninger om grafteori / V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. — M.: Nauka, 1990.