\documentclass[11pt,twoside]{article} 
\usepackage{AML-acta-info-julius30}
\PassOptionsToPackage{hyphenation=composite}{magyar.ldf}
\RequirePackage[magyar]{babel}
\RequirePackage[T1]{fontenc}

\usepackage[latin2]{inputenc}
\frenchspacing

\usepackage{epic}
\usepackage{eepic}



\newcommand{\idez}[1]{{\ideze}#1''}
\newcommand{\ideze}{\setbox0=\hbox{\lower1.38ex\hbox{''}}\dp0=0pt\box0}

\def\textbinom#1#2{\left(\strut\textstyle{#1 \atop #2}\right)}

\hyphenation{al-go-rit-mus
cik-ké-nek
}

\begin{document}
\begin{center}
\large
LINEÁRIS ERDŐS-GALLAI TESZT 

\vspace{8mm}
\normalsize
IVÁNYI ANTAL, LUCZ LORÁND, MÓRI F. TAMÁS
\end{center}


\short{%
IVÁNYI ANTAL, LUCZ LORÁND, SÓTÉR PÉTER
}{%
\textit{\textit{Alkalmazott Matematikai Lapok}}}

\begin{abstract}
  Havel 1955-ben \cite{Havel1955}, Erdős és Gallai 1960-ban \cite{ErdosG1960}, 
Hakimi 1962-ben \cite{Hakimi1962}, Ruskey, Cohen, Eades és Scott 1994-ben \cite{RuskeyCES1994}, Barnes and Savage 1997-ben 
\cite{BarnesS1997}, Tripathi, Venugopalan és West 2010-ben \cite{TripathiVW2010} javasoltak módszert annak eldöntésére, hogy 
nemnegatív egészek sorozata lehet-e egy egyszerű gráf foksorozata. Ezeknek az algoritmusoknak a futási ideje legrosszabb esetben négyzetes. Cikkünkben bemutatjuk az \textsc{Erdős-Gallai-Lineárisan} algoritmust, amelynek 
legrosszabb futási ideje lineáris. Mivel például jó sorozat esetén a sorozat minden elemét tesztelni kell, RAM számítási modell 
esetén EGL aszimptotikusan optimális. Az új algoritmus segítségével 24, 25, 26, 27,28 és 29 csúcs esetén meghatároztuk egyszerű 
gráfok különböző foksorozatainak a számát \cite{Sloane2011A001700}.  
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bevezetés\label{sec-Intro}}
A gyakorlatban különböző területeken szükség van objektumok rangsorolására. Ennek egyik elterjedt módszere, hogy az 
objektumokat páronként összehasonlítjuk, és az összehasonlítás eredményeképpen pontokat adunk az objektumoknak, végül pedig az objektumokat a kapott pontszámok alapján rangsoroljuk. 

Például Landau biológiai \cite{Landau1953}, Hakimi kémiai 
\cite{Hakimi1962}, Kim, Toroczkai, Miklós, Erdős és Székely \cite{KimTMESz2009} és Newman és Barabási \cite{NewmanB2006} hálózati,   
Bozóki, Fülöp, Poesz és Rónyai gazdasági \cite{AnholzerBBK2011,BozokiFP2011,BozokiFR2010,Keri2011,Temesi2011} Liljeros et al. emberi kapcsolatokra vonatkozó 
\cite{LiljerosEASA2001}, Iványi et al. pedig sportbeli 
\cite{Ivanyi2009,Ivanyi2010,IvanyiLS2011,IvanyiP2011,KayibiKPI2011,PirzadaIK2011,PirzadaZI2010} alkalmazásokra hivatkoztak. 

A számos lehetséges terminológia közül Erdős Pál és Gallai Tibor \cite{ErdosG1960} cikkének szóhasználatát és jelöléseit követjük.

A pontozás módjától függően sokféle feladat és eredmény van. Ebben a cikkben gráfon 
olyan véges, irányítás nélküli gráfot értünk, amelyben nem fordulnak elő hurokélek és bármely két csúcsot 
legfeljebb egy él köt össze, azaz \textit{egyszerű gráfokról} lesz szó. 
Ez a gráf annak a pontozásnak felel meg, amikor az összehasonlításoknak két 
lehetséges eredménye van: vagy mindkét objektum egy, vagy pedig mindkettő nulla pontot kap. Az összehasonlítások 
eredményét ábrázoló gráfban két csúcs pontosan akkor van összekötve, amikor a nekik megfelelő objektumok 
összehasonlítása során mindkét objektum egy pontot kapott. 

A sok népszerű feladat közül azt vizsgáljuk, hogyan dönthető el gyorsan, hogy nemnegatív egészek 
$n \geq 1$ hosszúságú $b = (b_1,\ldots,b_n)$ sorozatához létezik-e olyan egyszerű gráf, amelynek 
$b$ a foksorozata. 

A hasonló feladatokkal kapcsolatban megjegyezzük, hogy mind az irányítatlan, mind pedig az irányított gráfokkal 
kapcsolatban az utóbbi néhány évben is számos cikk és könyvfejezet jelent meg (például \cite{BeregI2008,BrualdiK2009,
delGenioKTB2010,HellK2009,KayibiKPI2011,Meierling2009,RodsethST2009,TripathiT2008,TripathiVW2010,Weisstein2011DS,Weisstein2011GS}, 
illetve \cite{BeasleyBR2009,BozokiFR2010,BuschCJ2010,ErdosMT2010,Frank2011,Ivanyi2009,Ivanyi2010,Ivanyi2011Kyoto,IvanyiP2011,
IvanyiP2011Opkut,KimTMESz2009,Knuth2011,LaMar2010,MiklosES2011,Pirzada2011,PirzadaIK2011,PirzadaNSI2010}).

Legyenek $l, \ m$ és $u$ egész számok, továbbá $1 \leq m$ és $0 \leq l \leq u.$  Egész számok 
$b = (b_1,\ldots,b_m)$ sorozatát \textit{$(l,u,m)$-korlátosnak} (röviden: korlátosnak) nevezzük, ha 
$l \leq b_i \leq u$ minden $1 \leq i \leq m$ indexre.  
A $b = (b_1,\ldots,b_m)$ $(l,u,m)$-korlátos sorozatot \textit{$(l,u,m)$-szabályosnak} (röviden: szabályosnak) mondjuk, ha   
$u \geq b_1 \geq \cdots \geq b_m \geq l.$ Egy $(l,u,m)$-szabályos sorozatot \textit{megvalósíthatónak} 
vagy \textit{grafikusnak} (röviden: jónak) nevezünk, ha létezik olyan $G$ egyszerű gráf, hogy $G$ foksorozata 
$(b_1,b_2,\ldots,b_m).$ Vizsgálatainkban kitüntetett szerepet játszanak a $(0,m-1,m)$-szabályos sorozatok, ahol $m$ egy egyszerű 
gráf csúcsainak száma, $0$ és $m - 1$ pedig a foksorozat alsó, illetve felső korlátja. 

Jelentős számú cikk (például \cite{Burns2007,ErdosR1997,Kohnert2004,MetropolisN1980}) foglalkozik páros számok 
\textit{grafikus felbontásaival:} előállítják a $2k$ páros szám pozitív egész öszeadandókra való monoton csökkenő 
felbontásait, és az így kapott 
$q = (q_1,\ldots,q_m)$ sorozatok közül -- amelyekre $q_1 + \cdots + q_m = 2k$ és $q_m \geq q_{m-1} \geq \cdots \geq q_1$ -- 
szűrik ki a grafikus sorozatokat, vagy pedig rekurzióval eleve csak a grafikus sorozatokat állítják elő. 

A továbbiakban főleg szabályos sorozatokkal foglalkozunk. A definíciókban az alsó és felső korlátok azért szerepelnek, hogy 
ellenőrző algoritmusainkat megkíméljük a nyilvánvalóan nem jó sorozatok ellenőrzésétől, 
ezért ezek a megszorítások nem jelentik az általánosság megszorítását. 

Cikkünk fő célkitűzése, hogy minél kisebb várható futási idejű algoritmust találjunk annak eldöntésére, hogy előírt $b$ 
szabályos sorozathoz található-e olyan $G$ egyszerű gráf, melynek foksorozata $b.$ A probléma önmagában 
is érdekes és fontos, hiszen a gráfelmélet több mint ötven éve intenzíven foglalkozik vele. Számunkra külön motivációt jelent, 
hogy a feladat részfeladatként jelentkezik, amikor minél kisebb várható futási idejű 
algoritmust keresünk annak eldöntésére, hogy előírt sorozat lehet-e egy labdarúgó bajnokság pontsorozata 
\cite{Frank2011,Ivanyi2001,Ivanyi2011Egres,IvanyiMN2011,IvanyiP2011Opkut,KovacsP2002,LuczIS2012}. A labdarúgás is 
olyan sport, amelyben a döntetlen megengedett eredmény. Vizsgálatainkban mind a tesztelés, mind pedig a megvalósítás során  
kulcsszerepet játszik a döntetlenek párosítása -- ez pedig pontosan az egyszerű gráfok fokainak párosításával 
ekvivalens feladat.  

Az egyszerű irányítatlan gráfok foksorozataival kapcsolatos eredmények és módszerek hasznosak az irányított gráfokra, multigráfokra 
\cite{Hakimi1963,Ivanyi2009,Ivanyi2010,KemnitzD1997,LaMar2010}, többrészes gráfokra \cite{PirzadaAK2011,SoterIL2012} és
a foksorozatokhoz hasonló sorozatokra \cite{PirzadaAK2011,PirzadaNSI2010,PirzadaZI2010} vonatkozó hasonló feladatok megoldásánál.  

Érdemes megemlíteni, hogy a fokszámsorozatok számának meghatározásával kapcsolatos nehézségek miatt annak is van irodalma 
(lásd például \cite{delGenioKTB2010,KayibiKPI2011,MiklosES2011}), hogy véletlen mintavétellel becsüljük ezeket a számokat.

Melléktermékként javítottuk és bővítettük az EIS \cite{Sloane2011} adatbázist: egyrészt a benne lévő ismert sorozatok 
új elemeivel, másrészt a cikkben definiált új sorozatok elemeinek megadásával. Módszerünk az összes 
jó sorozat gazdaságos előállítására is alkalmas (vesd össze Ruskey \cite{RuskeyCES1994} 1994-es, valamint Barnes and Savage 
\cite{BarnesS1997} 1997-es cikkével).

A cikk felépítése a következő. A bevezető első rész után a témakör klasszikus algoritmusait foglaljuk össze. 
A harmadik részben új pontos algoritmusokat, a negyedik részben leszámlálási eredményeket, 
az ötödik részben pedig új tesztelő algoritmusokat ismertetünk. A hatodik részben a közelítő algoritmusok hibáját,  
míg a hetedikben a pontos algoritmusok futási idejét elemezzük. Végül a nyolcadik részben a grafikus sorozatok 
számának nagyságrendjét jellemezzük. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Klasszikus pontos algoritmusok\label{sec-pontos}}

\subsection{Havel-Hakimi algoritmus \label{subsec-HH}}
A feladat megoldására az első módszert Vaclav Havel cseh matematikus javasolta 1955-ben \cite{Havel1955,Lovasz2007}, majd 1962-ben Louis Hakimi \cite{Hakimi1962} tőle függetlenül publikálta ugyanezt az eredményt, innen adódik a Havel-Hakimi elnevezés.

\begin{theorem} \emph{(Havel \cite{Havel1955})} Ha $n \geq 1$, a $(b_1,\ldots,b_n)$ $n$-szabályos  
sorozat akkor és csak akkor $n$-jó, ha a $(b_2 - 1, b_3 - 1, \ldots,  b_{b_1} - 1, b_{b_1 + 1} - 1, 
b_{b_1 + 2}, \ldots, b_n)$ sorozat $(n - 1,n - 1)$-jó.
\end{theorem}

\begin{proof}: Lásd \cite{Havel1955}.
\end{proof}

Az eredeti tétel $n \geq 3$ korlátozó feltételt tartalmaz, de könnyű ezt az $n \geq 1$ feltételre módosítani.

Ha ezen tétel alapján írunk egy rekurzív algoritmust, akkor annak futási ideje a RAM számítási modell 
\cite{CormenLRS2009} szerint legjobb esetben -- például az $(n-1,0,\ldots,0)=(n - 1,0^{n-1})$ bemenetre -- $\Theta(1)$, 
legrosszabb esetben pedig -- például a \textit{homogén} $(n - 1)^n$ vagy a \textit{tranzitív} $(n - 1, n - 2, \ldots, 1, 0)$ 
bemenetre -- $\Theta(n^2)$. Érdemes megjegyezni, hogy a tétel bizonyítása konstruktív, 
és a bizonyításon alapuló algoritmus négyzetes idő alatt nem csak ellenőriz, hanem egy megfelelő gráfot is előállít 
(feltéve persze, hogy létezik megfelelő egyszerű gráf). 

Mivel a teljes gráfnak $\textbinom{n}{2} = \Theta(n^2)$ éle van, bármely -- a megvalósítást is biztosító -- RAM algoritmus 
legrosszabb futási ideje nem lehet kisebb, mint négyzetes.

1962-ben Louis Hakimi \cite{Hakimi1962} Haveltől függetlenül publikálta ugyanezt az eredményt, ezért ma a tételt rendszerint 
\textit{Havel-Hakimi tételnek}, a módszert pedig \textit{Havel-Hakimi algoritmusnak} nevezik.

Az algoritmust később irányított gráfokra \cite{ErdosMT2010,Ivanyi2009,Ivanyi2010,KleitmanW1973} is kiterjesztették.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erdős-Gallai algoritmus\label{subsec-EG}}
Időrendben a következő eredmény Erdős Pál és Gallai Tibor alábbi szükséges és elégséges feltétele \cite{ErdosG1960} volt. 

Nemnegatív egészek adott $b = (b_1,\ldots,b_n)$ sorozata esetén a sorozat első $i$ elemét a sorozat $i$ elemhez tartozó 
\textit{fejének,} míg a többi elemét a $i$ elemhez tartozó \textit{farkának} nevezzük. A fejelemek összegét $H_i,$ 
míg a farokelemek összegét $T_i$ jelöli $(i = 1, \ldots,n)$. A $\sum_{k=i+1}^n \min(i,b_k)$ összeget pedig $C_i$-vel jelöljük 
és a farok \textit{kapacitásának} nevezzük.  Ha egy $b$ sorozatra $H_n$ páros, akkor a sorozatot \textit{párosnak,} 
egyébként \textit{páratlannak} nevezzük.

\begin{theorem} \emph{(Erdős, Gallai, \cite{ErdosG1960})} Ha  $n \geq 1,$ az \label{tetel-EG} $n$-szabályos $(b_1\ldots,b_n)$ 
sorozat akkor és csak akkor jó, ha 
\begin{equation}
H_n \quad \mbox{páros}\label{eq-EGparity}
\end{equation}
és
\begin{equation}
H_i - i(i - 1) \leq C_i \quad (i = 1, \ldots, n - 1).\label{eq-EGbinom}
\end{equation}
\end{theorem}

\begin{proof} Lásd \cite{Choudum1986,ErdosG1960,SierksmaH1991,TripathiVW2010}.
\end{proof}

Bár ez a tétel csak ellenőriz, futási ideje a RAM számítási modell szerint a legjobb esetben $\Theta(n)$ és a legrosszabb esetben $\Theta(n^2)$ 
között változik. A közelmúltban Tripathi et al. \cite{TripathiVW2010} publikáltak a tételre konstruktív bizonyítást, amely 
jó bemenet esetén $O(n^3)$ idő alatt egy megoldást is előállít.
Az  \ref{fig-parszabarany}. ábrán láthatjuk az n-szabályos (R(n)) és n-páros (E(n)) sorozatok számát és ezek egymáshoz viszonyított arányát (E(n)/R(n)) n=1,...,38. Ha n tart a végtelenbe, akkor ez a hányados az $1/2$-hez tart (\ref{eq-epsrholim}).

\begin{figure}[!t]
\begin{footnotesize}
\begin{center}
\begin{tabular}{|r|r|r|r|}  \hline \hline
$n$  &    $R(n)$  &$E(n)$& $E(n)/R(n)$       \\ \hline \hline
$1$  &     $1$       &$1$          &       $1.0000000000000$            \\ \hline
$2$  &     $3$       &$2$          &      $0.6666666666667$  \\ \hline
$3$  &     $10$      &     $6$     &      $0.6000000000000$       \\ \hline
$4$  &     $35$      &     $19$    &  $0.5428571428571$\\ \hline
$5$  &     $126$     &     $66$    &    $0.5238095238095$           \\ \hline
$6$  &     $462$     &     $236$   &    $0.5108225108225$           \\ \hline 
$7$  &     $1716$    &     $868$   &    $0.5058275058275$         \\ \hline 
$8$  &     $6435$    &    $3235$   &    $0.5027195027195$     \\ \hline 
$9$  &     $24310$   &   $12190$   &    $0.5014397367339$      \\ \hline 
$10$  &    $92378$   &   $46252$   &    $0.5006819805581$   \\ \hline 
$11$  &   $352716$   &  $176484$   &    $0.5003572279114$    \\ \hline 
$12$  & $1352078$    &  $676270$   &    $0.5001708481315$     \\ \hline 
$13$  & $5200300$    & $2600612$   &    $0.5000888410284$      \\ \hline 
$14$  &$20058300$    &$10030008$   &    $0.5000427753100$      \\ \hline 
$15$  &$77558760$    &$38781096$   &    $0.5000221251603$     \\ \hline 
$16$  &$300540195$   &$150273315$  &    $0.5000107057227$     \\ \hline 
$17$  &$1166803110$  &$583407990$  &    $0.5000055150693$      \\ \hline 
$18$  &$4537567650$  &$2268795980$ &    $0.5000026787479$     \\ \hline 
$19$  &$17672631900$ &$8836340260$ &    $0.5000013755733$      \\ \hline 
$20$  &$68923264410$ &$34461678394$&    $0.5000006701511$       \\ \hline 
$21$  &$269128937220$&$134564560988$&   $0.5000003432481$      \\ \hline 
$22$&$1052049481860$&$526024917288$&    $0.5000001676328$      \\ \hline 
$23$&$4116715363800$&$2058358034616$&   $0.5000000856790$    \\ \hline 
$24$&$16123801841550$  &$8061901596814$   &$0.5000000419280$        \\ \hline 
$25$&$63205303218876$  &$31602652961516$  &$0.5000000213918$  \\ \hline 
$26$&$247959266474052$ &$123979635837176$  &    $0.5000000104862$     \\ \hline 
$27$&$973469712824056$ &$486734861612328$  &    $0.5000000053420$      \\ \hline 
$28$&3824345300380220&1912172660219260 &    $0.5000000026224$     \\ \hline 
$29$&15033633249770520&7516816644943560 &    $0.5000000013342$     \\ \hline 
$30$&59132290782430712 &29566145429994736&    $0.5000000006558$  \\ \hline 
$31$&$232714176627630544$             &$116357088391374032$            &   $0.5000000003333$      \\ \hline 
$32$ &$916312070471295267$&  $458156035385917731$&   $0.5000000001640$      \\ \hline 
$33$ &$3609714217008132870$&$1804857108804606630$&   $0.5000000000833$    \\ \hline 
$34$&$14226520737620288370$&$7113260369393545740$          &   $0.5000000000410$           \\ \hline 
$35$&$56093138908331422716$&$28046569455332514468$ &   $0.5000000000208$     \\ \hline  
$36$  &$221256270138418389602$&$ 110628135071477978626$&   $0.5000000000103$         \\ \hline 
$37$ &$873065282167813104916$&  $436532641088444120108$&   $0.5000000000052$        \\ \hline 
$38$ &$3446310324346630677300$&$1723155162182151654600$&   $0.5000000000026$      \\ \hline \hline
\end{tabular}
\caption{Páros és szabályos sorozatok száma és ezen számok aránya.\label{fig-parszabarany}}\end{center}
\end{footnotesize}
\end{figure}
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Új pontos algoritmusok\label{sec-ujpontos}}
Ebben a részben a nullamentes algoritmusok, az eltoló Havel-Hakimi, a paritásos Havel-Hakimi, a rövidített Erdős-Gallai, ugró Erdős-Gallai, lineáris Erdős-Gallai és a gyors Erdős-Gallai algoritmusokat mutatjuk be.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Nullamentes algoritmusok\label{subsec-nullamentes}}
Mivel a sorozatok végén lévő nullák izolált csúcsokat jelentenek, így azok nem befolyásolják, hogy az adott sorozat 
jó-e. Ezt a megfigyelést hasznosítja a következő állítás, amelyben $p$ a $b$ sorozat pozitív elemeinek a számát jelöli. 

\begin{corollary} Ha\label{lemma-nullamentes} $n \geq 1$, a $(b_1,\ldots,b_n)$ $(n,n)$-szabályos  
sorozat akkor és csak akkor $n$-jó, ha a $(b_1, \ldots, b_p)$ sorozat $(p,p)$-jó.
\end{corollary}

\begin{proof} Ha a sorozatnak van pozitív eleme, akkor az állítás a Havel-Hakimi, illetve az Erdős-Gallai 
következménye, de közvetlenül is adódik: a nullák ugyanis nem segítenek a pozitív fokszámok párosításánál, ugyanakkor nem okoznak 
önálló igényt sem. 
\end{proof}

Az ezen a tulajdonságon alapuló megvalósítást nullamentes Havel-Hakimi (HHN), illetve nullamentes Erdős-Gallai (EGN) 
algoritmusnak nevezzük.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Eltoló Havel-Hakimi algoritmus\label{subsec-RHH}}
Havel és Hakimi eredeti tételének természetes algoritmikus megfelelőjét HHR-nek (Rendező Havel-Hakimi) nevezzük, mert a 
tétel természetes alkalmazása minden menetben igényli a redukált bemenet rendezését.

A tétel alapján olyan megvalósítás is lehetséges, hogy a fokszámok redukálását a sorozat monotonitását megőrizve végezzük. 
Ekkor az Eltoló Havel-Hakimi algoritmust (HHE) kapjuk. A módszer tovább gyorsítható, ha az első nem kielégíthető csúcsnál elutasítjuk a sorozatot és nem végzünk el további felesleges számításokat.\\

\textit{Bemenet}: $n $ a csúcsok száma $(n \geq 1)$; $b = (b_1, b_2, \ldots, b_n)$ $n$-szabályos sorozat

\textit{Kimenet}: $L$ logikai változó\\ ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy $b$ jó) 


\medskip
\noindent \textsc{Eltoló-Havel-Hakimi}$(n, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $FF = b$\` $\rhd$ 01. sor: munkaváltozó inicializálása\\
\hspace{-7mm}02 $first = 0$ \` $\rhd$ 02. sor: ellenőrizendő elem indexének beállítása\\
\hspace{-7mm}03 \textbf{while} $FF_{first} > 0$ \` $\rhd$ 03--33. sor: sorozat ellenőrzése\\
\hspace{-7mm}04 \>    $last = FF_{first} + first$ \` $\rhd$ 04. sor: utoljára megvizsgálandó elem\\
\hspace{-7mm}05 \>    \textbf{if} $FF_{last} == 0$ \` $\rhd$ 05--08. sor: gyors teszt\\
\hspace{-7mm}06 \>	\>   $L =$ \textit{false} \` $\rhd$ 06--07. sor: rossz sorozat elutasítása\\
\hspace{-7mm}07 \>    \>   \textbf{return}\\
\hspace{-7mm}08 \>    \textbf{end}\\
\hspace{-7mm}09 \>    \textbf{if} $FF_{last} == FF_{last + 1}$ \` $\rhd$ 09--30. sor: ellenőrzése 'eltolással' \\
\hspace{-7mm}10 \>    \>    $i = first + 1$ \` $\rhd$ 06. sor: első egyforma elem index\\
\hspace{-7mm}11 \>    \>    \textbf{if} $FF_{last} \not = FF_i$ \` $\rhd$ 11--15. sor: első egyforma elem keresése\\
\hspace{-7mm}12 \>    \>    \>    \textbf{while} $FF_i \not = FF_{last}$\\
\hspace{-7mm}13 \>    \>    \>    \>    $i = i + 1$\\
\hspace{-7mm}14 \>    \>    \>    \textbf{end}\\
\hspace{-7mm}15 \>    \>    \textbf{end}\\    
\hspace{-7mm}16 \>    \>    \textbf{for} $j = first + 1$ \textbf{to} $i$\` $\rhd$ 16--18. sor: eltolás mentes rész csökkentése\\
\hspace{-7mm}17 \>    \>    \>    $FF_j = FF_j - 1$\\
\hspace{-7mm}18 \>    \>    \textbf{end}\\
\hspace{-7mm}19 \>    \>    $i = last - i + 1$\` $\rhd$ 19. sor: leköthető fokszámigény\\
\hspace{-7mm}20 \>    \>    $j = last + 2$ \` $\rhd$ 20. sor: $j$ inicializálása\\
\hspace{-7mm}21 \>    \>    \textbf{while} $FF_{last} = FF_j$ \` $\rhd$ 21--23 sor: utolsó ugyanolyan elem megkeresése\\
\hspace{-7mm}22 \>    \>    \>    $j = j + 1$\\
\hspace{-7mm}23 \>    \>    \textbf{end}\\    
\hspace{-7mm}24 \>    \>    \textbf{for} $ii = 0$ \textbf{to} $i$ \` $\rhd$ 24--27. sor: fokszámok csökkentése hátulról haladva\\
\hspace{-7mm}25 \>    \>    \>    $j = j - 1$\\
\hspace{-7mm}26 \>    \>    \>    $FF_j = FF_j - 1$\\
\hspace{-7mm}27 \>    \>    \textbf{end}\\
\hspace{-7mm}28 \>    \>    $FF_{first} = 0$\` $\rhd$ 28. sor: a kielégített első elem nullázása\\
\hspace{-7mm}29 \>    \>    $first = first + 1$\` $\rhd$ 29. sor: új első elem beállítása\\
\hspace{-7mm}30 \>    \textbf{else}\` $\rhd$ 30--36. sor: ellenőrzés 'eltolás' nélkül\\
\hspace{-7mm}31 \>    \>    \textbf{for} $j = first + 1$ \textbf{to} $last+1$ \` $\rhd$ 31--33. sor: fejelem igényének kielégítése\\
\hspace{-7mm}32 \>    \>    \>    $FF_j = FF_j - 1$\\
\hspace{-7mm}33 \>    \>    \textbf{end}\\
\hspace{-7mm}34 \>    \>    $FF_{first} = 0$ \` $\rhd$ 34. sor: a kielégített első elem nullázása\\
\hspace{-7mm}35 \>    \>    $first = first + 1$ \` $\rhd$ 35. sor: új első elem beállítása\\
\hspace{-7mm}36 \>    \textbf{end}\\
\hspace{-7mm}37 \textbf{end}\\
\hspace{-7mm}38 \textbf{if} $FF_n == 0$ \` $\rhd$ 38. sor: ha az utolsó igényt is sikeresen kielégítettük\\
\hspace{-7mm}39 \>    $L = true$ \` $\rhd$ 39. sor: elfogadó állapot beállítása\\
\hspace{-7mm}40 \textbf{else}\\
\hspace{-7mm}41 \>    $L = false$ \` $\rhd$ 41. sor: elutasító állapot beállítása\\
\hspace{-7mm}42 \textbf{end}\\
\hspace{-7mm}43 \textbf{return} $L$ \` $\rhd$ 43. sor: visszatérés az eredménnyel
\end{tabbing}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Paritásos Havel-Hakimi algoritmus\label{subsec-RHH}}
Érdekes gondolat az Erdős-Gallai és a Havel-Hakimi feltételek együttes alkalmazása úgy, hogy először $b$ paritását vizsgáljuk, 
és csak a páros bemenetekre alkalmazzuk a rendszerint négyzetes futási idejű rekurzív ellenőrzést. 
Ezzel ugyan elveszítjük a nullamentes Havel-Hakimi azon jó tulajdonságát, hogy legjobb esetben konstans idő alatt lefut, 
viszont cserébe megkapjuk azt, hogy a várható futási idő közel 50 százalékkal csökken.\\

\textit{Bemenet}: $n $ a csúcsok száma $(n \geq 1)$; $b = (b_1, b_2, \ldots, b_n)$ $n$-szabályos sorozat

\textit{Kimenet}: $L$ logikai változó\\ ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy $b$ jó)

\textit{Munkaváltozók}:\\
$H = (H_1,\ldots,H_n)$: $H_i$ $b$ első $i$ elemének az összege

\medskip
\noindent \textsc{Havel-Hakimi}$(n, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = b_1$ \` $\rhd$ 01. sor: $H_1$ számítása\\
\hspace{-7mm}02 \textbf{for} $i=2$ \textbf{to} $n$\` $\rhd$ 02--04. sor: $H$ értékek számítása\\
\hspace{-7mm}03 \>    $H_i = H_{i-1} + b_i$\\
\hspace{-7mm}04 \textbf{end}\\
\hspace{-7mm}05 \textbf{if} $H_n$ páratlan \` $\rhd$ 05--08. sor: paritás ellenőrzés\\
\hspace{-7mm}06 \>   $L =$ \textbf{false} \` $\rhd$ 06--07. sor: hibás sorozat elutasítása\\
\hspace{-7mm}07 \>   \textbf{return} $L$\\
\hspace{-7mm}08 \textbf{end}\\

\hspace{-7mm}09 $FF = b$\` $\rhd$ 09. sor: munkaváltozó inicializálása\\
\hspace{-7mm}10 \textbf{while} $FF_0>0$ \` $\rhd$ 10. sor: amíg nem értünk a sorozat végére\\
\hspace{-7mm}11 \>    \textbf{for} $j=1$ \textbf{to} $FF_0+1$ \` $\rhd$ 11--13. sor: kielégítjük az első fok igényét\\
\hspace{-7mm}12 \>    \>    $FF_j = FF_j - 1$\\
\hspace{-7mm}13 \>    \textbf{end}\\
\hspace{-7mm}14 \>    $FF_0 = 0$\` $\rhd$ 14. sor: nullázzuk az első elemet\\
\hspace{-7mm}15 \>    $sort\_descending(FF)$ \` $\rhd$ 15. sor: újrarendezzük a sort\\
\hspace{-7mm}16 \textbf{end}\\
\hspace{-7mm}17 $t=0$ \` $\rhd$ 09. sor: ideiglenes változó nullázása\\
\hspace{-7mm}18 \textbf{for} $i=0$ \textbf{to} $n$ \` $\rhd$ 18--20. sor: munkaváltozó értékeinek összegzése\\
\hspace{-7mm}19 \>    $t = t + FF_i$\\
\hspace{-7mm}20 \textbf{end}\\
\hspace{-7mm}21 \textbf{if} $t == 0$ \` $\rhd$ 21--25. sor: helyreállíthatóság eldöntése\\
\hspace{-7mm}22 \>    $L = true$ \` $\rhd$ 22. sor: helyreállítható\\
\hspace{-7mm}23 \textbf{else}\\
\hspace{-7mm}24 \>    $L = false$ \` $\rhd$ 24. sor: nem helyreállítható\\
\hspace{-7mm}25 \textbf{end}\\
\hspace{-7mm}26 \textbf{return} $L$
\end{tabbing}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Rövidített Erdős-Gallai algoritmus\label{sec-EGS}}
$H_i$ maximális értéke szabályos sorozat esetén $n(n - 1),$ ezért a 
(\ref{eq-EGbinom}) egyenlőtlenség $i = n$ esetén biztosan teljesül, így felesleges ellenőrizni. 

Ennél is hasznosabb észrevételt tartalmaz a következő lemma.

Tripathi és Vijay 2003-as cikkében \cite{TripathiV2003} szerepel az az észrevétel, hogy az Erdős-Gallai tételben 
a (\ref{eq-EGbinom}) egyenlőtlenséget elég csak addig ellenőrizni, amíg $H_i > i(i - 1)$ teljesül.

\begin{lemma} \emph{(Tripathi és Vijay \cite{TripathiV2003})} Ha\label{lemma-EGS} $n \geq 1,$\label{theorem-EGS} az $n$-szabályos 
$b = (b_1\ldots,b_n)$ sorozat akkor és csak akkor $n$-jó, ha 
\begin{equation}
H_n \quad \mbox{páros}\label{eq-EGSparos} 
\end{equation}
és
\begin{equation}
H_i - \min(H_i,i(i - 1)) \leq \sum _{k=i+1}^n \min(i,b_k) 
\quad (i = 1,2,\ldots,g),\label{eq-EGStbinom}
\end{equation}
ahol 
\begin{equation}
g = \max_{1 \leq k \leq n}(k \ | \ k(k - 1) < H_k).
\end{equation}
\end{lemma}  

\begin{proof} Ha $i(i - 1) \geq H_i,$ akkor (\ref{eq-EGbinom}) bal oldala nempozitív, ezért az egyenlőtlenség 
biztosan teljesül, így felesleges ellenőrizni. 
\end{proof}

Például a $b = (5^{100})$ sorozat esetén (\ref{eq-EGbinom}) jobb oldalát az Erdős-Gallai algoritmus szerint 99-szer, míg 
a rövidített Erdős-Gallai algoritmus szerint csak 6-szor kell kiszámítani. A javításnak a várható futási időre 
gyakorolt hatását a \ref{sec-pontosido}. részben vizsgáljuk. 

A \ref{lemma-EGS}. lemmán alapuló algoritmust rövidített Erdős-Gallai algoritmusnak (EGR) nevezzük.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Ugró Erdős-Gallai algoritmus}
Az ismétlődő elemeket összevonva egy szabályos $(b_1,\ldots,b_n)$ sorozat 
$(b_{i_1}^{e_1},$ \linebreak 
\noindent $\ldots, b_{i_q}^{e_q})$ alakban is felírható, ahol $b_{i_1} > \cdots > b_{i_q},$ $e_1,\ldots,e_q \geq 1$ és 
$e_1 + \cdots + e_q = n.$ Legyen $\sigma _j = e_1 + \cdots + e_j \ (j = 1, \ \ldots, q).$   

A $b_i$ elemet a $b$ sorozat \textit{ugró} elemének nevezzük, ha $i = n$ vagy  $1 \leq i \leq n - 1$ és $b_i > b_{i+1}$. 
Ekkor az ugró elemek a $b_{\sigma _1},b_{\sigma _2},\ldots,b_{\sigma _q}$ elemek. 

\begin{theorem} \emph{(Tripathi, Vijay \cite{TripathiV2003})} Az\label{tetel-EGJ} $n$-szabályos $b = (b_1\ldots,b_n)$ 
sorozat akkor és csak akkor $n$-jó, ha
\begin{equation} 
H_n \quad \mbox{páros}\label{eq-TVparos}
\end{equation}
és
\begin{equation}
H_{\sigma_i} - \sigma_i(\sigma_i - 1) \leq 
\sum _{k=\sigma _i + 1}^n \min(i,b_k) \quad (i = 1,\ldots,q).\label{eq-TVbinom}
\end{equation}
\end{theorem}

\begin{proof} Lásd \cite{TripathiV2003}.
\end{proof}

Később majd az \textsc{Erdős-Gallai-Lineárisan} algoritmusban kihasználjuk, hogy a (\ref{eq-TVbinom}) egyenlőtlenségben 
$\sigma _q$ mindig $n,$ és ezért $H_n - n(n - 1)$ mindig teljesül, így elég az egyenlőtlenséget 
$(i = q - 1)$-ig ellenőrizni. 

A következő program az Erdős-Gallai algoritmusnak az \ref{lemma-nullamentes}. és \ref{lemma-EGS}. lemma, valamint a 
\ref{tetel-EGJ}. tétel alapján gyorsított változatát mutatja be.\\

\textit{Bemenet}: $n $ a csúcsok száma $(n \geq 1)$; $b = (b_1, b_2, \ldots, b_n)$ $n$-szabályos sorozat

\textit{Kimenet}: $L$ logikai változó\\ ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy $b$ jó) 

\textit{Munkaváltozók}:\\ 
$H = (H_1,\ldots,H_n)$: $H_i$ $b$ első $i$ elemének az összege

\medskip
\noindent \textsc{Erdős-Gallai-Ugró}$(n, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = b_1$ \` $\rhd$ 01. sor: $H_1$ számítása\\
\hspace{-7mm}02 \textbf{for} $i=2$ \textbf{to} $n$\` $\rhd$ 02--04. sor: $H$ értékek számítása\\
\hspace{-7mm}03 \>    $H_i = H_{i-1} + b_i$\\
\hspace{-7mm}04 \textbf{end}\\
\hspace{-7mm}05 \textbf{if} $\mod(H_n, 2)$ \` $\rhd$ 05--08. sor: paritás ellenőrzés\\
\hspace{-7mm}06 \>   $L =$ \textbf{false} \` $\rhd$ 06--07. sor: hibás sorozat elutasítása\\
\hspace{-7mm}07 \>   \textbf{return} $L$\\
\hspace{-7mm}08 \textbf{end}\\
\hspace{-7mm}09 \textbf{for} $j=1$ \textbf{to} $n-1$ \` $\rhd$ 09--23. sor: sorozat ellenőrzése\\
\hspace{-7mm}10 \>    \textbf{if} $b_j = b_{j+1}$ \` $\rhd$ 10--12. sor: eldöntjük, hogy az adott pont ellenőrzőpont-e\\
\hspace{-7mm}11 \>    \>    \textbf{continue}\\
\hspace{-7mm}12 \>    \textbf{end}\\
\hspace{-7mm}13 \>    $R = 0$\` $\rhd$ 13. sor: munkaváltozó nullázása\\
\hspace{-7mm}14 \>    \textbf{for} $k=j+1$ \textbf{to} $n$ \` $\rhd$ 14--16. sor: a tétel szummájának számítása\\
\hspace{-7mm}15 \>       $R = R + min(j, b_k)$\\
\hspace{-7mm}16 \>    \textbf{end}\>\\
\hspace{-7mm}17 \>    \textbf{if} $H_j - j \cdot (j-1) > R$\` $\rhd$ 17. sor: a tétel feltételének ellenőrzése\\
\hspace{-7mm}18 \>    \>    \>    $L =$ \textbf{false}\` $\rhd$ 18--19. sor: rossz sorozat elutasítása\\
\hspace{-7mm}19 \>    \>    \>    \textbf{return} $L$\\
\hspace{-7mm}20 \>    \textbf{end}\>\\
\hspace{-7mm}21 \textbf{end}\\
\hspace{-7mm}22 $L =$ \textbf{true} \` $\rhd$ 22-23. sor: jó sorozat elfogadása\\
\hspace{-7mm}23 \textbf{return} $L$\\
\end{tabbing}

Ennek az algoritmusnak a futási ideje a legjobb $\Theta(1)$ és a legrosszabb $\Theta(n^2)$ között változik. 

 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lineáris Erdős-Gallai algoritmus\label{subsec-EGlinearis}}
A következő \textsc{Erdős-Gallai-Lineárisan} algoritmus kihasználja, hogy a $b$ bemeneti sorozat monoton. 
Ennek köszönhetően a $C_i$ kapacitásokat minden $i$-re konstans időben meg tudja határozni, azaz nincs szüksége arra, 
hogy a megfelelő farok elemeit egyenként megvizsgálja. A gyors számolás kulcsa a súlypontokat tartalmazó $w(b)$ sorozat.
 
Adott $b$ sorozat esetén legyen $w(b) = (w_1,\ldots,w_{n-1}),$ ahol $w_i$ a $b$ sorozat legnagyobb indexű olyan elemére 
mutat, ameyik legalább akkora, mint $i.$ 

\begin{theorem} Ha\label{theorem-EGL} $n \geq 1,$ a $b = (b_1\ldots,b_n)$ $n$-szabályos sorozat akkor és csak 
akkor $n$-jó, ha
\begin{equation}
H_n \quad \textrm{páros,}\label{eq-EGLparity}
\end{equation}
és ha $i>w_i$, akkor
\begin{equation}
H_i \leq i(i - 1) + H_n - H_i,  \label{eq-EGL}
\end{equation}
különben ha $i$  $w_i$, akkor
\begin{equation}
H_i \leq i(i - 1) + i(w_i -i) + H_n - H_{w_i}. \label{eq-EGLk}
\end{equation}
\end{theorem}  

\begin{proof} 
A $b$ sorozat $b_i$ elemének ellenőrzésekor két eset van: 
\begin{itemize}
\item ha $i > w_i,$ akkor a $C_i$ kapacitás 
egyszerűen számítható: $H_n - H_i,$ mivel a farok minden $b_j$ elemének hozzájárulása csak $b_j.$ \\

\item ha $i \leq w_1,$ akkor a farok hozzájárulása két esetet tartalmaz: $C_{i+1},\ldots,C_{m_i}$ 
egyenlő $i,$ while $C_j = b_j$ for $j = m_{i} + 1,\ldots,n.$  
\end{itemize}


Ezért ha $n - 1 \geq i > w_i$, akkor
\begin{equation}
C_i = i(i - 1) + H_n - H_i,\label{eq-EGLClargei}
\end{equation}
ha $1 \leq i \leq w_i$, akkor
\begin{equation}
C_i = i(i - 1) + i(w_i -i) + H_n - H_{w_i}.\label{eq-EGLCsmalli}
\end{equation}
\end{proof}  
 

A következő program a \ref{theorem-EGL}. tétel alapján adott $n$-re tetszőleges $n$-szabályos sorozatról  eldönti, hogy jó-e. 
A program futási ideje minden sorozatra $O(n).$ 
Érdemes megjegyezni, hogy akár a bemenő sorozat rendezettségétől is eltekinthetünk, mivel a sorozat elemei egész számok és 
mindegyik a $[0,n-1]$ intervallumba esik, így szükség esetén $O(n)$ idő alatt rendezni tudjuk a sorozatot.

\textit{Bemenet}: $n$ a csúcsok száma $(n \geq 1)$; $b = (b_1,\ldots,b_n)$: $n$-szabályos sorozat.  

\textit{Kimenet}: $L$ logikai változó\\
(melynek értéke \textsc{True}, ha a bemenet jó, és \textsc{False} egyébként) 

\textit{Munkaváltozók}  \\
$H = (H_1,\ldots,H_n)$: $H_i$ az éppen tesztelt $b$ első $i$ elemének az összege \\
$m = (m_1,\ldots,m_{n-1})$: $m_i$ a legnagyobb indexű olyan $b_j$ indexe, amely legalább $i$ \\
$H_0 = 0$: segédváltozó a $H$ sorozat elemeinek kiszámításához; \\
$b_0 = n -1$: segédváltozó az $m$ sorozat elemeinek kiszámításához; \\
$w = (w_1,\ldots,w_{n-1})$: $w_i$ a $b_i$ súlypontja, a legnagyobb eleme a $b$-nek ami nem kisebb mint $i$ \\


\newpage
\noindent \textsc{Erdős-Gallai-Lineárisan}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = 0$                                            \` $\rhd$  01. sor: értékadás \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$  02--03. sor: $H$ számítása    \\     
\hspace{-7mm}03 \> $H_i = H_{i-1} + b_i$ \\ 
\hspace{-7mm}04 \textbf{if} \= $H_n$ \textrm{ páratlan}    \` $\rhd$ 04--06. sor: paritás tesztelése   \\ 
\hspace{-7mm}05  \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $b_0 = n - 1$                             \` $\rhd$  07. sor: értékadás a segédváltozónak \\ 
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$ 08--12. sor: súlypont kiszámítása \\ 
\hspace{-7mm}09              \> \textbf{if} \= $b_i < b_{i-1}$  \\ 
\hspace{-7mm}10              \>             \> \textbf{for} \= $j = b_{i-1}$ \textbf{downto} $b_i + 1$ \\
\hspace{-7mm}11              \>             \>              \> $w_j = i - 1$ \\
\hspace{-7mm}12              \>             \> $w_{b_i} = i$ \\ 
\hspace{-7mm}13 \textbf{for} \= $j = b_n$ \textbf{downto} $1$  \` $\rhd$ 13--14. sor: large weights\\
\hspace{-7mm}14              \> $w_j = n$ \\  
\hspace{-7mm}15 \textbf{for} \= $i = 1$ \textbf{to} $n$            \` $\rhd$ 15--23. sor: a $b$ elemeinek tesztelése\\                          
\hspace{-7mm}16              \> \textbf{if} \= $i \leq w_i$        \` $\rhd$ 16--19. sor: test of indices for large $w_i$'s \\ 
\hspace{-7mm}17              \>             \> \textbf{if} \= $H_i > i(i - 1) + i(w_i - i) + H_n - H_{w_i}$ \\
\hspace{-7mm}18              \>             \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}19              \>             \>             \> \textbf{return} $L$ \\  
\hspace{-7mm}20              \> \textbf{if} \= $i > w_i$  \` $\rhd$ 20--23. sor: test of indices for small $w_i$'s \\  
\hspace{-7mm}21              \>             \> \textbf{if} \= $H_i >  i(i - 1) + H_n - H_i$ \\
\hspace{-7mm}22              \>             \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}23              \>             \>             \> \textbf{return} $L$ \\           
\hspace{-7mm}24 $L = \textsc{True}$ \` $\rhd$ 24--25. sor: a program visszatérési értéke \textsc{True} \\
\hspace{-7mm}25 \> \textbf{return} $L$  \\ 
\end{tabbing}

\begin{corollary} Nemnegatív egészek $n$-szabályos $b = (b_1,\ldots,,b_n)$ sorozatáról $theta(n)$ idő alatt eldönthető, hogy 
létezik-e olyan $G$ egyszerű gráf, amelynek $b$ a foksorozata. 
\end{corollary} 

\begin{proof} Az első sor $O(1)$, 2--3. sor $\Theta(n)$, 4--6. sor $O(1)$, 07. sor $O(1)$ , 
08--12. sor $O(1)$, 13--14. sor $O(n)$, 15--23. sor $O(n)$ és 24--25. sor $O(1)$ időben végezhető el, 
ezért a szükséges futási idő $\Theta(n)$. 
\end{proof}
Mivel a jó sorozatok minden elemét megvizsgáljuk a teszt során, ezért a RAM számítási modell alapján a  \cite{CormenLRS2009} \textsc{Erd\H os-Gallai-Linear} aszimptotikusan optimális.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Gyors Erdős-Gallai algoritmus\label{subsec-EGlinearis}}
A \textsc{Erdős-Gallai-Lineárisan} algoritmus egyik lehetséges alkalmazása, hogy meghatározzuk a jó sorozatok számát 
olyan $n$ értékekre, amelyekre eddig a nagy számolásigény miatt nem volt ismert: Sloane 
\textit{On-line Encyclopedia of Integer Sequences} című honlapja \cite{Sloane2011} az $n = 23$ értékig 
tartalmazza a jó sorozatok számát. 

Az alábbi \textsc{Erdős-Gallai-Gyorsan} algoritmus a lineáris legrosszabb eset mellett azt is igyekszik kihasználni, hogy ha 
lexikografikus sorrendben ellenőrizzük a szóbajövő sorozatokat, akkor a szomszédos sorozatok bizonyos tulajdonságai 
nagyon hasonlóak, ezért adott sorozat jellemzői az őt megelőző sorozat jellemző adataiból konstans idő alatt meghatározhatóak. 

Igyekszünk az ellenőrizendő sorozatok számát is csökkenteni. 

Ennek egy egyszerű megoldása, hogy eleve csak a páros sorozatokat állítjuk elő. További ötlet, hogy csak a nullamentes sorozatokat 
vizsgáljuk. A nullát tartalmazó $n$-jó sorozatok között ugyanis a \ref{lemma-nullaatl}. lemma szerint pontosan 
$G(n - 1)$ jó sorozat van. Igaz, hogy aszimptotikusan a nullát tartalmazó sorozatok a páros sorozatok elhanyagolható részét adják, de az általunk most gyakorlatilag vizsgált 
$n \in [4,30]$ tartományban még jelentős a részarányuk. 

Lényeges gyorsítást jelent az is, hogy a sorozatokat csak az ellenőrző pontokban vizsgáljuk.

Az \textsc{Erdős-Gallai-Gyorsan} program azt is kihasználja, hogy a szomszédos sorozatok ellenrző pontjainak a listája 
átlagosan konstans idő alatt származtatható a megelőző sorozat adataiból. A kiindulási értékek szintén könnyen 
számíthatók: az első -- $\textbf{q} = (n - 1)^n$ -- sorozatra a $C$ lista üres (azaz egyáltalán nem kell elllenőrzést végeznünk), 
a mutatók listája pedig kezdetben $m = \left ((n - 1)^{n - 1} \right.$

Az \textsc{Erdős-Gallai-Gyorsan} algoritmus előállítja és megvizsgálja az $n$-páros, nullamentes sorozatokat,  
és kimenetként megadja a $G(n)$ értéket. Az algoritmus kihasználja, hogy a páros sorozatok lexikografikusan 
csökkenő sorozatában szomszédos sorozatok több lényeges paramétere hasonló, ezért ezek a paraméterek a vizsgált $b'$ 
sorozatot megelőző $b$ sorozat adott paraméteréből gyorsan meghatározhatóak. 

\textit{Ellenőrző pontoknak} nevezzük a $n$-nél kisebb ugró pontokat. Az ellenőrző pontok $C(b')$ listája rendszerint megegyezik 
a $C(b)$ listával, és legfeljebb a végén változik egy vagy két elem.  

\textit{Bemenet}. $n$: a csúcsok száma $(n \geq 4);$ (azért korlátozzuk $n$-et alulról, hogy a 
programot mentesítsük a rövid sorozatok speciális tulajdonságainak figyelembe vételétől).


\textit{Kimenet}. $G$: az $n$-jó sorozatok száma. 

\textit{Munkaváltozók.} $i$ és $j$: ciklusváltozók; \\
$b = (b_1,\ldots,b_n)$: $b_i$ az éppen tesztelt páros, nullamentes sorozat $i$-edik eleme; \\
$b_0 = n - 1$: segédváltozó a $H$ sorozat elemeinek kiszámításához; \\ 
$H = (H_1,\ldots,H_n)$: $H_i$ az éppen tesztelt $b$ első $i$ elemének az összege; \\
$H_0$: segédváltozó $H$ elemeinek számolásához; \\
$C(b) = C = (c_1,c_2,\ldots,c_{q-1})$: ellenőrző pontok maximális hosszúságú listája; \\ 
$c$: ellenőrző pontok száma az aktuális $C$ listában; \\
$m = m_1,\ldots,m_{n-1}$: $m_i$ a legnagyobb indexű olyan $b_j$ indexe, amely legalább $i$;
$q$: ellenőrzésre eddig az indexig van szükség;
$k$: ellenőrzés egyszerűsítéséhez használt változó.


\medskip
\noindent \textsc{Erdős-Gallai-Gyorsan}$(n,G)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = c = 0$                                              \` $\rhd$ 01--03. sor: kezdeti értékek beállítása \\
\hspace{-7mm}02 $G = 1$ \\
\hspace{-7mm}03 ??? \\
\hspace{-7mm}04 \textbf{for} \= $i = 1$ \textbf{to} $n$           \` $\rhd$ 04--05. sor: első vizsgált sorozat előállítása   \\     
\hspace{-7mm}05              \> $b_i = n - 1$ \\
\hspace{-7mm}06              \> $H_i = H_i + b_i$                              \` $\rhd$ 06. sor: $H_i$-k előállítása \\        
\hspace{-7mm}07 \textbf{while} \= $b_2 \geq 2$                             \` $\rhd$ 07. sor: van-e még vizsgálandó sorozat?   \\ 
\hspace{-7mm}08                \> ??? \\
\hspace{-7mm}09                \> ??? \\
\hspace{-7mm}10                \> \textbf{for} \= $i=1$ \textbf{to} $c$   \` $\rhd$ 10--15. sor: aktuális sorozat tesztelése \\
\hspace{-7mm}11                \>              \> \textbf{if} ??? \\
\hspace{-7mm}12                \>              \>                       \> \textbf{if} \= ??? \\
\hspace{-7mm}13                \>              \>                       \>             \> ??? \\
\hspace{-7mm}14                \>              \> \textbf{else} \textbf{if} \= ??? \\
\hspace{-7mm}15                \>              \>                           \>  \textbf{go to} 19   \` $\rhd$ áttérés új sorozatra \\         
\hspace{-7mm}16                \> $G = G + 1$       \` $\rhd$ 16. sor: jó sorozat esetén $G$ növelése  \\
\hspace{-7mm}17                \> \textbf{go to} 19                               \` $\rhd$ áttérés új sorozatra  \\
\hspace{-7mm}18 \textbf{return} $G$ \` $\rhd$ 18. sor: program befejezése \\ 
\hspace{-7mm}19 \textbf{if \ \ } \= $b_n \geq 3$             \` $\rhd$ 19--??. sor: új sorozat előállítása \\
\hspace{-7mm}20                  \> $b_n = b_n - 2$            \` $\rhd$ 19--25. sor: ha $b_n = 3$     \\
\hspace{-7mm}21                  \> $H_n = H_n - 2$ \\
\hspace{-7mm}22                  \> \textbf{if} \= $b_n == b_{n-1} - 2$ \\
\hspace{-7mm}23                  \>             \> $c = c + 1$ \\
\hspace{-7mm}24                  \>             \> $C_c = n - 1$ \\
\hspace{-7mm}25                  \> \textbf{go to} 07 \\             
\hspace{-7mm}26 \textbf{else} \= \textbf{if} \= $b_n == 2$                                   \` $\rhd$ 26--46. sor: ha $b_n = 2$\\
\hspace{-7mm}27               \>             \> \textbf{if} \= $b_{n - 1} > 2$ \\
\hspace{-7mm}28               \>             \>             \> $b_{n-1} = b_{n-1} - 1$ \\
\hspace{-7mm}29               \>             \>             \> $H_{n-1} = H_{n-1} - 1$ \\
\hspace{-7mm}30               \>             \>             \> $b_n = b_{n-1}$ \\
\hspace{-7mm}31               \>             \>             \> $H_n = H_n + b_n - 3$ \\ 
\hspace{-7mm}32               \>             \> \textbf{if} \= $b_{n-1}$ páros \\
\hspace{-7mm}33               \>             \>             \> $b_n = b_n - 1$ \\
\hspace{-7mm}34               \>             \>             \> $C_c = n - 2$  \\
\hspace{-7mm}35               \>             \>             \> $c = c + 1$ \\
\hspace{-7mm}36               \>             \>             \> $C_c = n - 1$ \\
\hspace{-7mm}37               \>             \> \textbf{if} \= $b_{n-2} > b_{n-1} + 1$ \\
\hspace{-7mm}38               \>             \>             \> $c = c + 1$ \\
\hspace{-7mm}39               \>             \>             \> $C_c = n - 1$ \\
\hspace{-7mm}40               \>             \> \textbf{else} \= $C_c = n - 2$ \\
\hspace{-7mm}41               \> \textbf{else} \= \textbf{if} \= $b_{n-1} == b_n$  \\
\hspace{-7mm}42               \>               \>             \> $C_c = n - 2$ \\
\hspace{-7mm}43               \>               \> \textbf{else} \= $c = c + 1$ \\ 
\hspace{-7mm}44               \>               \>               \> $C_c = n - 1$ \\
\hspace{-7mm}45               \> \textbf{go to} 07 \\
\hspace{-7mm}46 \textbf{else}  \= $j = n - 1$                              \` $\rhd$ 46--??. sor: ha $b_n = 1$  \\
\hspace{-7mm}47                \> \textbf{while} \= $b_j == 1$ \\
\hspace{-7mm}48                \>                \> $j = j - 1$ \\
\hspace{-7mm}49                \> \textbf{ if } \= $b_j > 2$ \\ 
\hspace{-7mm}50                \>               \> \textbf{for} \= $k = j$ \textbf{to} $n$ \\
\hspace{-7mm}51                \>               \>              \> $b_k = b_j - 1$ \\
\hspace{-7mm}52                \>               \>              \> $H_k = H_k - 1 + (k - j)(b_j - 1)$ \\
\hspace{-7mm}53                \>               \> \textbf{if} \= $(n - j)(b_j + 1)$ páros \\
\hspace{-7mm}54                \>               \>             \> $b_n = b_n - 1$ \\
\hspace{-7mm}55                \>               \>             \> $H_n = H_n - 1$  \\
\hspace{-7mm}56                \>               \> \textbf{if} \= $j > 1$ \\
\hspace{-7mm}57                \>               \>             \> \textbf{if} \= $b_j < b_{j-1} - 1$ \\
\hspace{-7mm}58                \>               \>             \>            \> $c = c -1$ \\
\hspace{-7mm}59                \>               \>             \>            \> \textbf{if} \= $b_n < b_{n-1}$ \\
\hspace{-7mm}60                \>               \>             \>            \>             \> $c = c + 1$ \\
\hspace{-7mm}61                \>               \>             \>            \>             \> $C_c = n -1$ \\
\hspace{-7mm}62                \>               \>             \>            \> \textbf{else} \= $C_c = j - 1$ \\
\hspace{-7mm}63                \>               \>             \>            \>               \> \textbf{if} \= $b_n < b_{n-1}$ \\
\hspace{-7mm}64                \>               \>             \>            \>               \>             \> $c = c + 1$ \\ 
\hspace{-7mm}65                \>               \>             \>            \>               \>             \> $C_c = n - 1$ \\
\hspace{-7mm}66                \> \textbf{go to} 07 \\


\hspace{-7mm}60                \>               \> \textbf{else} \= \textbf{  for} \= $k = j-1$ \textbf{to} $n$ \\
\hspace{-7mm}61                \>               \>                \>                \> $b_k = b_{j-1} - 1$ \\
\hspace{-7mm}62                \>               \>                \>                \> $H_k = H_k - 1 + (k - j + 1)(b_{j-1} - 1)$ \\ \\ \\

\hspace{-7mm}63                  \> ???              \> \\
\hspace{-7mm}64                  \> ???              \> \\
\hspace{-7mm}65                  \> ??? \\
\hspace{-7mm}66                  \> ???  \\ 
\hspace{-7mm}67                  \> ??? \\
\hspace{-7mm}68                  \> ???  \\    
\hspace{-7mm}69                  \> \textbf{go to} 07  \\
\end{tabbing}


 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Leszámlálási eredmények\label{sec-leszam}}
Eddig például Avis és Fukuda \cite{AvisF1996}, Barnes és Savage \cite{BarnesS1995,BarnesS1997}, Burns \cite{Burns2007}, 
Erdős és Moser \cite{Moon1968}, Frank, Savage and Sellers \cite{FrankSS2002}, Kleitman és Winston \cite{KleitmanW1981},  
R{\o}dseth, Sellers, Tverberg  \cite{RodsethST2009}, Ruskey et al. \cite{RuskeyCES1994}, Simion \cite{Simion1997}, 
Stanley \cite{Stanley1991}, Winston és Kleitman \cite{WinstonK1983} publikáltak foksorozatok leszámlálására vonatkozó 
eredményeket. Az általunk vizsgált sorozatok számával kapcsolatos eredmények találhatók Sloane és Ploffe \cite{SloaneP1995}, 
valamint Stanley \cite{Stanley1997} könyvében és az \textit{On-line Encyclopedia of Integer Sequences} című honlapon 
\cite{Sloane2011A001700,Sloane2011A004251,Sloane2011A005654} is. 

Könnyen belátható, hogy ha $l, \ m$ és $u$ egész számok, továbbá $l \geq u$ és $1 \geq m,$ és $l \leq b_i \leq u$ akkor az 
$(l,u,m)$-korlátos sorozatok $\kappa(l,u,m)$ száma
\begin{equation}
\kappa(l,u,m) = (u - l + 1)^m.\label{eq-kappan}
\end{equation}


Tudjuk (lásd \cite[65. oldal]{Jarai2005}), hogy ha $l, \ u$ és  $m$ egészek, továbbá $u \geq l$ és $m \geq 1$, 
and $u \geq b_1 \geq \cdots \geq b_n \geq l,$ akkor a $(l,u,m)$-szabályos sorozatok száma $R(l,u,m)$. 
\begin{equation} 
R(l,u,m) = \binom{m + u - l}{m}. \label{eq-rhon}
\end{equation}

Az előző két speciális eset \ref{eq-rhon }. nagyon hasznos a leszámlálást végző algoritmusok számára.

Ha $n \geq 1$ egész szám, akkor $R(0,n-1,n)$-szabályos sorozatok száma 
\begin{equation}
R(0,n-1,n) = R(n) = \binom{2n - 1}{n}.\label{eq-lum3}
\end{equation}

Ha $n \geq 1$ egész szám, akkor $R(1,n-1,n)$-szabályos sorozatok száma
\begin{equation}
R(1,n-1,n) = R_z(n) = \binom{2n - 2}{n}.\label{eq-lum4}
\end{equation}

1987-ben Ascher az alábbi explicit megoldást adta a páros sorozatok számára vonatkozóan.

\begin{lemma} \emph{(Ascher \cite{Ascher1987}, Sloane and Pfoffe \cite{SloaneP1995})} Ha\label{lemma-epsn} $n \geq 1,$ 
akkor az $n$-páros sorozatok száma $E(n)$ 
\begin{equation}
E(n) = \frac{1}{2} \left ( \binom{2n -1}{n} + \binom{n - 1}{\lfloor n \rfloor} \right ).\label{eq-epsen}
\end{equation}
\end{lemma}

\begin{proof} Lásd \cite{SloaneP1995}.
\end{proof}

A \ref{lemma-rhon}. és a \ref{lemma-epsn}. lemmák egybe vetése mutatja, hogy a páros és páratlan sorozatok számának 
nagyságrendje megegyezik, azonban több a páros sorozat, mint a páratlan. A \ref{lemma-epsn}. lemma alapján pontosan 
meg tudjuk adni $E(n)$ aszimptotikus nagyságrendjét.



\begin{lemma} Ha $n \geq 1,$ akkor\label{lemma-rhonjell}
\begin{equation}
\frac{R(n + 2)}{R(n + 1)} > \frac{R(n + 1)}{R(n)},\label{eq-rhonmon}
\end{equation}
\begin{equation}
\lim R _{n \rightarrow \infty} = 4,\label{eq-rhonlim}
\end{equation}
továbbá
\begin{equation}
\frac{4^n}{\sqrt{4\pi n}}\large (1 - \frac{1}{2n} \large) < R(n) < 
\frac{4^n}{\sqrt{4\pi n}}\large(1 - \frac{1}{8n+8}\large).\label{eq-rhonass} 
\end{equation}
\end{lemma}

\begin{proof} 
A (\ref{eq-rhon}) egyenlőség alapján
\begin{equation}
\frac{R(n + 2)}{R(n + 1)} = \frac{(2n + 3)!(n + 1)n!}{(n + 2)!(n + 1)!(2n + 1)!} 
 = \frac{4n + 6}{n + 2} = 4 - \frac{2}{n + 2}, \label{eq-rhonbiz}
\end{equation} 
ahonnan (\ref{eq-rhonmon}) és (\ref{eq-rhonlim}) is közvetlenül adódik.
\end{proof}
A \ref{lemma-epsntul} felhasználásával megadhatjuk precise asymptotic order of growth of $E(n)$.


\begin{lemma} Ha\label{lemma-epsntul} $n \geq 1,$ akkor
\begin{equation}
\frac{E(n + 2)}{E(n + 1)} > \frac{E(n + 1)}{E(n)},\label{eq-epsnmon}
\end{equation}
\begin{equation}
\lim E _{n \rightarrow \infty} = 4,\label{eq-epsnlim}
\end{equation}
továbbá 
\begin{equation}
\frac{4^n}{\sqrt{\pi n}}(1 - \delta _3(n)) < E(n) < \frac{4^n}{\sqrt{\pi n}}(1 - \delta _4(n)),\label{eq-epsnnass} 
\end{equation}
ahol $\delta _3(n)$ és $\delta _4(n)$ monoton csökkenve nullához tartó sorozatok.
\end{lemma}

\begin{proof} A bizonyítás hasonló a \ref{lemma-rhonjell}. lemma bizonyításához.
\end{proof}

?????????????????????????????????????
A (\ref{eq-lum3}) és (\ref{lemma-epsen}) összehasonlítva látjuk, hogy a , that the order of growth of numbers of 
even and odd sequences is the same, de több páros sorozat van mint páratlan. 
Az \ref{fig-parszabarany}. ábra tartalmazza $R(n)$, $E(n)$ és $E(n)/R(n)$ értékeit $n = 1, \ \ldots, \ 37$-ig.
Amint azt a következő állítás és a \ref{fig-parszabarany}. ábra is mutatja, az $E(n)/R(n)$ hányadosok sorozata 
monoton csökkenve $\frac{1}{2}$-hez tart. 

\begin{corollary} Ha\label{cor-epsmon} $n \geq 1$, akkor
\begin{equation}
\frac{E(n + 1)}{R(n + 1)} < \frac{E(n)}{R(n)}\label{eq-epsrhomon}
\end{equation}
és
\begin{equation}
\lim _{n \leftarrow \infty} \frac{E(n)}{R(n)} = \frac{1}{2}.\label{eq-epsrholim}
\end{equation}
\end{corollary}

\begin{proof} Az állítás a \eqref{eq-lum3} és \eqref{eq-epsen} következménye.

\end{proof}


Bár az alapfeladatban nemnegatív elemekből álló sorozatok szerepelnek, algoritmusaink -- a futási idő csökkentése érdekében -- 
csak a sorozatok pozitív kezdőszeletét vizsgálják. Ennek várható hatását jellemzi a következő két állítás, amelyek a nullát 
tartalmazó sorozatok számát és a sorozatokban lévő nullák átlagos számát adják meg.

\begin{lemma} Ha\label{lemma-nullasszab} $n \geq 1,$ akkor az $n$-szabályos sorozatok közül
\begin{equation}
\binom{2n - 2}{n - 1} = \frac{n}{2n - 1}R(n).\label{eq-0szabalyos}
\end{equation}
tartalmaz legalább egy nullát.  
\end{lemma}

\begin{proof} A nullát tartalmazó $n$-szabályos sorozatok halmaza kölcsönösen egyértelműen leképezhető az $(n - 1,n)$-szabályos 
sorozatok halmazára. Az utóbbi halmaz elemszáma pedig a \ref{lemma-rhon}. lemma szerint 
\begin{equation}
\binom{2n - 2}{n - 1} = \frac{(2n - 2)!n}{n(n - 1)!(2n - 1)} = \frac{n}{2n - 1}\binom{2n - 1}{n}.
\end{equation}
\end{proof}

\begin{lemma} Ha\label{lemma-nullaatl} $n \geq 1,$ akkor az $n$-szabályos sorozatokban lévő nullák átlagos száma
\begin{equation}
\frac{\sum _{i=0}^n i\binom{2n - 3}{n - i}}{\binom{2n - 1}{n}}. \label{eq-0katl}
\end{equation}  
\end{lemma}
\begin{proof} Az $n$-szabályos sorozatokban $0,\ 1, \ldots, n - 1$ vagy $n$ nulla van. Az $i$ nullát és $n - i$ pozitív elemet 
tartalmazó $n$-szabályos sorozatok száma ugyanannyi, mint ahány féleképpen $2n - 3$ különböző elem közül $n - i$ 
kiválasztható.  
\end{proof}

A pontos algoritmusokról szóló \ref{subsec-nullamentes}. részben beláttuk, hogy elég az $n$-páros sorozatok nullamentes prefixét 
megvizsgálni ahhoz, hogy eldöntsük, jó-e a vizsgált sorozat. Mivel a \ref{lemma-nullasszab} páros sorozatoknak 
aszimptotikusan csak nullmértékű hányada tartalmaz nullát (és ez a hányad a gyakorlat számára legérdekesebb $n$-ekre sem nagy), 
konkrét sorozatok vizsgálatánál nem jelentős az időmegtakarítás. Amikor viszont az összes $n$-páros sorozatot elemezzük 
(az átlagos futási idő vagy $G(n)$ meghatározása érdekében), nagyon hasznos a következő lemma.

Legyen $\zeta(n)$ a nullamentes jó $n$-páros sorozatok száma.

\begin{lemma} Ha\label{lemma-nullaatl} $n \geq 2,$ akkor az $n$-jó sorozatok száma 
\begin{equation}
G(n) = \zeta{n} + G(n - 1). \label{eq-zerofreegood}
\end{equation}  
\end{lemma}
\begin{proof} Az $n$-jó sorozatokban vagy $b_n = 0,$ vagy $b_n > 0.$ Az előbbiekben vagy $b_1 = n -1,$ vagy $b_1 < n_ 1.$ 
Ha $b_1 = n - 1$ és $b_n = 0,$ akkor a $b$ sorozat biztosan rossz, mert nincs benne elég pozitív elem. A $b_1 < n -1$ és 
$b_n = 0$ tulajdonságú sorozatok $n - 1$ hosszú fejei pontosan az $(n - 1)$-jó sorozatok.
\end{proof}
 



Az ugró elemek számának várható értéke lényegesen befolyásolja a velük kapcsolatos algoritmusok futási idejét. Ezért hasznos a 
következő két állítás. 

Egy $n$-korlátos sorozat \textit{szivárvány száma} a sorozatban lévő különböző elemek száma.

\begin{lemma} \emph{(Móri \cite{Mori2011})}. Ha\label{lemma-korsziv} $n \geq 1,$ akkor az $n$-korlátos 
sorozatok átlagos szivárvány száma 
\begin{equation}
\frac{n^2}{2n - 1}.\label{eq-Mori1}
\end{equation}
\end{lemma}
\begin{proof}
\end{proof}

Megjegyezzük, hogy ez a lemma választ ad egy Kátai Imre által \cite{Katai2010} az átfedéses memóriájú számítógépekkel és a  
rejtvények megoldásait ellenőrző algoritmusokkal kapcsolatban felvetett kérdésre. 

\begin{lemma} \emph{(Móri \cite{Mori2011})}. Ha\label{lemma-szabsziv} $n \geq 1,$ akkor az $n$-szabályos 
sorozatok átlagos szivárvány száma 
\begin{equation}
\frac{n}{2} + \frac{1}{4} + \frac{3}{8n - 4}.
\end{equation}
\end{lemma}
\begin{proof} Egy $n$-szabályos sorozatban $1, \ 2, \ \ldots, \ n$ különböző elem lehet. $n$ különböző elem közül $k$ elemet 
$\textbinom{n}{k}$ féleképpen választhatunk ki. Ha már kiválasztottunk $k$ elemet, akkor ezeket $\textbinom{n - 1}{k - 1}$ 
módon rendezhetjük, hiszen az azonos elemekből álló részsorozatokat elválasztó $k - 1$ helyet a sorozat $n$ eleme közti 
$n - 1$ hely közül kell kiválasztanunk. Figyelembe véve, hogy a \ref{lemma-rhon}. lemma szerint az $n$-szabályos sorozatok száma 
$R(n) = \textbinom{2n - 1}{n},$ az $n$-szabályos sorozatok átlagos szivárványszáma 
\begin{equation}
\frac{\sum _{k=1}^n k \binom{n}{k} \binom{n - 1}{k - 1}}{\binom{2n - 1}{n}}.\label{eq-Mori1varhato}
\end{equation}  
Ezt a kifejezést átalakítva és felhasználva a hipergeometrikus sorozat várható értékére vonatkozó képletet, az  
adódik, hogy a keresett várható érték 
\begin{equation}
\frac{n^2}{2n - 1} = \frac{n}{2} + \frac{1}{4} - \frac{3}{8n - 4}.\label{eq-Mori1ered}
\end{equation}
\end{proof}

A következő állítás a rendező és az eltoló Havel-Hakimi algoritmusok futási idejének összehasonlításánál hasznosak. 
\begin{lemma} Ha $n \geq 1,$ akkor egy $n$-szabályos sorozatot $b = (b_1^{e_1},\ldots,b_q^{e_q})$ alakban felírva 
az $e_j$ kitevők (\idez{futamhosszak}) várható értéke 

konstans ???
\end{lemma}

\begin{proof} ????
\end{proof}


A jó sorozatok $G(n)$ számának jellemzésével kapcsolatos kutatások ígéretes iránya a páros számok pozitív összeadandókra 
való felbontása, és annak vizsgálata, hogy az ilyen felbontások közül melyek jók \cite{BarnesS1995,BarnesS1997,Burns2007}. 
Ezek segítségével sikerült a jó sorozatok számára vonatkozó alábbi aszimptotikus korlátokat bizonyítani.

\begin{lemma} \emph{(Burns \cite{Burns2007})} Léteznek olyan pozitív $c$ és $C$ állandók, hogy a jó sorozatok  
$G(n)$ száma a következő korlátok közé esik:
\begin{equation}
\frac{4^n}{cn} < G(n) <  \frac{4^n}{(\log n)^C \sqrt{n}} \ .
\end{equation}
\end{lemma}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tesztelő algoritmusok\label{sec-teszt}}

A minket is érdeklő focisorozatok vizsgálatakor gyakran szükség van egy foksorozat tesztelésére.

Lehetséges mód a tesztelési idő csökkentésére, ha gyors (lineáris) szűrő algoritmusokat futtatunk, amivel a nem jó sorozatok nagy része elutasítható, így a lassú pontos algoritmusokkal csak a visszamaradó sorozatokat kell vizsgálni.  

Bemutatunk egy \idez{paritásos}, majd egy \idez{pozitív}, egy \idez{binomiális} és végül egy \idez{fejfelező}                                                                                            tesztelő/szűrő algoritmust. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Paritás teszt\label{subsec-paritas}}
Első tesztünk az Erdős-Gallai tétel első szükséges feltételén alapul. Nagyon hatékony teszt, mivel szabályos sorozatoknak körülbelül fele páratlan sorozat ( \ref{fig-parszabarany}. ábra, \ref{eq-epsrholim}. ), és a teszt ezekről lineáris idő alatt megállapítja, 
hogy biztosan nem jó sorozatok.



\begin{lemma} Ha\label{lemma-paritas} $n \geq 1$ és $b$ $n$-jó sorozat, akkor
\begin{equation}
H_n \quad \mbox{páros}.\label{eq-parossag}
\end{equation}
\end{lemma}

\begin{proof} Egy egyszerű gráf minden éle kettővel növeli a fokszámok összegét.
\end{proof}

Ezt az állítást a \ref{tetel-EG}. tétel következményeként is megkaphatjuk.
A \ref{lemma-paritas}. lemmában javasolt tesztet a következő algoritmus végzi.\\

\textit{Bemenet}: $n$ a csúcsok száma $(n \geq 1)$; $b = (b_1, b_2, \ldots, b_n)$ $n$-szabályos sorozat.
\textit{Kimenet}: $L$ logikai változó 
\\($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg $L = \textsc{True}$ azt mutatja, hogy a teszt \textit{nem tudta eldönteni,} hogy $b$ jó-e); \\
$H = (H_1, \ldots, H_n)$: $H_i$ a $b$ sorozat első $i$ elemének összege; 

\medskip
\noindent \textsc{Paritás-teszt}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n$ \\
\hspace{-7mm}03              \> $H_i = H_{i - 1} + b_i$ \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ páratlan \\
\hspace{-7mm}05             \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $L = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $L$
\end{tabbing}

Ennek az algoritmusnak a lépésszáma minden esetben $\Theta(n)$. Az \ref{fig-parszabarany}. ábra mutatja milyen hatékony a \textsc{Paritás-teszt}. 
A \textsc{Paritás-teszt} csak egy közelítő algoritmus mivel csak a (\ref{eq-EGparity}.) szükséges feltételt ellenőrzi.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Binomiális teszt\label{subsec-binom}}
Második tesztünk az Erdős-Gallai tétel másik szükséges feltételének ötletét terjeszti ki. 
Az algoritmus nevét arról kapta, hogy a fej és a farok belső éleinek a számát egy-egy binomiális együttható segítségével becsüljük. 
Legyen $T_i = b_{i+1} + \cdots + b_n  \ (i = 1, \ldots, n)$.

\begin{lemma} Ha\label{lemma-binom} $n \geq 1$ és $b$ $n$-jó sorozat, akkor 
\begin{equation} 
H_i  \leq i(i - 1) + T_i \quad (i =1, \ldots, n-1).\label{eq-binom1}
\end{equation}
\end{lemma}

\begin{proof} A (\ref{eq-binom1}) egyenlőtlenség azt fejezi ki, hogy a fej $H_i$ igényét a legfeljebb $i(i - 1)$ 
belső lehetőség és a farok legfeljebb $T_i$ kapacitása segítségével kell kielégíteni, ahol $T_I = H_n - H_i.$ 
\end{proof}

A \ref{lemma-binom}. lemmában javasolt tesztet végzi el a következő program.\\

\textit{Bemenet}: $n$ a csúcsok száma $(n \geq 1)$; $b = (b_1, b_2, \ldots, b_n)$ $n$-páros sorozat; \\
$p$ a $b$ sorozat pozitív elemeinek a száma; 
\textit{Kimenet}. $L$: logikai változó \\ ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy a teszt \textit{nem tudta eldönteni,} hogy $b$ jó-e). 
\textit{Munkaváltozó}:\\
$T = (T_1, \ldots, T_n)$: $T_i$ az utolsó $n - i$ elem összeg $b$; \\
$H = (H_1, \ldots, H_n)$: $H_i$ a $b$ sorozat első $i$ elemének összege.

\medskip
\noindent \textsc{Binomiális-teszt}$(n,b,H,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $T_0 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}03              \> $T_i = H_n - H_i$ \\
\hspace{-7mm}04              \> \textbf{if} \= $H_j > i(i - 1) + T_i$ \\
\hspace{-7mm}05              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}06              \>             \> \textbf{return} $L$ \\          
\hspace{-7mm}07 $L = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $L$
\end{tabbing}


Az algoritmus futási ideje legrosszabb esetben $\Theta(n)$, míg a legjobb esetben $\Theta(1)$. 

A tesztek alapján \textsc{Binomial-Test} egy hatékony tesztelő algoritmus (lásd \ref{fig-sorozatszam}. ábra).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fej felezése\label{subsec-fejfelezteszt}}
A $b$ sorozat fokpárosító lehetőségeinek az eddigieknél pontosabb becslését kaphatjuk, ha a fejet két részre osztjuk a (\ref{eq-binom1}) binomiális együttható alapján. Legyen $\lfloor i/2 \rfloor = h_i$, $p$ a $b$ sorozat pozitív elemeinek a száma. A $(b_1,\ldots,b_{h_i})$ sorozatot az $i$ indexhez tartozó fej  
\textit{elejének}, a $(b_{h_i+1},\ldots,b_i)$ sorozatot pedig az $i$ indexhez tartozó fej \textit{végének} nevezzük.

\begin{lemma} Ha \label{lemma-headsplitting} $n \geq 1$ és $b$ egy $n$-jó sorozat, akkor 
\begin{align}
H_i & \leq \min(\min(H_{h_i},T_n - T_i,h_i(n - i))\notag \\
    & + \min(H_i - H_{h_i},T_n - T_i,(i - h_i)(n - i)),T_i) \notag \\
    & + \min(h_i(i - h_i) + \binom{h_i}{2} + \binom{i - h_i}{2}  \quad (i = 1, \ldots, n),\label{eq-HSa}
\end{align}
továbbá
\begin{equation}
\min(H_{h_i},T_n - T_i,h_i(n - i)) + \min(H_i - H_{h_i},T_n - T_i,(i - h_i)(n - i)) \leq T_i.\label{eq-HSb}
\end{equation}
\end{lemma}

\begin{proof}  
Hasonló gondolatmenettel adódik megkapjuk (\ref{eq-X2})-t is. 

Ugyanakkor annak is teljesednie kell, hogy sem a fej, sem a farok nem lépi túl a saját kapacitását, azaz 
$2X_3 \leq \min(2(X_1 + X_2),H_i,T_n - T_i).$ Legyen $Z = \min(2(X_1 + X_2),H_i,T_n - T_i).$

Ehhez jön a fej elejének $X_2$-vel becsült további hozzájárulása és a fej végének $X_3$-mal 
becsült további hozzájárulás  

$X_1$ nem lehet nagyobb, mint a fej elejében ($H_{h_i}$), illetve a fej végében $(H_i - H_{h_i})$ lévő elemek összegének kétszerese. 
Ugyancsak igaz, hogy a fej elejéhez tartozó $h_i$ elem egyenként legfeljebb $b_{h_i+1},$ míg a fej végéhez tartozó $i - h_i$ 
elem egyenként legfeljebb $b_1$ fokkal kapcsolódhat a fej másik részéhez. És az is igaz, hogy a két rész elemeiből legfeljebb 
$h_i(i - h_i)$ pár képezhető.

A fej elejének a külsőt kiegészítő belső hozzájárulását egyrészt a lehetséges belső párok $\textbinom{h_i}{2}$ száma, másrészt a 
külső hozzájárulás után megmaradt szabad kapacitás korlátozza. A fej végének kiegészítő hozzájárulását hasonlóképpen becsülhetjük 
a $\min((i - h_i)(i - h_i - 1),H_i - H_{i+1} - X_1/2)$ kifejezéssel. 
\end{proof}

\begin{proof} Legyen $G$ a $b$ sorozatot megvalósító $G$ gráf.Ekkor az $i$ indexhez tartozó fej $H_i$ fokszámösszegét lekötő 
éleinek halmazát öt részhalmazra osztjuk: $(S_{i,1})$ a fej eleje és a farok, a fej vége és a farok közötti, 
$(S_{i,2})$  a fej eleje és vége közötti, $S_{i,3}$ a fej részein belüli élekre, 
$S_{i,4}$ a fej eleje $S_{i,5}$ a fej vége.  
 
A következő halmazt kaptuk $X_{i,1}, \ \ldots, \ X_{i,5}$. \\ 
$X_{i,1}$ legfeljebb a fej elemeinek $H_{h_i}$ összege, legfeljebb a farok elemeinek $T_n - T_{h_i}$ összege, és legfeljebb a 
fej elejéből és a farokból képezhető párok $h_{h_i}(n - h_i)$ szorzata lehet.

$X_{i,1}$ legfeljebb a fej elemeinek az összege $H_{h_i}$, legfeljebb a farok elemeinek az összege $T_n - T_i$,  és legfeljebb a fej elejéből és a farokból képezhető párok, 
\begin{equation}
X_{i,1} \leq \min(H_{h_i},T_n - T_i,h_i(n - i)).\label{eq-HS1}
\end{equation}

A similar train of thought results ?????????
\begin{equation}
X_{i,2} \leq \min(H_i - H_{h_i},T_n - T_i,(i - h_i)(n - i)).\label{eq-HS2}
\end{equation}

$X_{i,3}$ is at most $h_i(i - h_i)$ and at most $H_i$, implying 
\begin{equation}
X_{i,3} \leq \min(h_i(i - h_i),H_i).\label{eq-HS3} 
\end{equation}

$X_{i,4}$ is at most $\binom{h_i}{2}$ and at most $H_{h_i}$, implying 
\begin{equation}
X_{i,4} \leq \min(\binom{h_i}{2},H_{h_i}),\label{eq-HS4} 
\end{equation}
while $X_{i,5}$ is at most $\binom{i - h_i}{2}$ and at most $H_i - H_{h_i}$, implying 
\begin{equation}
X_{i,5} \leq \binom{i - h_i}{2}.\label{eq-HS5} 
\end{equation}
A requirement is also, that the tail can overrun its capacity, that is  
\begin{equation}
X_{i,1} + X_{i,2}  \leq T_i.\label{eq-HS6}
\end{equation}

Summing of \eqref{eq-HS1}, \eqref{eq-HS2}, \eqref{eq-HS3}, \eqref{eq-HS4}, and \eqref{eq-HS5} results 
\begin{equation}
H_i \leq X_{i,1} + X_{i,2} + X_{i,3} + 2X_{i,4} + 2X_{i,5}.\label{eq-HS7}
\end{equation}

Substituting of \eqref{eq-HS1}, \eqref{eq-HS2}, \eqref{eq-HS3}, \eqref{eq-HS4}, and \eqref{eq-HS5} into \eqref{eq-HS7} 
results \eqref{eq-HSa}, while \eqref{eq-HS6} is equivalent with \eqref{eq-HSb}.
\end{proof}

A \ref{lemma-headsplitting}. lemmában javasolt tesztet a következő algoritmus végzi. \\


\textit{Bemenet}: $n $ a csúcsok száma $(n \geq 1)$; $b = (b_1, \ldots, b_n)$: egy $n$-páros sorozat,a \textsc{Binomial-Test} által előtesztelt; \\
$H = (H_1,\ldots,H_n)$, $H_i$ a $b$ sorozat első $i$ elemének összege; \\
$T = (T_1,\ldots,T_n)$, $T_i$ a $b$ sorozat utolsó $n - i$ elemének összege.

\textit{Kimenet}: $L$ logikai változó\\ ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy a teszt \textit{nem tudta eldönteni,} hogy $b$ jó-e). 

\textit{Munkaváltozók}:\\
$h$: a $h_i$ aktuális értéke
$X = (X_1,X_2,X_3,X_4,X_5)$: $X_j$ az $X_{i,j}$ értéke a fej végének ??????????? of the end of the head. 

\medskip
\noindent \textsc{Fejfelező-teszt}$(n,b,H,T,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$ \\
\hspace{-7mm}02              \> $h = \lfloor i/2 \rfloor$ \\
\hspace{-7mm}03              \> $X_1 = \min(H_h,T_n - T_i,h(n - i))$ \\
\hspace{-7mm}04              \> $X_2 = \min(H_i - H_h,T_n - T_i,(i - h)(n - i))$ \\
\hspace{-7mm}05              \> $X_3 = \min(h(i - h)$ \\
\hspace{-7mm}06              \> $X_4 = \binom{h}{2}$ \\
\hspace{-7mm}07              \> $X_5 = \binom{i - h}{2}$ \\
\hspace{-7mm}06              \> \textbf{if} \= $H_i > X_1 + X_2 + X_3 + 2X_4 + 2X_5$ or $X_1 + X_2 > T_i$ \\
\hspace{-7mm}07              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}08              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}09 $L = \textsc{True}$ \\
\hspace{-7mm}10 \textbf{return} $L$
\end{tabbing}

Az algoritmus futási ideje legjobb esetben $\Theta(1),$ legrosszabb esetben $\Theta(n).$

Hasonló módon a farok felezése is további sorozatokat kiszűrését tenné lehetővé, de a szimulációs kísérletek tanúsága 
szerint ez nem csökkentené a várható futási időt.

???? A továbbiakban a futási idő és a hatékonyság együttes optimalizálására törekszünk. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Összetett teszt\label{subsec-osszetettteszt}}
Az \textsc{Összetett-teszt} algoritmus egymás után alkalmazza az eddig ismertetett teszteket a \textsc{Paritás-teszt}, 
\textsc{Binomiális-teszt}, \textsc{Pozitív-teszt}, \textsc{Fejfelező-teszt}, \textsc{Farokfelező-teszt} sorrendben. 

\medskip
\noindent \textsc{Összetett-teszt}$(n,b,E,B,F,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $E = B = \pi = F = T = 0$ \\
\hspace{-7mm}02  \textsc{Binomiális-teszt}$(L,E,B)$ \\
\hspace{-7mm}03  \textsc{Fejfelező-teszt}$(L,F)$ \\
\hspace{-7mm}04 $L = \textsc{True}$ \\  
\hspace{-7mm}05  \textbf{return} $E,B,F,L$ \\
\end{tabbing}

Az érdekesség kedvéért megjegyezzük, hogy ha $k > 0,$ akkor egyik tesztelő algoritmus sem szűrné ki a $(k)$ alakú sorozatokat,  
mivel azonban ezek \textit{nem} szabályos sorozatok, így bemenetként nem fordulhatnak elő.

Ennek az összetett algoritmusnak a futási ideje a legjobb $\Theta(1)$ és a legrosszabb $\Theta(n)$ között változik.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Közelítő algoritmusok hatékonysága és futási ideje\label{sec-kozhat}}
A tesztek elemzésénél a szabályos és páros sorozatokat vettük alapul. A páros sorozatok halmaza a legkisebb olyan 
halmaz, melynek elemszámát explicit képlettel meg tudjuk adni. Az $n - 1 \geq b_i \geq 1$ 
feltételeknek eleget tevő \textit{$n$-korlátos sorozatok} halmazának elemszámát is könnyű megadni, de ezen halmazok elemszáma 
túl gyorsan nő $n$ növekedtével. A szabályos sorozatok elemzéséhez szerencsére nem kell \textit{minden} korlátos 
sorozatot előállítani: elegendő a szabályos sorozatokat előállítani, és a rájuk vonatkozó hatékonysági jellemzőket a 
nekik megfelelő gyakoriságokkal súlyozni. Például egy azonos elemekből álló \textit{homogén} szabályos sorozatnak 
egyetlen korlátos sorozat felel meg, míg a különböző elemekből álló $(n,n - 1,\ldots,1,0)$ \idez{szivárvány} sorozatnak 
$n!$ különböző korlátos sorozat felel meg. 

Az alapvető pontos algoritmusokat kétféle módon próbáljuk gyorsítani (azaz várható futási idejüket csökkenteni). 
Az egyik út, hogy csökkentjük az általuk elvégzendő ellenőrzések számát. A másik út pedig az, hogy gyors (lineáris)   
előtesztekkel igyekszünk a rossz sorozatok jelentős részét kiszűrni, hogy csak a lehetséges bemenetek kis hányadánál legyen 
szükség a viszonylag lassú, de pontos alapalgoritmusokra. A második típusra pedig példa, hogy

Az első típusú javításra példa az Erdős-Gallai algoritmus ugrása. A második típusra pedig példa a Havel-Hakimi algoritmus kiegészítése 
előzetes paritásvizsgálattal, valamint az Erdős-Gallai algoritmus kiegészítése nullamentesítéssel.

A futási idők csökkentése érdekében \textit{minden} algoritmus csak a páros, nullamentes sorozatokat vizsgálta. 

Adott A algoritmusnak az $n$ hosszúságú szabályos sorozatokra vonatkozó hatékonyságát az A algoritmus által kizárt $n$ 
hosszúságú sorozatok és az ugyanolyan hosszúságú szabályos sorozatok számának hányadosával jellemezzük. 
Ezt a hányadost R$_{\textsc{A}}(n)$-nel jelöljük és az A algoritmus $n$ hosszúságú sorozatokra vonatkozó 
\textit{hatékonyságának} nevezzük (lásd a \ref{fig-kozrelativ}. ábrát). 

A következő közelítő algoritmusokat vizsgáljuk:

1) \textsc{Nullamentesítő-teszt}

2) \textsc{Binomiális-teszt}

3) \textsc{Fejfelező-teszt}

A szabályos sorozatoknak aszimptotikusan a fele páros sorozat. Az \ref{fig-parszabarany}. ábra az $n$-szabályos 
sorozatok számát megadó \ref{lemma-rhon}, valamint az $n$-páros sorozatok számát megadó \ref{lemma-epsn} lemmák alapján 
mutatja a konvergencia gyorsaságát (ami a képletek alapján természetes). 



A \ref{fig-sorozatszam}. ábra a \textsc{nullamentes binomiális-teszt}, 
\textsc{nullamentes fejfelező-teszt} és az \textsc{Erdős-Gallai-Gyorsan} programok futási eredményeit tartalmazza. 




\begin{figure}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||r|r|r|r|r||}  \hline \hline
$n$  & $B_z(n)$      &$F_z(n)$           & $G(n)$  & $G(n+1)/G(n)$    \\ \hline \hline
$1$  &$\mathbf{1}$ &$\mathbf{0}$     & $\mathbf{1}$ & $2.000000$\\ \hline
$2$  &$\mathbf{2}$ &$\mathbf{2}$     & $\mathbf{2}$ & $2.000000$\\ \hline
$3$  &$\mathbf{4}$ &$\mathbf{4}$     & $\mathbf{4}$ & $2.750000$      \\ \hline
$4$  &$\mathbf{11}$ &$\mathbf{11}$    & $\mathbf{11}$ & $2.818182$\\ \hline
$5$  &$\mathbf{31}$&$\mathbf{31}$    &$\mathbf{31}$  & $3.290323$     \\ \hline
$6$  &    $103$    &$\mathbf{102}$   &$\mathbf{102}$ & $3.352941$      \\ \hline 
$7$  &    $349$    &$344$            &$\mathbf{342}$ & $3.546784$    \\ \hline 
$8$  &    $1256$   &$1230$           &   $1213$      & $3.595218$\\ \hline 
$9$  &    $4577$   &$4468$           &  $4361$       & $3.672552$ \\ \hline 
$10$ &     $17040$ &$16582$          &$16016$        & $3.705544$\\ \hline 
$11$ &     $63944$ &$62070$          &$59348$        & $3.742620$ \\ \hline 
$12$ &   $242218$  &$234596$         &$222117$       & $3.765200$ \\ \hline 
$13$ & $922369$    &$891852$         & $836315$      & $3.786674$ \\ \hline 
$14$ &$3530534$    &$3409109$        & $3166852$     & $3.802710$ \\ \hline 
$15$ &$13563764$   &$13082900$       &   $12042620$  & $3.817067$ \\ \hline 
$16$ &$52283429$   &$50380684$       &   $45967479$  & $3.828918$ \\ \hline 
$17$ &$202075949$  &$194550002$      & $176005709$   & $3.839418$ \\ \hline 
$18$ &$782879161$  &$753107537$      &$675759564$   & $3.848517$ \\ \hline 
$19$ &$3039168331$ &$2921395019$     & $2600672458$  & $3.856630$ \\ \hline 
$20$ &$11819351967$&$11353359464$    & $10029832754$ & $3.863844$  \\ \hline 
$21$ &             &                 & $38753710486$ & $3.870343$ \\ \hline 
$22$ &             &                 &$149990133774$       & $3.876212$ \\ \hline 
$23$ &             &                 &$581393603996$       & $3.881553$\\ \hline 
$24$ &             &                 &$2 256 710 139 346$  & $3.886431$        \\ \hline 
$25$ &             &                 &$8 770 547 818 956$  & $3.890907$      \\ \hline 
$26$ &             &                 &$34 125 389 919 850$ & $3.895031$\\ \hline 
$27$ &             &                 &$132 919 443 189 544$& $3.897978$        \\ \hline 
$28$ &             &                 &$518 232 001 761 434$& $3.898843$      \\ \hline
$29$ &             &                 &$2 022 337 118 015 338$&           \\ \hline \hline
\end{tabular}
\caption{nullamentes binomiális,nullamentes fejfelező és jó sorozatok száma, valamint a jó sorozatok szomszédos helyeken 
vett értékeinek hányadosa.\label{fig-sorozatszam}}
\end{center}
\end{small}
\end{figure} 


A \ref{fig-kozrelativ}. ábra a nullamentes, binomiális és fejfelező tesztelt sorozatoknak a szabályos sorozatokhoz viszonyított részarányát mutatja be.

\begin{figure}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||c|r|c|c|c|c||}  \hline \hline
$n$ &   $E_z(n)$           & $E_z(n)/R(n)$       & $B_z(n)/R(n)$       &$F_z(n)/R(n)$         &$G(n)/R(n)$ \\ \hline \hline
$1$ &$0$               &$0.000000$         &$1.000000$         &$1.000000$          &$1.000000$  \\ \hline
$2$ &$1$               &$0.333333$         &$0.666667$         &$0.666667$          &$0.666667$ \\ \hline
$3$ &$2$               &$0.300000$         &$0.400000$         &$0.400000$          &$0.400000$ \\ \hline
$4$ &$9$               &$0.257143$         &$0.314286$         &$0.314286$          &$0.314286$ \\ \hline
$5$ &$28$              &$0.230159$         &$0.246032$         &$0.246031$          &$0.246032$ \\ \hline
$6$ &$110$             &$0.238095$         &$0.222943$         &$0.220779$          &$0.220779$ \\ \hline
$7$ &$396$             &$0.231352$         &$0.203380$         &$0.200466$          &$0.199301$ \\ \hline 
$8$ &$1 519$           &$0.236053$         &$0.195183$         &$0.191142$          &$0.188500$ \\ \hline
$9$ &$5 720$           &$0.235335$         &$0.188276$         &$0.183793$          &$0.179391$ \\ \hline
$10$&$21 942$          &$0.237524$         &$0.184460$         &$0.179502$          &$0.173375$ \\ \hline 
$11$&$83 980$          &$0.238098$         &$0.181290$         &$0.175977$          &$0.168260$ \\ \hline
$12$&$323 554$         &$0.239301$         &$0.179145$         &$0.173508$          &$0.164278$ \\ \hline
$13$&$1 248 072$       &$0.240000$         &$0.177368$         &$0.171500$          &$0.160821$ \\ \hline
$14$&$4 829 708$       &$0.240784$         &$0.176014$         &$0.169960$          &$0.157882$ \\ \hline
$15$&$18 721 080$      &$0.241379$         &$0.174884$         &$0.168684$          &$0.155271$ \\ \hline
$16$&$72 714 555$      &$0.241946$         &$0.173965$         &$0.167634$          &$0.152950$ \\ \hline
$17$&$282 861 360$     &$0.242424$         &$0.173188$         &$0.166738$          &$0.150844$ \\ \hline
$18$&$1 101 992 870$   &$0.242860$         &$0.172533$         &$0.165972$          &$0.148926$ \\ \hline
$19$&$4 298 748 300$   &$0.243243$         &$0.171970$         &$0.165306$          &$0.147158$ \\ \hline
$20$&$16 789 046 494$  &$0.243590$         &$0.171486$         &$0.164725$          &$0.145521$ \\ \hline
$21$&                  &                   &                   &                    &$0.143997$ \\ \hline
$22$&                  &                   &                   &                    &$0.142569$ \\ \hline
$23$&                  &                   &                   &                    &$0.141228$ \\ \hline
$24$&                  &                   &                   &                    &$0.139961$ \\ \hline
$25$&                  &                   &                   &                    &$0.138762$ \\ \hline 
$26$&                  &                   &                   &                    &$0.137625$ \\ \hline
$27$&                  &                   &                   &                    &$0.136542$ \\ \hline
$28$&                  &                   &                   &                    &$0.135509$ \\ \hline
$29$&                  &                   &                   &                    &$0.134521$ \\ \hline \hline
\end{tabular}
\caption{A nullamentes páros sorozatok száma,nullamentes páros, binomiális, fejfelező tesztek és jó sorozatok számának részaránya a szabályos sorozatokhoz viszonyítva.\label{fig-kozrelativ}}
\end{center}
\end{small} 
\end{figure}


A \ref{fig-kozido}. ábra a binomiális és a fejfelező közelítő algoritmusok elemenkénti átlagos futási idejét és műveletszámát tartalmazza. 
Az algoritmusok bemenete az összes páros  sorozat volt. 
A mikromásodpercben mért idő és a műveletszám is tartalmazza a sorozatok előállítására fordított időt és műveletszámot is.
  
\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||r|r|r|r|r||}  \hline \hline
$n$  & \textsc{Binomiális}, s & \textsc{Binomiális}, művelet & \textsc{Fejfelező}, s &\textsc{Fejfelező}, művelet   \\
1          &         0          &         14        &         0          &         15        \\
2          &         0          &         41        &         0          &         43        \\
3          &         0          &         180       &         0          &         200      \\
4          &         0          &         716       &         0          &         815      \\
5          &         0          &         2 918     &         0          &         3 321   \\
6          &         0          &         11 918    &         0          &         13 675 \\
7          &         0          &         48 952    &         0          &         56 299 \\
8          &         0          &         201 734   &         0          &         233 182           \\
9          &         0          &         831 374   &         0          &         964 121           \\
10         &         0          &         3 426 742 &         0          &         3 988 542        \\
11         &         0          &     14 107 824    &         0          &         16 469 036      \\
12         &         0          &   58 028 152      &         0          &         67 929 342      \\
13         &         0          &    238 379 872    &         0          &         279 722 127    \\
14         &         0          &    978 194 400    &         1          &         1 150 355 240 \\
15         &         2          &     4 009 507 932 &         3          &         4 724 364 716 \\
16         &         6          & 16 417 793 698    &         13         &         19 379 236 737          \\
17         &         26         & 67 160 771 570    &         51         &         79 402 358 497          \\
18         &        106         & 274 490 902 862   &         196        &         324 997 910 595        \\
19         &       423          & 1 120 923 466 932 &         798        &         1 328 948 863 507     \\
20         &      1 627         & 4 573 895 421 484 &         3 201      &         5 429 385 115 097     \\ \hline \hline
\end{tabular}
\caption{Binomiális teszt és a fejfelező teszt futási ideje másodpercben és műveletszáma.\label{fig-kozido}}
\end{center} 
\end{footnotesize}
\end{figure}


Ha $n = 2,$ akkor (\ref{eq-rhon}) szerint $R(n) = \textbinom{3}{2} = 3$ szabályos sorozat van: $(1,1), \ (1,0)$ és 
$(0,0).$ Ha egy szabályos sorozat elemeinek összege páros, akkor \textit{páros sorozatnak} nevük. Az $n$ 
hosszúságú páros sorozatok számát $\pi(n)$-nel jelöljük. Ezzel a jelöléssel $\pi(2) = 2.$ A \textsc{Binomiális-teszt} 
által elfogadott, $n$ hosszúságú sorozatok számát $B(n)$-nel jelölve $B(2) = 2.$ Az $n$ hosszúságú 
helyreállítható sorozatok számát jelöljük $G(n)$-nel. Ekkor $G(2) = 2$ és a \textsc{Binomiális-teszt} 
hibája (hatékonysága) $R_{\textsc{BT}}(2) = 2/2 = 1.$

Ha $n = 3,$ akkor a szabályos sorozatok száma $R(3) = 10.$ Ezek közül a (2,2,2), (2,2,0), (2,1,1), (2,0,0), (1,1,0) és 
(0,0,0) páros, azaz $E(3) = 6.$ Ezek közül a \textsc{Binomiális-teszt} kizárja a (2,2,0) és (2,0,0) sorozatokat, így 
$B(3) = 4.$ A megmaradt 4 sorozat jó, így $F(3) = T(3) = G(3) = 4.$

Ha $n = 4,$ akkor a szabályos sorozatok száma $R(4) = 35.$ Ezek közül 19 a páros, és a következő 11 jó: 
(3,3,3,3), (3,3,2,2), (3,2,2,1), (3,1,1,1,), (2,2,2,2), (2,2,2,0), (2,2,1,1), (2,1,1,0), (1,1,1,1), (1,1,0,0) és (0,0,0,0). 
A 19 páros sorozat közül \textsc{Binomiális-teszt} is kizárja azt a nyolc sorozatot, amelyeket az \textsc{Erdős-Gallai} 
kizárna, így $B(4) = G(4) = F(4) = G(4) = 11.$ 

A $R(5) = 126$ szabályos sorozat közül $E(5) = 66$ a páros, ezek között pedig $B(5) = 31$ 
a binomiális. Ezek a sorozatok mind jók, azaz $F(5) = T(5) = G(5) = 31.$ 

A $R(6) = 462$ szabályos sorozat közül $E(6) = 236$ a páros, amelyek között $B(6) = 103$ 
binomiális sorozat van. \textsc{Binomiális-teszt} a 102 jó sorozat mellett az (5,5,3,3,3,1) rossz sorozatot is elfogadja. 
Ezek szerint a legfeljebb 5 hosszúságú sorozatokra nézve a \textsc{Binomiális-teszt} hibátlanul kiszűri a nem jó 
sorozatokat, a 6 hosszú sorozatokra azonban már csak közelítő algoritmus. 
A \textsc{Fejfelező-teszt} ezzel a sorozattal is megbirkózik, ezért $F(6) = T(6) = G(6) = 102.$


???????????????????????????????????????Eddig jó  
A $R(7) = 1716$ szabályos sorozat között $E(6) = 868$ a páros, melyek közül $B(7) = 376$ a binomiális. 
A binomiális sorozatok között még 34 rossz van, melyek közül a \textsc{Pozitív-teszt} a 27 jó sorozat mellett a következő 
7 rosszat is elfogadja: $(6,6,6,4,4,4,2),$ $(6,6,5,4,4,4,1),$ $(6,6,4,4,4,3,1),$ $(6,6,4,3,3,3,1),$ $(6,6,3,3,3,2,1),$ 
$(6,5,3,3,3,1,1),$ $(5,5,3,3,3,1,0).$ A következő \textsc{Fejfelező-teszt} ezek közül a $(6,6,4,3,3,3,1)$ kivételével 
mindet kiszűri, így $F(7) = 343.$ A következő \textsc{Farokfelező-teszt} $i = 4$ mellett legfeljebb $8 + 2$ fokot 
tud lekötni a fej eleje és a farok részei között, legfeljebb további $4 + 0$ fokot a fej vége és a farok részei között, 
legfeljebb további 8 fokot a fej két része között, és két fokot a fej elején belül. Ez azonban összesen csak 
$10 + 4 + 8 + 2 = 24$ fok, ami kevesebb a sorozat $H_7 = 26$ összfokszámánál. Tehát $T(7) = G(7) = 342.$

A \ref{fig-sorozatszam}. ábrán minden sorban az első pontos értéket félkövéren írtuk. Eszerint $n \leq 4$ esetén 
$B(n) = G(n),$ azaz a \textsc{Binomiális-teszt} ugyanannyi 
sorozatot fogad el, mint a pontos algoritmusok. $n > 5$ esetén egyre nő a \textsc{Binomiális-teszt} hibája: $n = 6$ 
esetén még csak egyetlen páros sorozatról nem ismeri fel, hogy rossz, $n = 7$ esetén már ötször hibázik.

\textsc{Pozitív-teszt} $n = 5$-ig hibátlan, a \textsc{Fejfelező-teszt} $n = 6$-ig, a \textsc{Farokfelező-teszt} pedig 
$n = 7$-ig. 


A \ref{fig-kozrelativ}. ábrán $R(n)$ értéke $n = 24$-ig az EIS A001700 sorozata \cite{Sloane2011A001700}, 
$E(n)$ értéke $n = 23$-ig az EIS A005654 sorozata \cite{Sloane2011A005654}, $G(n)$ értéke pedig $n = 23$-ig 
az EIC A0004251-es sorozata \cite{Sloane2011A004251}. A többi értéket mi határoztuk meg: sem R(25),..., R(38)
sem E(24),...,E(38), sem a $B_z(n)$, $\pi(n),$ $G(n)$ és $(T(n)$ értékek nem szerepelnek az EIS-ben. 

Ebben a cikkben első sorban a soros algoritmusokkal kapott eredményekről számoltunk be. 

A témakörben vannak párhuzamos eredmények is \cite{PecsySz2000,Siklosi2001,Soroker1990}. Saját párhuzamos eredményeinket a 
\ref{sec-grafikusszam}. részben ismertetjük. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Pontos algoritmusok futási ideje\label{sec-pontosido}}

A pontos algoritmusok által elvégzett műveleteinek a számát $n$ függvényében alábbi 
\ref{fig-pontosido}. ábra tartalmazza. Az algoritmusok csak a páros, nullamentes sorozatokat vizsgálták. 
A művelet szám nem tartalmazza a sorozatok előállításának a költségét. 


\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||c|c|c|c|c|c|||}  \hline \hline
$n$  &      HH  &  HHE    &   EG      & EGU   &  EGL        \\ \hline \hline
 1	 &	    10	 &	15	    &   87	   &        -     &  -	\\
 2	 &	    40	 &	61	    &  119	   &        12    &  37	\\
 3	 &	   231	 &	236	    &  267	   &       116    & 148	\\
 4	 &	1 170	 &	1 052   &  946	   &       551    & 585	\\
 5	 &	5 969	 &	4 477   & 4 000	   &     2 677    & 2 339	\\
 6	 &	31 121	 &	20 153  & 18 206	   &    12 068    & 9 539	\\
 7	 &	157 345	 &	88 548  & 82 154	   &    54 184    & 38 984	\\
 8	 &	784 341	 &  393 361   & 372 363   &    238 813   & 160 126	\\
 9	 &3 628 914  & 1 726 484 &1 666 167  &  1 666 167   &  656 575	\\
10	 &17 345 700 &7 564 112  &7 418 447  & 4 552 276    & 2 692 240	\\
11	 &80 815 538 &32 895 244 &32 737 155 & 19 680 986   &  11 018 710	\\
12	&385 546 527 &142 460 352&143 621 072&84 608 529   &  45 049 862	\\
13	&1 740 003 588&613 739 913&626 050 861& 362 141 061&  183 917 288	\\
14	&8 066 861 973&	2 633 446 908&2 715 026 827&1 543 745 902 &750 029 671	\\
15	&36 630 285 216&11 254 655 388&11 717 017 238&6 557 902 712 & 3 055 289 271	\\ \hline \hline
\end{tabular}
\caption{Pontos algoritmusok elvégzett műveleteinek a száma.\label{fig-pontosido}}
\end{center} 
\end{footnotesize}
\end{figure}

A következő pontos algoritmusokat vizsgáljuk:

1) HH: Rendező Havel-Hakimi algoritmus (HH).

2) HHE: Eltoló Havel-Hakimi algoritmus (HHE).

3) EG: Erdős-Gallai algoritmus (EG).

4) EGU: Erdős-Gallai algoritmus ugrásokkal (EGU).

5) EGL: Erdős-Gallai algoritmus ugrásokkal lineárisan (EGL).
  
A pontos algoritmusok műveletszámát $n$ függvényében a \ref{fig-pontosido}. ábra tartalmazza. 


Az \textsc{EG-Lineárisan-Mind} algoritmus teljes és az elemenkénti futási időit tartalmazza a \ref{fig-EG-Lineárisan}. ábra. 

\begin{figure}[!t]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||r|r|r|r|r|r||}  \hline \hline
$n$  &  $E(n)$  & $T(n)$, s  & $Op(n)$ & $T(n)/E(n)/n,$ s & $Op(n)/E(n)/n$       \\ \hline \hline   
2    &     2    &      0      &     37    &         0         &         9.25000000000     \\
3    &     6    &      0      &    148    &         0         &         8.22222222222    \\
4    &    19    &      0      &    585    &         0         &         7.69736842105    \\
5    &    66    &      0      &  2 339   &         0          &         7.08787878788   \\
6    &   236    &      0      &  9 539   &         0          &         6.73658192090   \\
7    &   868    &      0      & 38 984    &         0         &         6.41606319947    \\
8    &  3 235   &      0      &160 126    &         0         &         6.18724884080    \\
9    &   12 190 &      0      & 656 575   &         0         &         5.98464132714    \\
10   &   46 252 &      0      & 2 692 240 &         0         &         5.82080774885     \\
11   &  176 484 &      0      &11 018 710 &         0         &         5.67587378511  \\
12   &  676 270 &      0      &45 049 862 &         0         &         5.55126675243   \\
13   &2 600 612 &      0      &183 917 288&         0         &         5.44005937537    \\
14   &10 030 008&      1      &750 029 671&0.000000007121487  &         5.34132654018    \\
15   &38 781 096&      5      &3 055 289 271&0.000000008595253&         5.25219687963   \\
16   &150 273 315&    23      &12 434 367 770&0.000000009565903&        5.17156346504    \\
17   &583 407 990&    79      &50 561 399 261&0.000000007965367&        5.09797604337    \\
18   &2 268 795 980&  297     &205 439 740 365&0.00000000727258&        5.03056202928    \\ \hline \hline
\end{tabular}
\caption{Az \textsc{EG-Lineárisan} algoritmus futási ideje műveletszámban, másodpercben kifejezve.\label{fig-EG-Lineárisan}}
\end{center} 
\end{footnotesize}
\end{figure}



A \ref{fig-EG-Lineárisan-menetek}. ábra azt mutatja, hányszor  
van az \textsc{Erdős-Gallai-Lineárisan} algoritmusnak $1, \ldots, n -1$ menetre szüksége, hogy a rossz sorozatokat kiszűrje. 

\begin{figure}[!ht]
\begin{footnotesize}
 $n$      1       2       3       4       5       6       7       8       9      10      11      12      13      14      15 \\
 $3$      2       0       0 \\
 $4$     8       0       0       0 \\
 $5$    33       2       0       0       0 \\
 $6$   122      12       0       0       0       0 \\
 $7$  459      65       2       0       0       0       0 \\
 $8$   1709     289      24       0       0       0       0       0 \\
 $9$   6421    1228     176       4       0       0       0       0       0 \\
  $10$ 24205    4951    1013      67       0       0       0       0       0       0 \\
 $11$  91786   19603    5126     610      11       0       0       0       0       0       0 \\
 $12$ 349502   76414   23755    4274     208       0       0       0       0       0       0       0 \\
 $13$ 1336491  296036  104171   25293    2277      29       0       0       0       0       0       0       0 \\
 $14$ 5128246 1142470  439155  133946   18673     666       0       0       0       0       0       0       0       0 \\
$15$ 19739076 4404813 1803496  655291  127116    8603      81       0       0       0       0       0       0       0       0 \\
Ezek az UGRÓ LEG adatai
\caption{Az \textsc{EG-Lineárisan} elutasítás előtti meneteinek száma.\label{fig-EG-Lineárisan-menetek}}
\end{footnotesize}
\end{figure}


Az \ref{fig-EGrounds-av}. ábrán az látható, hogy az \textsc{EG-Lineárisan} ciklusmagja átlagosan 
(gyakoriságokkal súlyozva) hányszor futott le, ha csak a rossz sorozatokat vesszük figyelembe, illetve a ha minden 
sorozatot figyelembe veszünk (mindkét esetben csak a páros, nullamentes sorozatokat vettük figyelembe). 


\begin{figure}[!ht]
\begin{footnotesize}
n=3	11 /6 /3 = 0.611111 \\
n=4	47 /19 /4 = 0.618421 \\
n=5	192 /66 /5 = 0.581818 \\
n=6	792 /236 /6 = 0.559322 \\
n=7	3229 /868 /7 = 0.531435 \\
n=8	13268 /3235 /8 = 0.512674 \\
n=9	54244 /12190 /9 = 0.494431 \\
n=10	222057 /46252 /10 = 0.480102 \\
n=11	906558 /176484 /11 = 0.466979 \\
n=12	3698529 /676270 /12 = 0.455751 \\
n=13	15063277 /2600612 /13 = 0.445554 \\
n=14	61286926 /10030008 /14 = 0.436454 \\
n=15	249056158 /38781096 /15 = 0.428140 \\
n=16	1011175412 /150273315 /16 = 0.420557 \\
n=17	4101727713 /583407990 /17 = 0.413567 \\
n=18	16625570580 /2268795980 /18 = 0.407107 
\caption{Az \textsc{EG-Lineárisan} menetszámai súlyozott átlagának $n$-ed része, ha a jó sorozatokat is figyelembe vesszük, 
illetve ha nem.\label{fig-EGrounds-av}}
\end{footnotesize}
\end{figure}

A \ref{fig-EGb1}. ábra pedig a jó sorozatok kezdő elem szerinti megoszlását mutatja be. Ezek az adatok segítenek a $G(n)$ 
számítását végző \textsc{Erdős-Gallai-Gyorsan} program párhuzamos megvalósításánál (a számítások több részre osztásában).




\begin{figure}[!t]
\begin{scriptsize}
\begin{center}
\begin{tabular}{||r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r||}  \hline \hline
$n/b_1$  & $0$   &$1$  & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ &$9$ & $10$ & $11$   \\ \hline \hline
$1$      &1      &     &     &     &     &     &     &     &     &    &      &           \\ \hline
$2$      &1      &   1 &     &     &     &     &     &     &     &     &     &          \\ \hline
$3$      &   1   &   1 &  2  &     &     &     &     &     &     &     &     &  \\ \hline
$4$      &   1   &   1 &  4  &  4  &     &     &     &     &     &     &     &   \\ \hline
$5$      &   1   &   2 &  7  &10   &  11 &     &     &     &     &     &     &    \\ \hline
$6$      &   1   &   3 &10   &  22 &  35 & 31  &     &     &     &     &     &    \\ \hline
$7$      &   1   &   3 &14   &  34 &  78 & 110 & 102 &     &     &     &     &    \\ \hline
$8$      &   1   &   4 & 18  &  54 & 138 & 267 & 389 & 342 &     &     &     &    \\ \hline
$9$      &   1   &   4 & 23  &  74 & 223 & 503 & 968 & 1352& 1213&     &     &     \\ \hline
$10$     &   1   &   5 & 28  & 104 & 333 & 866 & 1927& 3496& 4895&4361 &     &    \\ \hline
$11$     &   1   &   5 & 34  &134  &479  &1356 &3471 &7221 &12892&17793&16016&        \\ \hline 
$12$     &   1   &   6 & 40  &176  &661  &2049 &5591 &13270&27449&47757&65769&59348     \\ \hline \hline
\end{tabular}
\caption{A jó sorozatok $b_1$ szerinti eloszlása $n = 1, \ \ldots, \ 12.$\label{fig-EGb1}}
\end{center} 
\end{scriptsize}
\end{figure}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Grafikus sorozatok száma\label{sec-grafikusszam}}
A \ref{fig-sorozatszam}. ábra $1$-től $29$ csúcsig tartalmazza a grafikus sorozatok számát. A táblázat grafikus sorozatok oszlopa úgy készült, hogy 
párhuzamosítottuk az \textsc{Erdős-Gallai-Gyorsan} algoritmust. Mivel viszonylag sok processzor vett részt a számolásban, 
viszont bizonytalan volt, hogy az egyes processzorok meddig vehetnek részt a számolásban, a feladatot \textit{szeleteknek} 
nevezett kisebb részekre bontottuk. Célszerű volt, hogy a szeletek feldolgozása hasonló ideig tartson. 

Mivel a futási idő csökkentése érdekében az \textsc{Erdős-Gallai-Gyorsan} algoritmus csak nullamentes sorozatokat állít elő és 
tesztel, a szeletekre bontás alapja a \ref{lemma-rhon}. lemma alábbi következménye.

\begin{corollary} Ha\label{corollary-rho1} Ha $m$ és $u$ pozitív egész számok, akkor az $(1,u,m)$-szabályos sorozatok 
$R(1,u,m)$ száma
\begin{equation}
R(1,u,m) = \binom{m + u - 1}{m}.\label{eq-rhon}
\end{equation}
\end{corollary} 

\begin{proof} A \ref{lemma-rhon}. lemmában alkalmazzuk az $l = 1$ helyettesítést. 
\end{proof}

Feltételezzük, hogy az $n$-szabályos nullamentes sorozatok halmazának szeletekre való felbontásánál az egyes szeletek 
futási ideje arányos a hozzájuk tartozó $R(1,u,m)$-szabályos sorozatok számával.

\bigskip
\noindent \small \textbf{Köszönetnyilvánítás.} A szerzők köszönik Kása Zoltán egyetemi tanárnak 
(Sapientia Erdélyi Magyar Tudományegyetem) a kézirat javítására vonatkozó javaslatait, 
Mányoki Ádámnak (TFM World Kereskedelmi és Szolgáltató Kft.) és Sándor Antal 
programtervező matematikusnak és munkatársainak pedig a programok nagy processzorigényű futtatásához 
nyújtott segítséget. A kutatás az Európai Unió támogatásával, az Európai Szociális Alap 
társfinanszírozásával valósul meg (a támogatás száma TÁMOP 4.2.1/B-09/1/KMR-2010-0003). 


\begin{thebibliography}{x}
\large
\vspace{-2mm}

\begin{footnotesize}


\bibitem{AnholzerBBK2011} 
\textsc{Anholcer, M., Babiy, V.,  Bozóki, S., Koczkodaj, W. W.:}
\textit{A simplified implementation of the least squares solution for pairwise comparisons matrices.} 
CEJOR Cent. Eur. J. Oper. Res. \textbf{19,} (4) (2011) 439--444. 

\bibitem{ArikatiM1996}  
\textsc{Arikati, S. R.,Maheshwari, A.:} 
\textit{Realizing degree sequences in parallel.} 
SIAM J. Discrete Math. \textbf{9,} (2) (1996) 317--338.

\bibitem{Ascher1987} 
\textsc{Ascher, M.:} 
\textit{Mu torere: an analysis of a Maori game.} 
Math. Mag. \textbf{60(2),} (1987) 90--100.

\bibitem{AvisF1996} 
\textsc{Avis, D., Fukuda, K.:} 
\textit{Reverse search for enumeration.}  
Discrete Appl. Math. \textbf{  2,} (1993) 21--46. 

\bibitem{BarnesS1995} 
\textsc{Barnes, T. M., Savage, C. D.:} 
\textit{A recurrence for counting graphical partitions.} 
Electron. J. Combin. \textbf{2,} (1995) R11, 10 pp.

\bibitem{BarnesS1997}  
\textsc{Barnes, T. M., Savage, C. D.:} 
\textit{Efficient generation of graphical partitions.} 
Discrete Appl. Math. \textbf{78(1--3),} (1997) 17--26.

\bibitem{BeasleyBR2009} 
\textsc{Beasley, L. B., Brown D. E., Reid, K. B.}: 
\textit{Extending partial tournaments.} 
Math. Comput. Modelling \textbf{50(1),} (2009) 287--291.

\bibitem{BeregI2008} 
\textsc{Bereg S., Ito, H.:} 
\textit{Transforming graphs with the same degree sequence.}
In: (ed. by H. Ito et al.) 
The Kyoto Int. Conf. on Computational Geometry and Graph Theory, 
LNCS \textbf{4535.} Springer-Verlag, Berlin, Heidelberg. 2008. pp. 25--32.

\bibitem{Bodei2010} 
\textsc{Bödei, N.:} 
\textit{Degree sequences of graphs}
(Hungarian), Mathematical master thesis (supervisor A. Frank),  
Dept. of Operation Research of E\"otv\"os Lor\'and University, Budapest, 2010, 43 oldal.

\bibitem{BozokiFP2011} 
\textsc{Bozóki, S., Fülöp, J., Poesz, A.:} 
\textit{On pairwise comparison matrices that can be made consistent by the modification of a few elements.} 
CEJOR Cent. Eur. J. Oper. Res. \textbf{19,} (2011) 157--175.

\bibitem{BozokiFR2010} 
\textsc{Bozóki S., Fülöp J., Rónyai, L.:}  
\textit{On optimal completion of incomplete pairwise comparison matrices.}   
Math. Comput. Modelling \textbf{52,} (2010) 318--333.

\bibitem{BrualdiK2009} 
\textsc{Brualdi, A. R., Kiernan K.:} 
\textit{Landau's and {R}ado's theorems and partial tournaments.}   
Electron. J. Combin. \textbf{16(\#N2),} (2009) (6 pp).

\bibitem{Burns2007} 
\textsc{Burns, J. M.:} 
\textit{The number of \href{http://dspace.mit.edu/bitstream/handle/1721.1/38882/166267576.pdf?sequence=1}{degree sequences}.} 
PhD Dissertation, \href{http://web.mit.edu/}{MIT}, 2007.

\bibitem{BuschCJ2010} 
\textsc{Busch A. N., Chen G., Jacobson M. S.:}   
\textit{Transitive partitions in realizations of tournament score sequences.} 
J. Graph Theory \textbf{64(1),} (2010), 52--62.

\bibitem{Choudum1986} 
\textsc{Choudum, S. A.:} 
\textit{A simple proof of the Erd\H os-Gallai theorem on graph sequences}. 
Bull. Austral. Math. Soc. \textbf{33,} (1986) 67--70.

\bibitem{CooperL2011} 
\textsc{Cooper, J., Lu, L.:} 
\textit{Graphs with asymptotically invariant degree sequences under restriction.} 
Internet Mathematics \textbf{7,} (1) 67--80.

\bibitem{CormenLRS2009} \textsc{Cormen, T. H., Leiserson, Ch. E., Rivest, R. L., Stein, C.:} \textit{Introduction to Algorithms.} 
Third edition, The MIT Press/McGraw Hill, Cambridge/New York, 2009. Magyarul: \textit{Algoritmusok.} 
Műszaki Könyvkiadó, Budapest, 2003.

\bibitem{Chungphaisan1974} \textsc{Chungphaisan, V.}: \textit{Conditions for sequences to be $r$-graphical}.  
Discrete Math. \textbf{7,} (1974) 31--39. 

\bibitem{DeAgostinoP1990} \textsc{De Agostino, S. , Petreschi, R.:}
\textit{Parallel recognition algorithms for graphs with restricted neighbourhoods.} \href{http://www.worldscinet.com/ijfcs/ijfcs.shtml}{\textit{Internat. J.}} 
\textit{Found. Comput. Sci.} \textbf{1,} (2) (1990) 123--130. 


\bibitem{delGenioKTB2010} \textsc{Del Genio, C. I., Kim, H., Toroczkai, Z., Bassler, K. E.:}   
\textit{Efficient and exact sampling of simple graphs with given arbitrary degree sequence.}  
PLoS ONE \textbf{5(4)}, e10012 (2010).

\bibitem{DessmarkLG1994} \textsc{Dessmark, A., Lingas, A., Garrido, O.:}
\textit{On parallel complexity of maximum $f$-matching and the degree sequence problem.} 
Mathematical Foundations of Computer Science 1994 (Ko\u{s}ice, 1994), LNCS \textbf{841,} Springer, Berlin, 1994, 316--325.

\bibitem{ErdosG1960} \textsc{Erd\H os, P., Gallai, T.:} \textit{Gráfok előírt fokú pontokkal.} 
Mat. Lapok \textbf{11,} (1960) 264--274.

\bibitem{ErdosMT2010} \textsc{Erd\H os, P. L., Miklós, I., Toroczkai, Z.:}   
\textit{A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs.} 
Electron. J. Combin. \textbf{17(1),} (2010) R66, 10 pp.

\bibitem{ErdosR1997} \textsc{Erdős, P., Richmond L. B.:} \textit{On graphical partitions.} 
Combinatorica \textbf{13(1),} (1993) 57--63.

\bibitem{Frank2011} \textsc{Frank, A.}: \textit{Connections in Combinatorial Optimization.}   
Oxford University Press, Oxford, 2011.

\bibitem{FrankSS2002} \textsc{Frank, D. A., Savage, C. D., Sellers, J. A.:} \textit{On the number of graphical forest partitions.} 
Ars Combin. \textbf{65,} (2002) 33--37. 

\bibitem{Hakimi1962} \textsc{Hakimi, S. L.:} \textit{On the realizability of a set of integers as degrees of the vertices 
of a simple graph.} J. SIAM Appl. Math. \textbf{10,} (1962) 496--506. 

\bibitem{Hakimi1963} \textsc{Hakimi, S. L.}: \textit{On realizability of a set of integers as degrees of the vertices 
of a linear graph {I}{I}. Uniqueness.} SIAM J. Appl. Math., \textbf{11(1),} (1963) 135--147.

\bibitem{Hakimi1965} \textsc{Hakimi, S. L.:} \textit{On the degrees of the vertices of a graph.}
F. Franklin Institute, \textbf{279,} (4) (1965) 290--308.

\bibitem{Havel1955} \textsc{Havel, V.:} \textit{A remark on the existence of finite graphs.} (cseh)
\u{C}asopis P\u{e}st. Mat. \textbf{80,} (1955), 477--480. 

\bibitem{HellK2009} \textsc{Hell, P., Kirkpatrick, D.:} \textit{Linear-time certifying algorithms for near-graphical sequences.} 
Discrete Math. \textbf{309(18)}, (2009) 5703--5713.

\bibitem{Ivanyi2001} \textsc{Iványi, A.:} \textit{Pontsorozatok ellenőrzése.} In: (szerk. Tóth B.) 
\textit{XXV. Magyar Operációkutatási Konferencia} (Debrecen, 2001. október 17--20), 53--53.

\bibitem{Ivanyi2009} \textsc{Iványi, A.:} \textit{Reconstruction of complete interval tournaments.} 
Acta Univ. Sapientiae, Inform., \textbf{1(1),} (2009) 71-88.

\bibitem{Ivanyi2010} \textsc{Iványi, A.}: \textit{Reconstruction of complete interval tournaments. II.} 
Acta Univ. Sapientiae,  Math., \textbf{2(1),} (2010) 47--71.

\bibitem{Ivanyi2011Egres} 
\textsc{Iványi, A.}: \textit{Deciding the validity of the score sequence of a soccer tournament.} 
In (ed. A. Frank): Open problems of the Egerváry Research Group, Budapest, 2011. 

\bibitem{Ivanyi2011Kyoto} \textsc{Iványi A.}: \textit{Directed graphs with prescribed score sequences.} 
In (ed. S. Iwata): The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Applications 
(Kyoto, May 31 - June 3, 2011), 114--123.

\bibitem{IvanyiLS2011} \textsc{Iványi, A., Lucz, L., Móri F. T., Sótér, P.}: 
\textit{On Erdős-Gallai and Havel-Hakimi algorithms.} Acta Univ. Sapientiae, Inform. \textbf{3(2)} 230--268.

\bibitem{IvanyiK2011} \textsc{Iványi A., Kátai, I.}: \textit{Testing of random matrices,} 
Acta Univ. Sapientiae,  Math., \textbf{3(1),} (2011) 99--126.

\bibitem{IvanyiMN2011} 
\textsc{Iványi, A., Madarász, J., Németh, Zs.}: \textit{Algoritmusok hatékonyságának oktatása.} In (szerk. Cser László 
és Herdon Miklós) \textit{Az Informatika'2011 előadásainak kivonatai} (Debrecen, 2011. augusztus 24--26). 
Debreceni Egyetem, Debrecen, 2011. 
 
\bibitem{IvanyiP2011} \textsc{Iványi, A., Pirzada, S.}: \textit{Comparison based ranking.} 
In (ed. A. Iványi): Algorithms of Informatics, Vol. 3. AnTonCom, Budapest 2011, 1262--1311.  

\bibitem{IvanyiP2011Opkut} \textsc{Iványi, A., Pirzada, S.}: \textit{Hiperversenyek helyreállítása.} 
In: \textit{XXIX. Magyar Operációkutatási Konferencia} (Balatonőszöd, 2001. október 17--20), 53--53.

\bibitem{Jarai2005} \textsc{J\'arai, A.:}\textit{Introduction to Mathematics} 
(Hungarian). ELTE E\"otv\"os Kiad\'o, Budapest, 2005. 

\bibitem{Katai2010} \textsc{Kátai, I.:} \textit{Szóbeli közlés.} Budapest, 2010.

\bibitem{KayibiKPI2011} \textsc{Kayibi K., Khan M. A., Pirzada S., Iványi A.:} 
\textit{Random sampling of minimally cyclic digraphs with given imbalance sequence.} 
Acta Univ. Sapientiae, Math. (submitted).

\bibitem{KemnitzD1997} \textsc{Kemnitz, A., Dolff, S.:} \textit{Score sequences of multitournaments,} 
Congr. Num., \textbf{127,} (1997) 85--95.


\bibitem{Keri2011}
\textsc{{K\'eri}, G.:}
\textit{On qualitatively consistent, transitive and contradictory judgment matrices emerging from 
multiattribute decision procedures.}
CEJOR Cent. Eur. J. Oper. Res. \textbf{19,} (2) (2011) 215--224. 

\bibitem{KernP2001}  
\textsc{Kern, K., Paulusma, D.:}
\textit{The new FIFA rules are hard: complexity aspects of sport competitions.}
Discrete Appl. Math. \textbf{108,} (3) (2001) 317--323.

\bibitem{KernP2004} 
\textsc{ Kern, K., Paulusma, D.:}
\textit{The computational complexity of the elimination problem in generalized sports competitions.}
Discrete Optimization \textbf{1} (2004) 205--214.


\bibitem{KimTMESz2009} 
\textsc{Kim, H., Toroczkai, Z., Miklós, I., Erdős, P. L., Székely, L. A.:}  
\textit{Degree-based graph construction.}
J. Physics: Math. Theor. A \textbf{42(39),} (2009) 392--401.

\bibitem{KleitmanW1973} 
\textsc{Kleitman, D. J., Wang, D. L.:} 
\textit{Algorithms for constructing graphs and digraphs with given valencies and factors.}
Discrete Math. \textbf{6} (1973) 79--88.

\bibitem{KleitmanW1981} 
\textsc{Kleitman, D. J., Winston K. J.:}  
\textit{Forests and score vectors.} 
Combinatorica \textbf{1(1),} (1981) 49--54.

\bibitem{Knuth2011} 
\textsc{Knuth, D. E.:} 
\textit{The Art of Computer Programming. Volume 4A, Combinatorial Algorithms.} 
Addison--Wesley, Upper Saddle River, 2011.

\bibitem{Kohnert2004} 
\textsc{Kohnert, A.:} 
\textit{Dominance order and graphical partitions.} 
Elec. J. Comb. \textbf{11(1),} (2004) No. 4. 17 pp.

\bibitem{KovacsP2002} 
\textsc{Kovács, G. Zs., Pataki, N.:} 
\textit{Rangsorolási algoritmusok elemzése.} 
TDK dolgozat. ELTE TTK, Budapest, 2002. 39 oldal. 

\bibitem{LaMar2010} 
\textsc{LaMar, M. D.} 
\textit{Algorithms for realizing degree sequences of directed graphs.} 
arXiv-0906:0343ve [math.CO], 7 June 2010.

\bibitem{Landau1953} 
\textsc{Landau, H. G.:} 
\textit{On dominance relations and the structure of animal societies. III. The condition for a score sequence.} 
Bull. Math. Biophys. \textbf{15,} (1953) 143--148. 

\bibitem{LiljerosEASA2001} 
\textsc{Liljeros, F., Edling, C. R., Amaral, L., Stanley, H., Áberg, Y.:}  
\textit{The web of human sexual contacts}. 
Nature \textbf{411,} (2001) 907--908.

\bibitem{Lovasz2007} 
\textsc{Lovász, L.:}  
\textit{Combinatorial Problems and Exercises} 
(corrected version of the second edition).  AMS Chelsea Publishing, Boston, 2007. 
Magyarul: \textit{Kombinatorikai problémák és feladatok.} Typotex, Budapest, 1999.
 
\bibitem{LuczISP2012MaCS} 
\textsc{Lucz, L., Iv\'anyi, A., S\'ot\'er, P., Pirzada, S.:} 
\textit{Testing and enumeration of football sequences.}  
Abstracts of MaCS 2012, ed. by Z. \href{http://people.inf.elte.hu/csz/}{Cs\"ornyei} (Si\'ofok, February 9--12). 
  
 
 
\bibitem{Meierling2009} 
\textsc{Meierling, D., Volkmann, L.:} 
\textit{A remark on degree sequences of multigraphs.} 
Math. Methods Oper. Res. \textbf{69(2),} (2009) 369--374. 

\bibitem{MetropolisN1980} 
\textsc{Metropolis, N., Stein, P. R.:} 
\textit{The enumeration of graphical partitions.} 
European J. Comb. \textbf{1(2),} (1980) 139--153.


\bibitem{Miklos2009} 
\textsc{Mikl\'os, I.:} 
\textit{Graphs with prescribed degree sequences.} 
Lecture in \href{http://www.renyi.hu/}{Alfr\'ed R\'enyi} Institute of Mathematics, 16 November 2009. 



\bibitem{MiklosES2011} 
\textsc{Miklós, I., Erdős, P. L., Soukup, L.:}     
\textit{A remark on degree sequences of multigraphs.} 
(2011) (benyújtva). 

\bibitem{Moon1968} 
\textsc{Moon, J. W.:} 
\textit{Topics on Tournaments.} 
Holt, Rinehart, and Winston, New York, 1968.

\bibitem{Mori2011} 
\textsc{Móri, T.:} 
\textit{Szóbeli közlés.}
Budapest, 2011.

\bibitem{NarayanaB1964} \textsc{Narayana, T. V., Bent, D. H.:} 
\textit{Computation of the number of score sequences in round-robin tournaments.} 
Canad. Math. Bull. \textbf{7,} (1) (1964) 133--136.

\bibitem{NewmanB2006} \textsc{Newman, M. E. J., Barabási, A. L.:} 
\textit{The Structure and Dynamics of Networks.}
 Princeton University Press, Princeton, NJ. 2006. 

\bibitem{Ozkan2011} \textsc{\"Ozkan S.}: \textit{Generalization of the Erd\H os-Gallai inequality}. Ars Combin.  
\textbf{98,} (2011) 295--302.
 
\bibitem{PecsySz2000} \textsc{Pécsy G., Szűcs, L.:} \textit{Parallel verification and enumeration of tournaments.}  
Stud. Univ. Babe\c s-Bolyai, Inform. \textbf{45(2),} (200) 11--26.

\bibitem{Pirzada2011} \textsc{Pirzada, S.:} \textit{Graph Theory.} Orient Blackswan, 2011, to appear.

\bibitem{PirzadaAK2011} \textsc{Pirzada, S., Al-Assaf, A. M., Kayibi, K. K.:} 
\textit{On imbalances in oriented multipartite graphs.} Acta Univ. Sapientiae,  Math., \textbf{3(1),} (2011) 34--42.

\bibitem{PirzadaI2011} 
\textsc{Pirzada, S., Iványi, A.:} \textit{Imbalances in digraphs.} 
In: Abstracts of Joint Conference on Mathematics and Computer Science (Siófok, February 2012), benyújtva.

\bibitem{PirzadaIK2011} \textsc{Pirzada, S., Iványi, A., Khan, M. A.:} \textit{Score sets and kings.} In (ed. A. Iványi): 
Algorithms of Informatics, Vol. 3, ed. A. Iványi. AnTonCom, Budapest 2011, 1451--1490.

\bibitem{PirzadaNSI2010} \textsc{Pirzada, S., Naikoo, T. A., Samee, U. T., Iványi, A.:}   
\textit{Imbalances in directed multigraphs.} Acta Univ. Sapientiae, Inform. \textbf{2(1),} (2010) 47--71. 
 
\bibitem{PirzadaZI2010} \textsc{Pirzada, S., Zhou G., Iványi A.:} 
\textit{On $k$-hypertournament losing scores,}
Acta Univ. Sapientiae, Inform. \textbf{2(2),} (2010) 184--193.  

\bibitem{RodsethST2009} \textsc{R{\o}dseth, {\O}. J., Sellers, J. A., Tverberg, H.}: 
\textit{Enumeration of the degree sequences of non-separable graphs and connected graphs.} 
European J. Comb. \textbf{30(5),} 1309--1319. 


\bibitem{RuskeyCES1994} \textsc{Ruskey, F., Cohen, R., Eades, P., Scott, A.:}
\textit{Alley CAT's in search of good homes.} Congr. Num., \textbf{102,} (1994) 97--110.

\bibitem{SierksmaH1991} 
\textsc{Sierksma, G., Hoogeveen, H.:} 
\textit{Seven criteria for integer sequences being graphic.}  
J. Graph Theory \textbf{15(2),} (1991) 223--231.

\bibitem{Siklosi2001} 
\textsc{Siklósi, B.:} 
\textit{Soros és párhuzamos algoritmusok összehasonlítása sportversenyekkel kapcsolatos problémákban.} 
Programtervező matematikus diplomamunka. ELTE TTK, Budapest, 2001. 69 oldal.

\bibitem{Simion1997} 
\textsc{Simion, R.:} 
\textit{Convex polytopes and enumeration.} 
Advances in Applied Math. \textbf{18(2)} (1996) 149--180.

\bibitem{SloaneP1995} 
\textsc{Sloane N. J. A., Plouffe S.:} 
\textit{The Encyclopedia of Integer Sequences.} 
Academic Press, 1995. 

\bibitem{Sloane2011} 
\textsc{Sloane N. J. A.} (szerk.): 
\textit{Encyclopedia of Integer Sequences.} 2011.


\bibitem{Sloane2011A001700}
\textsc{Sloane N. J. A.:} 
\textit{The number of ways to put $n+1$ indistinguishable balls into $n+1$ distinguishable boxes.} 
In (ed. N. J. A. Sloane): The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A004251} 
\textsc{Sloane N. J. A.:} 
\textit{The number of degree-vectors for simple graphs.}
In (ed. N. J. A. Sloane): The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A005654} 
\textsc{Sloane N. J. A.:}
\textit{The number of bracelets with $n$ red, 1 pink and $n - 1$ blue beads.} 
In (ed. N. J. A. Sloane): The On-line Encyclopedia of the Integer Sequences. 2011.



\bibitem{SloaneP1995}
\textsc{Sloane, N., J., A., S. Plouffe:} 
\textit{The Encyclopedia of Integer Sequences.} 
Academic Press, 1995. 



\bibitem{Soroker1990} 
\textsc{Soroker, D.:} 
\textit{Optimal parallel construction of prescribed tournaments.} 
Discrete Appl. Math. \textbf{29(1),} (1990) 113--125.

\bibitem{Stanley1997} 
\textsc{Stanley, R.:} 
\textit{Enumerative Combinatorics. Vol. 2.} 
Cambridge University Press, Cambridge, 1997.  

\bibitem{Stanley1991} 
\textsc{Stanley, R.:} 
\textit{A zonotope associated with graphical degree sequence}. 
In: Applied Geometry and Discrete Mathematics, Festschr. 65th Birthday Victor Klee. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. \textbf{4,} (1991) 555-570.   

\bibitem{Temesi2011} 
\textsc{Temesi, J.:}
\textit{Pairwise comparison matrices and the error-free property of the decision maker.} 
CEJOR Cent. Eur. J. Oper. Res. \textbf{19,} (2) (2011) 239--249. 


\bibitem{TripathiT2008} 
\textsc{Tripathi, A., Tyagy, H.:} 
\textit{A simple criterion on degree sequences of graphs.} 
Discrete Appl. Math. \textbf{156(18),} (2008) 3513--3517.

\bibitem{TripathiV2003} 
\textsc{Tripathi, A., Vijay, S.:}  
\textit{A note on a theorem of Erd\H os} \& \textit{Gallai.} 
Discrete Math. \textbf{265(1--3),} (2003) 417--420.

\bibitem{TripathiVW2010} 
\textsc{Tripathi, A., Venugopalan, S., West, D. B.:} 
\textit{A short constructive proof of the Erdős-Gallai characterization of graphic lists.}
Discrete Math. \textbf{310(4),} (2010) 833--834.  

\bibitem{Weisstein2011DS} 
\textsc{Weisstein, E. W.:} 
\textit{Degree sequence.} 
From MathWorld---Wolfram Web Resource, 2011. 
 
\bibitem{Weisstein2011GS} 
\textsc{Weisstein, E. W.:} 
\textit{Graphic sequence.}
From MathWorld---Wolfram Web Resource, 2011.

\bibitem{WinstonK1983} 
\textsc{Winston, K. J., Kleitman, D. J.:} 
\textit{On the asymptotic number of tournament score sequences.} 
J. Combin. Theory Ser. A. \textbf{35,} (1983) 208--230. 

\end{footnotesize}

\end{thebibliography}

\begin{small}
\begin{center}
\textit{Beérkezett: }
\end{center}

\noindent IVÁNYI ANTAL \\
tony@compalg.inf.elte.hu \\ \\
LUCZ LORÁND \\
lorand.lucz@gmail.com \\ \\
MÓRI F. TAMÁS \\
mapoleon@freemail.hu  \\ \\
Eötvös Loránd Tudományegyetem \\
Természettudományi Kar \\
1117 Budapest, Pázmány Péter sétány 1/C \\


\vspace{4mm}
Budapest, 2011. november 26.

\begin{center}
\vspace{6mm}

LINEAR ERDŐS-GALLAI TEST

\vspace{4mm}
\textsc{ANTAL IVÁNYI, LORÁND LUCZ, F. TAMÁS MÓRI}
\end{center}

\noindent Havel in 1955 \cite{Havel1955}, Erdős and Gallai in 1960 \cite{ErdosG1960}, 
Hakimi in 1962 \cite{Hakimi1962}, Ruskey, Cohen, Eades and Scott 1994-ben \cite{RuskeyCES1994}, Barnes and Savage in 1997  
\cite{BarnesS1997}, Tripathi, Venugopalan and West in 2010 \cite{TripathiVW2010} proposed a method to decide, whether a sequence    
of nonnegative integers can be the degree sequence of a simple graph (such sequences are called graphical). 
The running time of their algorithms in worst case is $\Omega(n^2).$ In this paper we propose a new algorithm called 
\textsc{Erdős-Gallai-Linear}, whose worst running time is linear. Since in the case of a graphical sequence 
all elements of the investigated sequence are to be tested, in the case of RAM model of computations 
\textsc{Erdős-Gallai-Linear} is asymptotically optimal. Using this algorithm we determined the number of the degree sequences of 
the simple graphs for $n = 24, \ 25, \ 26, \ 27$ and $n = 28$ (\textit{Online Encyclopedia of Integer Sequences} 
\cite{Sloane2011A001700} contains these numbers only for $n = 1, \ \ldots, \ 23).$
\end{small}

\end{document}

