\documentclass[11pt,twoside]{article} 
\usepackage{euler,acta-info}
\usepackage[latin2]{inputenc}
\frenchspacing

\usepackage{epic}
\usepackage{eepic}

\title{%
On Erdős-Gallai and Havel-Hakimi algorithms
}

\newcommand{\vol}{\textbf{3,} 2 (2011) xx--yy}   %% to be completed by the editor, do not modify it
\setcounter{page}{1}  %% to be completed by the editor 

\newcommand{\amss}{\amssubj{%
%% Write here the AMS subject classification codes as: 68R15
05C85, 68R10
}}   %% Source:   http://www.ams.org/msc/    
\newcommand{\CRs}{\CRsubj{%
%% Write here the CR  Categories and Description codes codes as: 
G.2.2. [Graph Theory]: Subtopic - Network problems.
}}   %% Source: http://oldwww.acm.org/class/1998/
\newcommand{\keyw}{\keywords{%
%% Write here the keywords and phrases, as: 
simple graphs, prescribed degree sequences, Erdős-Gallai theorem, Havel-Hakimi theorem
}} 

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

\twoauthors{%
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony&angolul=1}{Antal Iv\'anyi }}
{%
\href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
\href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mailto:tony@compalg.inf.elte.hu}{tony@inf.elte.hu}
}{%
\href{http://people.inf.elte.hu/lulsaai}{Lor\'and Lucz}
}{%
 \href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
 \href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mailto:lorand-lutz@caesar.elte.hu}{lorand-lucz@caesar.elte.hu}}
 
\twoauthors{%
\href{http://www.cs.elte.hu/org/depts.html?tsz=valszam&lang=en&musthavecookie=1}{Tam\'as M\'ori}}
{%
\href{http://www.math.elte.hu/~mori/index.html}{Department of Probability Theory and Statistics},
\href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}  
{%
\href{mailto:moritamas@ludens.elte.hu}{moritamas@ludens.elte.hu}
}{%
 \href{http://people.inf.elte.hu/sopsaai}{P\'eter S\'ot\'er}
}{%
 \href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
 \href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mapoleon@freemail.hu}{mapoleon@freemail.hu}}


 %% Short name of the authors and short title, to be included in heading.

\short{%
A. Iványi, L. Lucz, T. M\'ori, P. Sótér
}{%
Quick Erdős-Gallai and Havel-Hakimi algorithms}

\begin{abstract}
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 EGL 
(Erdős-Gallai Linear algorithm), whose worst running time is $O(n).$ 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 EGL is asymptotically optimal. 
As an application of this quick algorithm we could enumerate the different degree sequences of simple graphs for 24, \ldots, 29 
vertices \cite{Sloane2011A004251}. 
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize
\section{Introduction\label{sec-Intro}}
In the practice an often appearing problem is the ranking of different objects as hardware or software products, cars, 
economical decisions, persons etc. A typical method of the ranking is the pairwise comparison of the objects, assignment 
of points to the objests and sorting the objects according to the sums of the numbers of the received points.

For example Landau \cite{Landau1953} references to biological, Hakimi \cite{Hakimi1962} to chemical, Kim et al. \cite{KimTME2009},  
Newman and Barabási \cite{NewmanB2006} to net-centric, Bozóki, Fülöp, Poesz and Rónyai to economical 
\cite{BozokiFP2011,BozokiFR2010}, Liljeros et al. \cite{LiljerosEASA2001} to human applications, while  Iványi and Pirzada  
 \cite{Ivanyi2009,Ivanyi2010,IvanyiP2011,PirzadaIK2011,PirzadaZI2010} to applications in sports.  

From several popular possibilities we follow the terminology and notations used by Pál Erdős and Tibor Gallai \cite{ErdosG1960}. 

Depending from the rules of the allocation of the points there are many problems. In this paper we deal only with the case when 
the comparisons have two possible results: either both objects get one point, or both objectos get zero points.
In this case the results of the comparisons can be represented using simple graphs.


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. In connection with this problem we remark that the main motivation for studying of this problem is 
the questin: what is the complexity of deciding whether a sequence is the score sequence of some football tournament 
\cite{Frank2011,Ivanyi2001,LuczISP2012MaCS}

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,Bodei2010,BrualdiK2009,delGenioKTB2010,
ErdosR???,HellK2009,IvanyiLS2011AML,KayibiKPI2011,Meierling2009,RodsethST2009,TripathiVW2010,Weisstein2011DS,Weisstein2011GS}, 
illetve \cite{BeasleyBR2009,BozokiFR2010,BuschCJ2010,ErdosMT2010,Frank2011,Ivanyi2009,Ivanyi2010,Ivanyi2011Kyoto,IvanyiS2011Opkut,
IvanyiP2011,KimTME2009,Knuth2011,Miklos2009,MiklosES2011,Pirzada2011,PirzadaIK2011,PirzadaNSI2010}).

Legyen $n \geq m \geq 11$ és $b \geq$. Egész számok $b = (b_1,\ldots,b_nm$ sorozatát \textit{$(m,n)$-korlátosnak} 
(röviden: korlátosnak) nevezzük, ha $0 \leq b_i \leq n - 1$ minden $1 \leq i \leq m$ indexre. 
A $b = (b_1,\ldots,b_m)$ $n$-korlátos sorozatot \textit{$(m,n)$-szabályosnak} (röviden: szabályosnak) mondjuk, ha   
$n - 1 \geq b_1 \geq \cdots \geq b_m \geq 0.$ Egy $(m,n)$-szabályos sorozatot 
\textit{$n$-megvalósíthatónak} (röviden: \textit{jónak}) nevezünk, ha létezik olyan $G$ egyszerű gráf, hogy 
$G$ foksorozata $(b_1,b_2,\ldots,b_m,0^{n-m}),$ ahol $0^{n - m}$ $n - m$ darab nulla elemet jelent. Ha egy 
korlátos vagy szabályos sorozat esetén $m = n,$ akkor az $n$ paramétert csak egyszer írjuk ki. 

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, azonban 
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,IvanyiP2011Opkut,KernP2001,KernP2004,KovacsP2002,Ivanyi2011Egres}. 

Melléktermékként bővítettük az EIS \cite{Sloane2011} adatbázist: egyrészt a benne lévő ismert sorozatok új elemeivel, másrészt 
konkrét alkalmazásokkal kapcsolatos új sorozatok elemeinek megadásával.

A cikkben egyrészt a vizsgált feladatot pontosan megoldó klasszikus és általunk javasolt új algoritmusokat, másrészt a feladat 
közelítő megoldását végző, új közelítő algoritmusokat vizsgálunk.

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ész 
az új tesztelő algoritmusokat ismerteti, az negyedik részben a közelítő algoritmusok hibáját vizsgáljuk, míg az ötödikben  
a pontos algoritmusok futási idejét elemezzük. 

A cikk eredményeinek egy része a magyar nyelvű \cite{Ivanyi2011AML} cikkből származik.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Classical precise algorithms\label{sec-classical}}
Given sequence $b = (b_1,\ldots,b_n)$ of nonegative integers the first $i$ elements of the sequence we call 
\textit{the head} of the sequence belonging to the index $i,$ while the last $n - i$ elements of the sequence we call 
\textit{the tail} of the sequence belonging to the index $i.$ 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi algorithm\label{subsec-HH}}
A feladat megoldására az első módszert Vaclav Havel cseh matematikus javasolta 1955-ben \cite{Havel1955,Lovasz2007}. 

\begin{theorem} \emph{(Havel \cite{Havel1955})} If $n \geq 3$, then the $n$-regular sequence $b = (b_1,\ldots,b_n)$   
is $n$-good if and only if the sequence $b' = (b_2 - 1, b_3 - 1, \ldots,  b_{b_1} - 1, b_{b_1 + 1} - 1, 
b_{b_1 + 2}, \ldots, b_n)$ is $(n - 1)$-good.
\end{theorem}

\begin{proof} See \cite{Havel1955}.
\end{proof}

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 legrosszabb esetben $\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 például a teljes gráfnak $\textbinom{n}{2}$ éle van, a megvalósítást is biztosító algoritmus futási ideje nem lehet 
kisebb, mint négyzetes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erdős-Gallai algorithm\label{subsec-EG}}
In 1962 Louis Hakimi \cite{Hakimi1962} published independently the same result, therefore the theoren is called today 
usually as  \textit{Havel-Hakimi theorem}, and the method of reconstruction 
is called \textit{Havel-Hakimi algorithm}.

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. 

\begin{theorem} \emph{(Erdős, Gallai, \cite{ErdosG1960})} Let\label{theorem-EG} $n \geq 3.$ The $n$-regular sequence 
$b = (b_1\ldots,b_n)$ is $n$-graphical if and only if 
\begin{equation}
\sum _{i=1}^n b_i \quad \mbox{even}\label{eq-EGparos}
\end{equation}
and
\begin{equation}
\sum_{i=1}^j b_i - j(j - 1) \leq \sum _{k=j+1}^n \min(j,b_k) \quad (j = 1,\ldots,n-1).\label{eq-EGbinom}
\end{equation}
\end{theorem}

\begin{proof} See \cite{Choudum1986,ErdosG1960,SierksmaH1991,TripathiVW2010}.
\end{proof}

Bár ez a tétel csak ellenőriz, (\ref{eq-EGbinom}) módszeres alkalmazása legrosszabb esetben (például jó sorozatok esetén) 
$\Theta(n^2)$ időt igényel. A közelmúltban Tripathi et al. \cite{TripathiVW2010} publikáltak a tételre konstruktív 
bizonyítást, amely megvalósítható bemenet esetén $O(n^3)$ idő alatt egy megoldást is előállít.  

\textsc{Erdős-Gallai}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{New precise theorems\label{section-newprecise}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Zerofree algorithms \label{subsec-zerofree}}
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} If\label{lemma-zerofree} $n \geq 1$, the $(b_1,\ldots,b_n)$ $(n,n)$-regular   
sequence is $n$-graphical if and only if $b_n = 0$ or the sequence $(b_1, \ldots, b_p)$ is $(p,p)$-graphical.
\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{Sorting and shifting Havel-Hakimi algorithms\label{subsec-HHShi}}
Havel és Hakimi eredeti tételének természetes algoritmikus megfelelőjét HHSo-nak (Havel-Hakimi Sorting) 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 a Havel-Hakimi Shifting algoritmust (HHSh) kapjuk.

The pseudocode of the algithm see in \cite{IvanyiLS2012AML}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parity checking Havel-Hakimi algorithm\label{subsec-HHP}}
É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 rövidített 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.

The pseudocode of the algithm see in \cite{IvanyiLS2012AML}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Shortened Erdős-Gallai algorithm (\textsc{EGSh})\label{subsec-EGS}}
$H_i$ maximális értéke szabályos sorozat esetén $n(n - 1),$ ezért a \ref{theorem-EG}. Erdős-Gallai tételben szereplő 
(\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ő \ref{lemma-EGS}. 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, 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{even}\label{eq-EGSparos} 
\end{equation}
and
\begin{equation}
H_i - \min(H_i,i(i - 1)) \leq \sum _{k=l+1}^n \min(i,b_k) 
\quad (i = 1,2,\ldots,g),\label{eq-EGStbinom}
\end{equation}
where 
\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{Jumping Erdős-Gallai algorithm\label{subsec-EGJ}}
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_{e_1} + \cdots e_{i_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}
and
\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{EGL-All} algoritmusban kihasználjuk, hogy a (\ref{eq-TVbinom}) egyenlőtlenségben $\sigma _q$ mindig 
$n,$ ezért 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{Input.} $n $: a csúcsok száma $(n \geq 1)$; \\
$b = (b_1, b_2, \ldots, b_n)$: $n$-szabályos sorozat.

\textit{Output.} $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.} $i$ és $j$: ciklusváltozók; \\
$H = (H_0, H_1,\ldots,H_n)$: $H_i$ $b$ első $i$ elemének az összege; \\
$p$: $b$ pozitív elemeinek a száma; \\
$b_{p + 1}$: segédváltozó annak eldöntéséhez, hogy $b_p$ ugró elem-e.  

\medskip
\noindent \textsc{Erd\H os-Gallai-Jumping}$(n,b,L,\gamma)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $p = n$                                        \` $\rhd$Lines 01--03: computing of the number of positive elements \\
\hspace{-7mm}02 \textbf{while} \= $b_p = 0$ \\
\hspace{-7mm}03                \> $p = p -1$  \\
\hspace{-7mm}04 $H_1 = b_1$                                 \` $\rhd$ Lines 04--09: test of parity \\
\hspace{-7mm}05 \textbf{for} \= $i = 2$ \textbf{to} $p$ \\
\hspace{-7mm}06              \> $H_i = H_{i-1} + b_i$ \\
\hspace{-7mm}07 \textbf{if} \= $H_p$ odd \\
\hspace{-7mm}08             \> $L = \textsc{False}$ \\
\hspace{-7mm}09             \>  \textbf{return} $L$  \\
\hspace{-7mm}10 $b_{p + 1} = 0$                        \` $\rhd$ Lines 11--23: test of the request of the head \\
\hspace{-7mm}11 $i = 1$ \\
\hspace{-7mm}12 \textbf{while} \= $i \leq p$ és $(i - 1) \geq H_i$\\
\hspace{-7mm}13                \> \textbf{if} \= $b_i == b_{i+1}$ \\
\hspace{-7mm}14                \>            \> $i = i +1$ \\ 
\hspace{-7mm}15                \>             \> $E = 0$ \\
\hspace{-7mm}16                \>             \> \textbf{for} \= $j = i + 1$ \textbf{to} $p$ \\
\hspace{-7mm}17                \>             \> $E = E + \min(j,b_j)$ \\
\hspace{-7mm}18                \> \textbf{if} \= $H_i > i(i - 1) + E$ \\
\hspace{-7mm}19                \>             \> $L = \textsc{False}$ \\  
\hspace{-7mm}20                \>             \> \textbf{return} $L$ \\
\hspace{-7mm}21  $L = \textsc{True}$ \\
\hspace{-7mm}21 \textbf{return} $L$  
\end{tabbing}


function L = EGJ( n, b )
p = n;
while b(p) == 0
   p = p - 1;
end
H(1) = b(1);
for i = 2:p
   H(i) = H(i-1) + b(i);
end
if mod(H(p), 2) == 1
   L = false;
   return
end
b(p+1) = 0;
i = 1;
while i<=p \&\& (i-1) <= H(i) %% 2. feltetel megforditva
   if b(i) ~= b(i+1) %% feltetel megfordítva
      E = 0;
      for j=i+1:p
         E = E + min(i,b(j)) ; % min( i, b(j) ) !!!
      end
      if H(i) > i*(i-1) + E
         L = false;
         return;
      end
   end
   i = i + 1; %% athelyezve
end
L = true;
return;
end

Input argument "n" is undefined.

Error in ==> EGJ at 3
p = n;


The running time of \textsc{EGJ} varies between the best $\Theta(1)$ and the worst $\Theta(n^2)$.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Linear Erdős-Gallai algorithm\label{subsec-EGlinearis}}
Recently we could improve this theorem \cite{IvanyiL2011AML,IvanyiLS2011Comb}. 
The algorithm \textsc{Erdős-Gallai-Linear} exploits, that $q$ is monoton. It determines the $C_i$ capacities 
in constant time. The base of the quick computation is the sequence $m(q)$ containing indices.
 
For given sequence $q$ let $m(q) = (m_1,\ldots,m_{n-1}),$ where $m_i$ points to the element of $q_k$ 
having the maximal index among such elements of $q$ which are greater or equal with $i.$

\begin{theorem} \emph{(Iványi, Lucz \cite{IvanyiL2011Comb}, Iványi, Lucz, Sótér \cite{IvanyiLS2011AML})} 
If  $n \geq 1,$\label{tetel-EGL} the $n$-regular sequence $(q_1\ldots,q_n)$ is graphical if and only if
\begin{equation}
H_n \quad \mbox{is even}\label{eq-EGLparos}
\end{equation}
and if $i > m_i,$ then
\begin{equation}
H_i \leq i(i - 1) + H_n - H_i,\label{eq-EGLlargei}
\end{equation}
further if $i \leq m_i,$ then
\begin{equation}
H_i \leq i(i - 1) + i(m_i -i) + H_n - H_{m_i},\label{eq-EGLlargei}
\end{equation}
\end{theorem}
\begin{proof}
(\ref{eq-EGLparos}) is the same as (\ref{eq-EGparos}). 

During the testing of the elements of $q$ by \textsc{Erdős-Gallai-Linear} there are two cases: 
\begin{itemize}
\item if $i > m_i,$ then the contribution of the tail of $q$ equals to 
$H_n - H_i,$ since the contribution $C_k$ of the element $q_k$ is only $q_k.$ 
\item if $i \leq m_1,$ then the contribution of the tail of $q$ consists of two parts: $C_{i+1},\ldots,C_{m_i}$ 
equal to $i,$ while $C_j = b_j$ for $j = m_{i} + 1,\ldots,n.$ 
\end{itemize}

Therefore in the case $n - 1 \geq i > m_i$ we have
\begin{equation}
C_i = i(i - 1) + H_n - H_i,\label{eq-EGLClargei}
\end{equation}
and in the case $1 \leq i \leq m_i$ 
\begin{equation}
C_i = i(i - 1) + i(m_i -i) + H_n - H_{m_i}.\label{eq-EGLCsmalli}
\end{equation}
\end{proof}

The following program is based on Theorem \ref{theorem-EGL}. 
It decides on arbitrary $n$-regular sequence whether it is graphicakl or not. 

\textit{Input}. $n$: number of vertices $(n \geq 1)$; \\
$q = (q_1,\ldots,q_n)$: $n$-regular sequence.  

\textit{Output}. $L$: logical variable, whose value is \textsc{True}, if the input is graphical, 
and it is \textsc{False}, if the input is not graphical. 

\textit{Work variables.} $i$ and $j$: cycle variables; \\
$H = (H_1,\ldots,H_n)$: $H_i$ is the sum of the first $i$ elements of the tested $q$; \\
$m = (m_1,\ldots,m_{n-1})$: $m_i$ is the maximum of the indices of such elements of $q,$ which are 
not smaller than $i$;
$H_0 = 0$: help variable to compute of the other elenments of the sequence $H$; \\
$q_0 = n -1$: help variable to compute the elements of the sequence $m$. \\


\bigskip
\noindent \textsc{Erd\H os-Gallai-Linear}$(n,b)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = 0$                                            \` $\rhd$ Line 01: initialization \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$ Lines 02--03: computation of the elemnts of $H$    \\     
\hspace{-7mm}03              \> $H_i = H_{i-1} + b_i$ \\ 
\hspace{-7mm}04 \textbf{if} \= $H_n$ \textrm{ odd}    \` $\rhd$ Lines 04--06: test of the parity    \\ 
\hspace{-7mm}05             \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $b_0 = n - 1$                             \` $\rhd$ Line 07: initialization of a working variable \\ 
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$ Lines 08--12: computation of the indices   \\ 
\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              \>             \>              \> $m_j = i - 1$ \\
\hspace{-7mm}12              \>             \> $m_{b_i} = i$ \\ 
\hspace{-7mm}13 \textbf{for} \= $j = b_n$ \textbf{downto} $1$  \` $\rhd$ Lines 13--14: large indices\\
\hspace{-7mm}14              \> $m_j = n$ \\  
\hspace{-7mm}15 \textbf{for} \= $i = 1$ \textbf{to} $n$            \` $\rhd$ Lines 15--23: test of the elements of $b$ \\                          
\hspace{-7mm}16              \> \textbf{if} \= $i \leq m_i$                 \` $\rhd$ Lines 16--19: test of indices for large $m_i$'s \\ 
\hspace{-7mm}17              \>             \> \textbf{if} \= $H_i > i(i - 1) + i(m_i - i) + H_n - H_{m_i}$ \\
\hspace{-7mm}18              \>             \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}19              \>             \>             \> \textbf{return} $L$ \\  
\hspace{-7mm}20              \> \textbf{if} \= $i > m_i$  \` $\rhd$ Lines 20--23: test of indices for small $m_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$ Lines 24--25: the program ends with the value \textsc{True} \\
\hspace{-7mm}25 \> \textbf{return} $L$  \\ 
\end{tabbing}

\begin{theorem} \emph{(Iványi, Lucz \cite{IvanyiL2011Comb}, Iványi, Lucz, Sótér \cite{IvanyiLS2011Acta})} 
Algorithm \textsc{Erdős-Gallai-Linear} decides in $O(n)$ time, whether an  $n$-regular sequence 
$q = (q_1,\ldots,q_n)$ is graphical or not.  
\end{theorem} 

\begin{proof} Line 1 requires $O(1)$ time, lines 2--3 $O(n)$ time, lines 4--6 $O(1)$ time, line 07 $O(1)$ time, 
line 08--09 $O(1)$ time, lines 10--18 $O(n)$ time, lines 19--25 $O(n)$ time and lines 26--27 $O(1)$ time, 
therefore the total time requirement of the algorithm is $O(n)$. 
\end{proof}

Until now the number of good sequences was known only for $n = 1, \ 2, \ \ldots, \ 23,$ see 
\textit{Online Encyclopedia of Integer Sequences} \cite{Sloane2011}.   
Using the new and quick algorithms we determined $\gamma(n)$ for $n = 24, \ 25, \ \ldots, \ 28$ 
too \cite{IvanyiL2011Comb,IvanyiLS2011AML}.
Figure \ref{fig-sorozatszam} contains the number of good sequences $\gamma(n)$ for $n = 1, \ \ldots, \ 28,$ 
and also $\gamma(n + 1)/\gamma(n)$ for $n = 1, \ \ldots, \ 28.$ 

\begin{figure}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||c|c|c|c|c||}  \hline \hline
$n$  & $\beta(n)$  &$\varphi(n)$     & $\gamma(n)$  & $\gamma(n+1)/\gamma(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{4}$ &$\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$& $???$      \\ \hline \hline
\end{tabular}
\caption{Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences 
for neighbouring values of $n$.\label{fig-sorozatszam}}
\end{center}
\end{small}
\end{figure} 

\section{Quick \textsc{Erd\H os-Gallai} algorithm}
A következő, a \ref{theorem-EGL} \textsc{Erd\H os-Gallai-Quick} algoritmus minden $n$-páros sorozatot megvizsgál, 
és kimenetként megadja a 
$\gamma(n)$ értéket. Az algoritmus kihasználja, hogy a a páros sorozatok lexikografikusan csökkenső 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. 

Például a $h(b')$ metszéspont vagy megegyezik $h(b)$-vel, vagy annál eggyel kisebb. 

\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{Input}. $n$: the number of vertices $(n \geq 4);$ (we bound $n$ from below to free the program from the investigation of 
the special properties of the short programs).

\textit{Output}. $\gamma$: the number of the $n$-graphical sequences. 

\textit{Working variables.} $i$ and $j$: cycle variables; \\
$b = (b_1,\ldots,b_n)$: $b_i$ the $i$th element of the actually tested even sequence; \\
$H = (H_0,H_1,\ldots,H_n)$: $H_i$ the sum of the first $i$ elements of the tested sequence; \\
$h$: the intersection point of the tested sequence $b$; \\
$C(b) = C = (c_1,c_2,\ldots,c_{q-1})$: list of maximal length of the control points; \\ 
$c$: number of control points in the actual list $C$; \\
$f = (f_1,\ldots,f_ {q-1}$: $f_i = \max(h,\sigma _i),$ the $i$-th control point.

\bigskip
\noindent \textsc{Erd\H os-Gallai-Quick}$(n,\gamma)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = c = 0$                                              \` $\rhd$ Lines 01--04: initialization \\
\hspace{-7mm}02 $\gamma = 1$ \\
\hspace{-7mm}03 $h = n - 2$  \\
\hspace{-7mm}04 $f = n - 1$ \\
\hspace{-7mm}05 \textbf{for} \= $i = 1$ \textbf{to} $n$           \` $\rhd$ Lines 05--06: generation of the first tested sequence \\     
\hspace{-7mm}06              \> $b_i = n - 1$ \\
\hspace{-7mm}07              \> $H_i = H_i + b_i$                              \` $\rhd$ Line 07: computation of $H_i$'s \\        
\hspace{-7mm}08 \textbf{while} \= $b_1 > 0$                             \` $\rhd$ Line 08: is there more sequence?   \\ 
\hspace{-7mm}09                \> \textbf{if} \= $b_h < h$                                 \` $\rhd$ Lines 09--10: updating of $h$ \\
\hspace{-7mm}10                \>             \> $h = h - 1$\\
\hspace{-7mm}11                \> \textbf{for} \= $i=1$ \textbf{to} $c$   \` $\rhd$ Lines 11--14: test of the actual sequence \\
\hspace{-7mm}12                \>              \> $f = \max(h,\sigma _i)$ \\
\hspace{-7mm}13                \>              \> \textbf{if} \= $H_i > f(f - i) + H_n - H_ f$ \\
\hspace{-7mm}14                \>              \>             \> \textbf{go to} 18        \` $\rhd$ continuation with a new sequence \\           
\hspace{-7mm}15                \> $\gamma = \gamma + 1$       \` $\rhd$ Line 15: rise of $\gamma$ after a graphical sequence \\
\hspace{-7mm}16                \> \textbf{go to} 18                               \` $\rhd$ continuation with a new sequence  \\
\hspace{-7mm}17 \textbf{return} $\gamma$ \` $\rhd$ Line 17: end of the program \\ 
\hspace{-7mm}18 \textbf{if \ \ \ \ \ \ } \= $b_n \geq 2$ \=  \` $\rhd$ Lines 18--69: generation of a new sequence \\
\hspace{-7mm}19               \> $b_n = b_n - 2$                       \` $\rhd$ Lines 18--27: $b_n = 2$     \\
\hspace{-7mm}20               \> $H_n = H_n - 2$ \\
\hspace{-7mm}21               \> \textbf{if \ } \= $c = 0$ \\
\hspace{-7mm}22               \>                \> $c = 1$ \\
\hspace{-7mm}23               \>                \> $C_1 = n - 1$ \\
\hspace{-7mm}24               \> \textbf{else if} \= $C_c = n - 1$  \` $\rhd$ here $c > 1$ \\  
\hspace{-7mm}25               \>                  \> $c = c + 1$ \\
\hspace{-7mm}26               \>                  \> $C_{c + 1} = n - 1$ \\
\hspace{-7mm}27               \> \textbf{go to} 08 \\             
\hspace{-7mm}28 \textbf{else if} \= $b_n == 1$                                   \` $\rhd$ Lines 28--43: $b_n = 1$\\
\hspace{-7mm}29                  \> $b_{n - 1} = b_{n - 1} - 1$ \\
\hspace{-7mm}30                  \> $b_n = b_{n-1}$ \\
\hspace{-7mm}31                  \> $H_{n-1} = H_{n-1} - 1$ \\
\hspace{-7mm}32                  \> \textbf{if} \= $b_n$ is odd \\
\hspace{-7mm}33                  \>             \> $b_n = b_n - 1$ \\ 
\hspace{-7mm}34                  \> $H_n = H_{n - 1} + b_n$ \\
\hspace{-7mm}35                  \> \textbf{ if } \= $b_n = 0$ és $b_{n-1} > 0$ \\
\hspace{-7mm}36                  \>               \> \textbf{ if } \= $b_{n-2} = b_{n-1} + 1$ \\
\hspace{-7mm}37                  \>               \> \textbf{else} \> $C_c = n - 2$  \\
\hspace{-7mm}38                  \>               \>               \> $c = c + 1$ \\
\hspace{-7mm}39                  \>               \>               \> $C_c = n - 1$ \\
\hspace{-7mm}40                  \> \textbf{else} \> \textbf{if} \= $b_{n-2} = 1$ \\
\hspace{-7mm}41                  \>               \>             \> $c = c + 1$ \\
\hspace{-7mm}42                  \>               \>             \> $C_c = n - 2$ \\
\hspace{-7mm}43                  \> \textbf{go to} 08 \\
\hspace{-7mm}44 \textbf{else if} \= $b_n == 0$                              \` $\rhd$ Lines 44--69: $b_n = 0$  \\
\hspace{-7mm}45                  \> $j = n - 1$ \\
\hspace{-7mm}46                  \> \textbf{while} \= $b_j == 0$ \\
\hspace{-7mm}47                  \>                \> $j = j - 1$ \\
\hspace{-7mm}48                  \> \textbf{ if } \= $b_j \geq 2$ \\ 
\hspace{-7mm}49                  \>               \> $b_j = b_j - 1$ \\
\hspace{-7mm}50                  \>               \> $H_j = H_j - 1$ \\
\hspace{-7mm}51                  \>               \> \textbf{for} \= $k = j + 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}52                  \>               \>              \> $b_k = b_j$ \\
\hspace{-7mm}53                  \>               \>              \> $H_k = H_j + (k - j)b_j$ \\
\hspace{-7mm}54                  \>               \>              \textbf{if} \= $(n - j)b_j$ is even \\
\hspace{-7mm}55                  \>               \>                          \> $b_n = b_n - 1$ \\
\hspace{-7mm}56                  \>               \> $H_n = H_{n - 1} + b_n$  \\
\hspace{-7mm}57                  \> \textbf{else} \= $b_{j-1} = b_{j - 1} - 1$     \` $\rhd$ here $b_j = 1$ \\
\hspace{-7mm}58                  \>               \> $H_{j-1} = H_{j-1} - 1$ \\
\hspace{-7mm}59                  \>               \> \textbf{for} \= $k = j$ \textbf{to} $n - 1$ \\
\hspace{-7mm}60                  \>               \>              \> $b_k = b_{j-1}$  \\
\hspace{-7mm}61                  \>               \>              \> $H_k = H_{j-1} + (k - j + 1)b_j$ \\
\hspace{-7mm}62                  \>               \>              \> \textbf{if} \= $(n - j)b_n$ is odd \\
\hspace{-7mm}63                  \>               \>              \>             \> $b_n = b_n - 1$ \\
\hspace{-7mm}64                  \>               \>              \> $H_n = H_{n - 1} + b_n$ \\
\hspace{-7mm}65                  \> \textbf{ if } \= $b_j > 0$ \= \textbf{ if } \= $b_{n-2} = b_{n-1} > b_n$ \\
\hspace{-7mm}66                  \>               \>           \>               \>            \> $C_c = n - 1$ \\
\hspace{-7mm}67                  \> \textbf{else} \>           \> \textbf{else} \> $b_{n-2} > b_{n-1} = b_n$ \\
\hspace{-7mm}68                  \>               \>           \>               \>            \> $C_c = n - 2$ \\
\hspace{-7mm}69                  \> \textbf{go to} 08 \\
\end{tabbing}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Enumerative results\label{sec-enum}}
Eddig például Burns \cite{Burns2007}, Erdős és Moser \cite{Moon1968}, Kleitman és Winston \cite{KleitmanW1981}, 
Winston és Kleitman \cite{WinstonK1983}, Stanley \cite{Stanley1991}, 
Ruskey et al. \cite{RuskeyCES1994}, Barnes és Savage \cite{BarnesS1995,BarnesS1997}, 
Simion \cite{Simion1997}, Frank, Savage and Selers \cite{FrankSS2002}, R{\o}dseth et al. \cite{RodsethST2009} 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. 

\begin{lemma} Ha\label{lemma-rhon} $n \geq 1,$ akkor az $n$-korlátos sorozatok $\kappa(n)$száma
\begin{equation}
\kappa(n) = n^n,\label{eq-kappaen}
\end{equation}
az $n$-szabályos sorozatoké pedig 
\begin{equation}
\rho(n) = \binom{2n - 1}{n}.\label{eq-rhon}
\end{equation}
\end{lemma}

\begin{proof} A korlátos sorozatok számára vonatkozó képlet közvetlen adódik abból, hogy mind az 
$n$ elem $n$ lehetséges értéket vehet fel.

Egy $b = (b_1,\ldots,b_n)$ $n$-szabályos sorozat esetén legyen $b' = (b_1',\ldots, b_n')$, ahol 
$b_i' = b_i + i - 1$. A lehetséges $b$ és $b'$ sorozatok halmazai között kölcsönösen egyértelmű kapcsolat áll fenn. 
A különböző $b'$ sorozatok száma pedig annyi, ahány féleképpen a különböző $0, \ 1, \ \ldots, \ 2n -2$ számok közül 
$n$ számot ki tudunk választani.
\end{proof}

A szimulációs vizsgálatok elemzésénél (is) hasznos a szabályos és a páros sorozatok számait 
megadó függvények tulajdonságainak ismerete.

\begin{lemma} Ha $n \geq 1,$ akkor\label{lemma-rhonjell}
\begin{equation}
\frac{\rho(n + 2)}{\rho(n + 1)} > \frac{\rho(n + 1)}{\rho(n)},\label{eq-rhonmon}
\end{equation}
\begin{equation}
\lim \rho _{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) < \rho(n) < 
\frac{4^n}{\sqrt{4\pi n}}\large(1 - \frac{1}{8n+8}\large).\label{rhon} 
\end{equation}
\end{lemma}

\begin{proof} 
A (\ref{eq-rhon}) egyenlőség alapján
\begin{equation}
\frac{\rho(n + 2)}{\rho(n + 1)} = \frac{(2n + 3)!(n + 1)n!}{(n + 2)!(n + 1)!(2n + 1)!} 
 = \frac{4n + 6}{n + 2} = 4 - \frac{2}{n + 2}, 
\end{equation} 
ahonnan (\ref{eq-rhonmon} és (\ref{eq-rhonlim} is közvetlenül adódik.
\end{proof}

\begin{lemma} \emph{(Ascher, Sloane, Pfoffe \cite{Ascher1987,SloaneP1995})} Ha\label{lemma-epsn} $n \geq 1,$ 
akkor az $n$- páros sorozatok $\epsilon(n)$ száma
\begin{equation}
\epsilon(n) = \frac{1}{2} \left ( \textbinom{2n -1}{n} + \textbinom{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 $\epsilon(n)$ aszimptotikus nagyságrendjét.

\begin{lemma} Ha\label{lemma-epsn} $n \geq 1,$ akkor
\begin{equation}
\frac{\epsilon(n + 2)}{\epsilon(n + 1)} > \frac{\epsilon(n + 1)}{\epsilon(n)},\label{eq-epsnmon}
\end{equation}
\begin{equation}
\lim \epsilon _{n \rightarrow \infty} = 4,\label{eq-rhonlim}
\end{equation}
továbbá 
\begin{equation}
\frac{4^n}{\sqrt{\pi n}}(1 - \delta _3(n)) < \epsilon(n) < \frac{4^n}{\sqrt{\pi n}}(1 - \delta _4(n)),\label{eq-rhonass} 
\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}

Amint azt a következő állítás és a \ref{fig-kozrelativ}. ábra is mutatja, az $\epsilon(n)/\rho(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{\epsilon(n + 1)}{\rho(n + 1)} < \frac{\epsilon(n)}{\rho(n)}\label{eq-epsrhomon}
\end{equation}
és
\begin{equation}
\lim _{n \leftarrow \infty} \frac{\epsilon(n)}{\rho(n)} = \frac{1}{2}.\label{eq-epsrholim}
\end{equation}
\end{corollary}

\begin{proof} 

\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} 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} 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-ron}. lemma szerint az $n$-szabályos sorozatok száma 
$\rho(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}

\begin{lemma} Ha $n \geq 1,$ akkor a $b$ $n$-szabályos sorozatot $b = (b_1^{e_1},\ldots,b_m^{e_m})$ alakban felírva 
az $e_j$ kitevők (''futamhosszak``) várható értéke 

konstans ?   $\log n$ ???
\end{lemma}

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


A jó sorozatok $\gamma(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  $\gamma(n)$ 
száma a következő korlátok közé esik:
\begin{equation}
\frac{4^n}{cn} < \gamma(n) <  \frac{4^n}{(\log n)^C \sqrt{n}}.
\end{equation}
\end{lemma}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section{Testing algorithms\label{sec-testing}}
Let $H_i = b_1 + \cdots + b_i$ and $T_i = b_{i+1} + \cdots + b_n  \ (i = 1, \ldots, n)$. 
Adott $i$ esetén a $b$ sorozat $i$-hez tartozó \textit{fejének} a $b_1, \ \ldots, \ b_i$ elemeket, míg 
$i$-hez tartozó \textit{farkának} a $b_{i+1}, \ \ldots, \ b_n$ elemeket nevezzük. 
A sorozatok megvalósíthatóságának vizsgálata során természetes észrevétel, hogy a $b$ fejéhez tartozó 
fokszámigényt részben belső, részben pedig külső fokszámokkal elégítjük ki. 

Először egy "paritásos", majd egy "binomiális", egy "haszontalan", egy "pozitív", 
egy "fejfelező" és végül egy "farokfelező" szűrő algoritmust mutatunk be. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parity test\label{subsec-parity}}
Első tesztünk az Erdős-Gallai tétel első szükséges feltételén alapul. Nagyon hatékony teszt, mivel mind a korlátos, mind a 
szabályos sorozatoknak körülbelül fele páratlan sorozat, és a teszt ezekről lineáris idő alatt megállapítja, 
hogy biztosan nem jó sorozatok.

\begin{lemma} If\label{lemma-paritas} $n \geq 1$ and $b$ is an $n$-good sequence, then 
\begin{equation}
H_i \quad \mbox{even} \quad (i = 1, \ldots, n).\label{eq-parossag}
\end{equation}
\end{lemma}

\begin{proof} Every edge of a simple graph adds two to the sum of the degrees.
\end{proof}

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

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

\textit{Output}. $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{Working variable:}. $i$: ciklusváltozó;

$S = (S_1, \ldots, S_n)$: $S_i$ az első $i$ fejelem összege. Az $S$ sorozatot globális változónak tekintjük, ezért a 
további algoritmusoknál \textit{nem} tüntetjük fel bemenő adatként. 

\bigskip
\noindent \textsc{Parity-Test}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $H_1 = b_1$ \\
\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} $\mathcal{L}$
\end{tabbing}

Ennek az algoritmusnak a lépésszáma minden esetben $\Theta(n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Binomial test\label{subsec-binom}}
Második tesztünk az Erdős-Gallai tétel másik szükséges feltételén alapul. Nevét arról kapta, hogy a fej belső 
éleinek a számát egy binomiális együttható segítségével becsüljük.

\begin{lemma} If\label{lemma-binom} $n \geq 1$ and $b$ is an $n$-good sequence, then 
\begin{equation} 
H_j - j(j - 1) \leq T_j  \quad (j = 1, \ldots, n - 1).\label{eq-binom}
\end{equation}
\end{lemma}

\begin{proof} A (\ref{eq-binom}) egyenlőtlenség bal oldalán szereplő összeg a $b$ sorozat fejének fokszámigénye. 
Ebből levonjuk az igény belső párosításokkal elérhető csökkenésére adható felső korlátot. A jobb oldalon pedig 
a felhasználható külső fokszámok felső korlátja szerepel.
\end{proof}

A lemmában javasolt tesztet végzi el a következő program.

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

\textit{Output}. $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{Working variables.} $i, \ j$: ciklusváltozók;

$H = (H_1, \ldots, H_n)$: $H_i$ az első $i$ fejelem összege;

$T = (T_1, \ldots, T_n)$: $T_i$ a $b$ sorozat $i$-nél nagyobb indexű elemeinek összege.


\bigskip
\noindent \textsc{Binomial-Test}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $B_1 = 1$ \\
\hspace{-7mm}02 \textbf{for} \= $j = 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}09              \> $R_j = S_n - S_j$ \\
\hspace{-7mm}03              \> \textbf{if} \> $S_j - j(j - 1) > R_j$ \\
\hspace{-7mm}04              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}05              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}06 $L = \textsc{True}$ \\
\hspace{-7mm}07 \textbf{return} $\mathcal{L}$
\end{tabbing}

Ennek az algoritmusnak a futási ideje legrosszabb esetben $\Theta(n),$ míg legjobb esetben csak $\Theta(1).$ Átlagos 
futási idejének meghatározása további vizsgálatokat igényel.

Mivel (\ref{eq-binom}) jobb oldalán a (\ref{eq-EGbinom}) egyenlet jobb oldalán lévőnél gyengébb feltétel szerepel, ez a 
lemma csak a vizsgált sorozatok szűrésére alkalmas közelítő algoritmus alapjául szolgálhat. 

Az eddigi szimulációs vizsgálatok szerint nagyon hatékony szűrő algoritmus. Aszimptotikus hatékonysága kulcs fontosságú 
az optimális tesztelő algoritmus szempontjából.     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Unuseful test\label{subsec-hasz}}
A fejen belül megvalósítható párosításnak nem csak a fejben lévő elemek száma, hanem a hozzájuk tartozó fokszámok 
összege is korlátja. Ezt fejezi ki a következő állítás.

\begin{lemma} If\label{lemma-hasz} $b$ is an $n$-good sequence, then 
\begin{equation} 
H_i - \min \left ( j(j - 1), H_i \right )  \leq T_i  \quad (j = 1, \ldots, n - 1).
\end{equation}
\end{lemma}

\begin{proof} Az egyenlőtlenség bal oldalán megjelent új követelmény abból adódik, hogy a fej belső döntetlenjeihez legfeljebb 
annyi szabad fokot tudunk felhasználni, mint a fej elemeinek összege.
\end{proof}

Az új követelmény csak látszólag javítja a tesztelés hatékonyságát, mert ha a fejelemek összege 
kisebb vagy egyenlő a mellette lévő binomiális együtthatónál, akkor az egyenlőtlenség bal oldala nemnegatív, ami 
természetesen kisebb vagy egyenlő lesz a farokelemek összegénél. 
Ezért ennek a feltételnek az ellenőrzését nem is végezzük el.

Ugyanakkor ez a szükséges feltétel egyrészt jó ötletet ad az Erdős-Gallai algoritmus gyorsítására (lásd majd az 
\ref{sec-pontos}. részben a \ref{tetel-EGrovid}. tételt), másrészt további közelítő algoritmusoknak lesz a kiindulási pontja.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Positive test\label{subsec-pozitiv}}
Természetesen a farokban lévő nulla elemek nem növelik a farok párosítási potenciálját. Ez az észrevétel lehetővé teszi, 
hogy a $j$-edik elemhez tartozó farok párosítási potenciáljára $T_j$-nél pontosabb becslést adjunk. 

Legyen $p = \max (j | b_j > 0)$ a $b$ sorozat pozitív elemeinek száma.  

\begin{lemma} If\label{lemma-pozitiv} $b$ is an $n$-good sequence, then 
\begin{equation}
H_j - j(j - 1) \geq \min(R_j, j(p - j), (p - j)b_{j+1}).
\end{equation}
\end{lemma}

\begin{proof} A minimumban $j(p - j)$ azt jelzi, hogy a fej külső párosítási teljesítményéhet a fej elemei egyenként legfeljebb 
annyival tudnak hozzájárulni, ahány pozitív elem van a farokban.  A $(p - j)b_{j + 1}$ 
elem pedig azt fejezi ki, hogy a farokban lévő $p - j$ elem mindegyikének legfeljebb annyi a hozzájárulása, mint a farokban 
lévő legnagyobb elem.
\end{proof}

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

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

\textit{Output}. $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{Working variabke:}. $i$: ciklusváltozó;

$p$: a bemenetben lévő pozitív elemek száma

$H $: Globális változó. 

\bigskip
\noindent \textsc{Positive-test}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $p = n$ \\
\hspace{-7mm}02 \textbf{while} \= $b_p = 0$ \\
\hspace{-7mm}03                \> $p = p - 1$ \\
\hspace{-7mm}04 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}05              \> \textbf{if} $H_i - j(j - 1) > \min (R_j,jb_j,(p - j)b_{j+1}$ \\
\hspace{-7mm}05              \> $L = \textsc{False}$ \\
\hspace{-7mm}06              \> \textbf{return} $L$ \\
\hspace{-7mm}07 $L = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $\mathcal{L}$
\end{tabbing}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Halfing of the head\label{subsec-fejfelez}}
We get a better estimation of the inner capacity of the head, than the binomial coefficient gives in (\ref{eq-binom}).

Lényeges körülmény, hogy a \ref{lemma-binom}. és \ref{lemma-hasz}. lemmák használata \textit{lineáris} időt igényel (míg a korábbi 
két tétel négyzetes futási időt). Az Erdős-Gallai tétel javítása viszont csak a másodfokú futási idő együtthatóját 
csökkenti, nagyságrendjét azonban nem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Composite test\label{subsec-osszetett}}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Properties of the approximate algorithms\label{sec-kozhat}}
A közelítő algoritmusok hatékonyságát a szabályos sorozatok tesztelésével vizsgáljuk. Adott A algoritmusnak az $n$ 
hosszúságú szabályos sorozatokra vonatkozó hatékonyságát az algoritmus által elfogadott (ki nem zárt) és jó 
$n$ hosszúságú 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ó hibájának nevezzük. 

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

1) \textsc{Párosság-teszt}

2) \textsc{Binomiális-teszt}

3) \textsc{Pozitív-teszt}

4) \textsc{Fejfelező-teszt}

5) \textsc{Farokfelező-teszt}

Ha $n = 2,$ akkor (\ref{eq-roen}) szerint $\rho(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 $\beta(n)$-nel jelölve $\beta(2) = 2.$ Az $n$ hosszúságú 
helyreállítható sorozatok számát jelöljük $\gamma(n)$-nel. Ekkor $\gamma(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 $\rho(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 $\pi(3) = 6.$ Ezek közül a \textsc{Binomiális-teszt} kizárja a (2,2,0) és (2,0,0) sorozatokat, így 
$\beta(3) = 4.$ A megmaradt 4 sorozat helyreállítható, így $\gamma(3) = 4.$

Ha $n = 4,$ akkor a szabályos sorozatok száma $\rho(4) = 35.$ Ezek közül 19 a páros, és a következő 11 a helyreállítható: 
(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 16 páros sorozat közül \textsc{Binomiális-teszt} is kizárja azt az öt sorozatot, amelyeket az \textsc{Erdős-Gallai}, így 
$\beta(4) = \gamma(4) = 11$ és $R_{\textsc{BT}}(4)$ = 11/11 = 1.

Ezek szerint a legfeljebb 4 hosszúságú sorozatokra nézve a \textsc{Binomiális-teszt} hibátlanul kiszűri a nem jó 
sorozatokat. A \ref{fig-relativ}. táblázat ezeket az adatokat foglalja össze. 

A táblázat is mutatja, hogy míg $n \leq 4$ esetén $\beta(n) = \gamma(n),$ azaz a \textsc{Binomiális-teszt} ugyanannyi 
sorozatot fogad el, mint a pontos algoritmusok, $n > 4$ esetén egyre nő a \textsc{Binomiális-teszt} hibája: $n = 5$ 
esetén még csak egyetlen páros sorozatról nem ismeri fel, hogy rossz, $n = 6$ esetén már hatszor hibázik.

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}  \hline \hline
$n$  &    $\rho(n)$  &$\epsilon(n)$& $\beta(n)$   &   $ \pi(n)$  &$\varphi(n)$  &   $\tau(n)$ &  $\gamma(n)$    \\ \hline \hline
$1$  &     $1$       &     $1$     &    $1$       &      $1$     &$1$           &     $1$     & $1$  \\ \hline
$2$  &     $3$       &     $2$     &    $2$       &      $2$     &   $2$        &     $2$     & $2$  \\ \hline
$3$  &     $10$      &     $6$     &    $4$       &      $4$     &   $4$        &     $4$     & $4$        \\ \hline
$4$  &     $35$      &     $19$    &    $11$      &      $11$    &   $11$       &     $11$    & $11$        \\ \hline
$5$  &     $126$     &     $66$    &    $31$      &      $31$    &   $31$       &     $31$    & $31$      \\ \hline
$6$  &     $462$     &     $236$   &    $103$     &      $102$   &   $???$       &            &      $102$      \\ \hline 
$7$  &     $1716$    &     $868$   &    $349$     &      $342$   &   $???$        &           &      $342$    \\ \hline 
$8$  &     $6435$    &    $3235$   &    $1256$    &      $1213$   &   $???$          &        &      $1213$ \\ \hline 
$9$  &     $24310$   &   $12190$   &    $4577$    &      $4361$   &   $???$         &         &     $4361$  \\ \hline 
$10$  &    $92378$   &   $46252$   &    $17040$   &      $16016$  &   $???$         &         &    $16016$\\ \hline 
$11$  &   $352716$   &  $176484$   &    $63944$   &      $59348$  &   $???$         &         &     $59348$ \\ \hline 
$12$  & $1352078$    &  $676270$   &  $242218$    &      $222117$ &   $???$         &         &     $222117$ \\ \hline 
$13$  & $5200300$    & $2600612$   & $922239$     &   $836315$   &   $???$         &          &     $836315$ \\ \hline 
$14$  &$20058300$    &$10030008$   &$???????$     &   $3530534$  &   $???$         & &  $3166852$ \\ \hline 
$15$  &$77558760$    &$38781096$   &    $???$     &      $???$   &   $???$         & &  $12042620$ \\ \hline 
$16$  &$300540195$   &$150273315$  &    $???$     &      $???$   &   $???$         & &  $45967479$ \\ \hline 
$17$  &$1166803110$  &$583407990$  &    $???$     &      $???$   &   $???$         & &  $675759564$ \\ \hline 
$18$  &$4537567650$  &$2268795980$ &    $???$     &      $???$   &   $???$         & &  $675759564$ \\ \hline 
$19$  &$17672631900$ &$8836340260$ &    $???$     &      $???$   &   $???$         & &$2600672458$ \\ \hline 
$20$  &$68923264410$ &$34461678394$&    $???$     &      $???$   &   $???$         & &$10029832754$  \\ \hline 
$21$  &$269128937220$&$134564560988$&   $???$     &      $???$   &   $???$         & & $38753710486$ \\ \hline 
$22$ &$1052049481860$&$526024917288$&   $???$     &      $???$   &   $???$         & &$149990133774$ \\ \hline 
$23$ &$4116715363800$&$2058358034616$&   $???$    &      $???$   &   $???$         & & $581393603996$\\ \hline 
$24$&$16123801841550$&$???$          &   $???$    &      $???$   &   $???$         & &$???$        \\ \hline 
$25$&$\mathbf{63205303218876}$&$???$ &   $???$    &       $???$  &   $??$         &  &    $??$ \\ \hline \hline
\end{tabular}
\caption{The number of regular, even, binomial, positive, tailtested and good sequences.\label{fig-relativ}}
\end{center}
\end{figure}



\begin{figure}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}  \hline \hline
$n$  &$\epsilon(n)$ & $100\beta(n)/\epsilon(n)/$&$100\pi(n)/\epsilon(n)$&$100\varphi(n)/\epsilon(n)$&$100\gamma(n)/\epsilon(n)$ \\ \hline \hline
$2$  &     $3$      &     $2$                   &     $2$               &      $2$                  &     \\ \hline
$3$  &     $10$     &     $6$                   &    $4$                &      $4$                  &       \\ \hline
$4$  &     $35$     &     $19$                  &    $11$               &      $11$                 &       \\ \hline
$5$  &     $126$     &     $66$    &    $32$      &      $31$     &$32/31 = 1,032$           \\ \hline
$6$  &     $462$     &     $236$   &    $108$     &      $102$    &$108/102=1,059$      \\ \hline 
$7$  &     $1716$    &     $868$   &    $376$     &      $342$    &$376/342=1,099$      \\ \hline 
$8$  &     $6435$    &    $3235$   &    $???$     &      $1213$   &      $??$           \\ \hline 
$9$  &     $24310$   &   $12190$   &    $???$     &      $4361$   &      $??$      \\ \hline 
$10$  &    $92378$   &   $46252$   &    $???$     &      $16016$  &      $??$      \\ \hline 
$11$  &   $352716$   &  $176484$   &    $???$     &      $59348$  &      $??$      \\ \hline 
$12$  &    $????$   &  $676270$   &    $???$     &$222117$       &      $??$      \\ \hline 
$13$  &    $????$   & $2600612$   &    $???$     &$836315$       &      $??$      \\ \hline 
$14$  &    $????$   &$10030008$   &    $???$     &$3166852$      &      $??$      \\ \hline 
$15$  &    $????$   &$38781096$   &    $???$     &$12042620$     &      $??$      \\ \hline 
$16$  &    $????$   &$150273315$  &    $???$     &$45967479$     &      $??$      \\ \hline 
$17$  &    $????$   &$583407990$  &    $???$     &$675759564$    &      $??$      \\ \hline 
$18$  &    $????$   &$2268795980$ &    $???$     &$675759564$    &      $??$      \\ \hline 
$19$  & $????$      &$8836340260$ &    $???$     &$2600672458$   &      $??$      \\ \hline 
$20$  & $????$      &$34461678394$&    $???$     &$10029832754$  &      $??$      \\ \hline 
$21$  & $?????$     &$134564560988$&    $???$     &$38753710486$  &      $??$     \\ \hline 
$22$  & $????$      &$526024917288$&    $???$     &$149990133774$ &      $??$     \\ \hline 
$23$  & $????$      &$2058358034616$&    $???$     &$581393603996$ &      $??$    \\ \hline 
$24$  & $????$      &$???$          &    $???$     &$???$          &      $??$    \\ \hline 
$25$  & $????$      &$???$          &    $???$     &$???$          &      $??$    \\ \hline \hline
\end{tabular}
\caption{Characteristic relativ properties of the approximate algorithms.\label{fig-abszolut}}
\end{center} 
\end{figure}

Eddig például Erdős és Moser \cite{Moon1968}, Kleitman és Winston \cite{KleitmanW1981}, 
Winston és Kleitman \cite{WinstonK1983}, Stanley \cite{Stanley1991}, 
Ruskey et al. \cite{RuskeyCES1994}, Barnes és Savage \cite{BarnesS1995,BarnesS1997}, 
Simion \cite{Simion1997}, Frank, Savage and Selers \cite{FrankSS2002}, R{\o}dseth et al. \cite{RodsethST2009} 
publikáltak foksorozatok számával kapcsolatos eredményeket. Az általunk vizsgált sorozatok számával kapcsolatos eredmények 
találhatók az \textit{On-line Encyclopedia of Integer Sequences} című honlapon 
\cite{Sloane2011A001700,Sloane2011A004251,Sloane2011A005654} is. 

A \ref{fig-abszolut} táblázatban $\rho(n)$ értéke $n = 24$-ig az EIS A001700 sorozata \cite{Sloane2011A001700}, 
$\epsilon(n)$ értéke $n = 23$-ig az EIS A005654 sorozata \cite{Sloane2011A005654}, $\gamma(n)$ értéke pedig $n = 23$-ig 
az EIC A0004251-es sorozata \cite{Sloane2011A004251} sorozata. A többi értéket mi határoztuk meg.

Eddig első sorban soros algoritmusokat alkalmaztunk, de vannak párhuzamos eredmények is 
\cite{PecsySz2000,Siklosi2001,Soroker1990}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Running time of the classical testing algorithms\label{sec-classalg}}
A tesztek elemzésénél a korlátos, illetve a szabályos sorozatokat vettük alapul. A szabályos sorozatok halmaza a legkisebb olyan 
halmaz, melynek elemszámát egyszerű explicit képlettel meg tudtuk adni. Az $ n - 1 \geq a_i \geq 1$ és az $n - 1 \geq a_i \geq 0$ 
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 monoton 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)$ "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. 

Az első típusú javításra példa a rövidítés és az ugrás, a másikra példa a Havel-Hakimi algoritmus kiegészítése a paritás 
vizsgálatával és az Erdős-Gallai algoritmus kiegészítése a binomiális algoritmussal, valamint a farok és a fej elemzésével.

A következő pontos algoritmusokat vizsgáljuk:

1) HH1 (HHSo): Sorting Havel-Hakimi algorithm.

2) HH2 (HHSh): Shifting Havel-Hakimi algorithm

3) HH3 (HHP): Parity checkig Havel-Hakimi algorithm.

4) HH4: (HHA): Approximate Havel-Hakimi algorithm.

5) EG1: (EG):Erdős-Gallai algorithm.

6) EG2: (EGS): Shortened Erdős-Gallai algorithm.

7) EG3: (EGJ): Jumping Erdős-Gallai algorithm.

8) EG4: Approximate Erdős-Gallai algorithm.
  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Running time of \textsc{EG-Linear} \label{sec-EGLinear}}

A következő program a \ref{theorem-EGL}. tétel alapján adott $n$-re az összes $n$-páros sorozatot előállítja 
és teszteli, hogy jók-e. A teljes program futási ideje minden sorozatra $O(n),$ így a teljes futási idő $O(n \epsilon(n)).$

\textit{Input}. $n$: a csúcsok száma $(n \geq 1).$ 

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

\textit{Working variables.} $i$ és $j$: ciklusváltozók; \\
$b = (b_1,\ldots,b_n)$: $b_i$ az éppen tesztelt páros sorozat $i$-edik eleme;
$H = (H_0,H_1,\ldots,H_n)$: $H_i$ az éppen tesztelt $b$ első $i$ elemének az összege;
$h$: a vizsgált $b$ sorozat metszéspontja. \\

\noindent \textsc{EG-Linear}$(n,\gamma)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = 0$                                              \` $\rhd$ 01--03. sor: kezdeti értékek beállítása \\
\hspace{-7mm}02 $\gamma = 1$ \\
\hspace{-7mm}03 $h = n - 2$  \\
\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_1 > 0$                             \` $\rhd$ 07. sor: van-e még vizsgálandó sorozat?   \\ 
\hspace{-7mm}08 \textbf{if} \= $b_h < h$                                 \` $\rhd$ 08--09. sor: $h$ frissítése \\
\hspace{-7mm}09             \> $h = h - 1$\\
\hspace{-7mm}10                \> \textbf{for} \= $i=1$ \textbf{to} $h-1$   \` $\rhd$ 10--17. sor: aktuális sorozat tesztelése \\
\hspace{-7mm}11                \>              \> \textbf{if} \= $H_i > i(i - 1) + i(h - i) + H_n - H_h$ \\
\hspace{-7mm}12                \>              \>             \> \textbf{go to} 18        \` $\rhd$ áttérés új sorozatra \\
\hspace{-7mm}13                \> \textbf{for} \= $i=h$ \textbf{to} $n-1$    \\
\hspace{-7mm}13                \>              \> \textbf{if} \= $H_i > i(i - 1) + H_n - H_i$ \\
\hspace{-7mm}14                \>              \>             \> \textbf{go to} 18 \` $\rhd$ áttérés új sorozatra \\            
\hspace{-7mm}15                \> $\gamma = \gamma + 1$   \\
\hspace{-7mm}16                \> \textbf{go to} 18 \\
\hspace{-7mm}17 \textbf{return} $\gamma$ \` $\rhd$ 17. sor: program befejezése \\ 
\hspace{-7mm}18 \textbf{if} \= $b_n \geq 2$  \` $\rhd$ 18--51. sor: új sorozat előállítása \\
\hspace{-7mm}19             \> $b_n = b_n - 2$ \\
\hspace{-7mm}20             \> $H_n = H_n - 2$ \\
\hspace{-7mm}21             \>  \textbf{go to} 07 \\
\hspace{-7mm}22 \textbf{if} \= $b_n == 1$ \\
\hspace{-7mm}23             \> $b_{n - 1} = b_{n - 1} - 1$ \\
\hspace{-7mm}24             \> $b_n = b_{n-1}$ \\
\hspace{-7mm}25             \> $H_{n-1} = H_{n-1} - 1$ \\
\hspace{-7mm}26             \> \textbf{if} \= $b_n$ páratlan \\
\hspace{-7mm}27             \>             \> $b_n = b_n - 1$ \\ 
\hspace{-7mm}28             \> $H_n = H_{n - 1} + b_n$ \\
\hspace{-7mm}29             \> \textbf{go to} 07 \\
\hspace{-7mm}30 \textbf{if} \= $b_n == 0$ \\
\hspace{-7mm}31             \> $j = n - 1$ \\
\hspace{-7mm}32             \> \textbf{while} \= $b_j == 0$ \\
\hspace{-7mm}33             \>                \> $j = j - 1$ \\
\hspace{-7mm}34             \> \textbf{ if } \= $b_j \geq 2$ \\ 
\hspace{-7mm}35             \>               \> $b_j = b_j - 1$ \\
\hspace{-7mm}36             \>               \> $H_j = H_j - 1$ \\
\hspace{-7mm}37             \>               \> \textbf{for} \= $k = j + 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}38             \>               \>              \> $b_k = b_j$ \\
\hspace{-7mm}39             \>               \>              \> $H_k = H_j + (k - j)b_j$ \\
\hspace{-7mm}40             \>               \>              \textbf{if} \= $(n - j)b_j$ páros \\
\hspace{-7mm}41             \>               \>                          \> $b_n = b_n - 1$ \\
\hspace{-7mm}42             \>               \> $H_n = H_{n - 1} + b_n$  \\
\hspace{-7mm}43             \> \textbf{else} \= $b_{j-1} = b_{j - 1} - 1$     \` $\rhd$ itt $b_j = 1$ \\
\hspace{-7mm}44             \>               \> $H_{j-1} = H_{j-1} - 1$ \\
\hspace{-7mm}45             \>               \> \textbf{for} \= $k = j$ \textbf{to} $n - 1$ \\
\hspace{-7mm}46             \>               \>              \> $b_k = b_{j-1}$  \\
\hspace{-7mm}47             \>               \>              \> $H_k = H_{j-1} + (k - j + 1)b_j$ \\
\hspace{-7mm}48             \>               \>              \> \textbf{if} \= $(n - jb_n$ páratlan \\
\hspace{-7mm}49             \>               \>              \>             \> $b_n = b_n - 1$ \\
\hspace{-7mm}50             \>               \>              \> $H_n = H_{n - 1} + b_n$ \\
\hspace{-7mm}51             \> \textbf{go to} 07 \\
\end{tabbing}


\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||c|c|c|c|c|c||}  \hline \hline
$n$  &  $\epsilon(n)$  & $\tau(n)$, mp  & $$Op(n)$$ & $\tau(n)/\epsilon(n)/n,$ mp 
& $Op(n)/\epsilon(n)/n$       \\ \hline \hline
$1$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$2$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$3$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$4$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$5$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$6$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$7$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$8$  &    ???    &  ???    &   ???    & ???   &  ???    \\ \hline
$9$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$10$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$11$  &    ???    &  ???    &   ???    & ???  &  ???      \\ \hline
$12$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$13$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$14$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$15$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$16$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$17$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$18$  &    ???    &  ???    &   ???    & ???   &  ???    \\ \hline
$19$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$20$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$21$  &    ???    &  ???    &   ???    & ???  &  ???      \\ \hline
$22$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$33$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$24$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$25$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline \hline
\end{tabular}
\caption{Total and amortized running time of \textsc{EG-Linear} in secundum, resp. in the number of executed operations 
műveletszámban kifejezve.\label{fig-EGLinear}}
\end{center} 
\end{footnotesize}
\end{figure}



\paragraph{Acknowledgements.} The authors thank Tamás F. Móri \cite{Mori2011} for proving Lemma \ref{lemma-korsziv} 
and \ref{lemma-szabsziv}, Ádám Mányoki (TFM World Kereskedelmi és Szolgáltató Kft.) for the help in running of our 
timeconsuming programs and the unknown referee for the useful corrections. 
The European Union and the European Social Fund have provided financial support to the project 
under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.



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

\bibitem{AvisF1996} D. Avis, K. Fukuda, Reverse search for enumeration, 
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Appl. Math.}
\textbf{2} (1993) 21--46.

\bibitem{BarnesS1995} T. M. Barnes, C. D. Savage, A recurrence for counting graphical partitions,  
\href{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{\textit{Electron.}} \textit{J. Combin.}  
\textbf{2,} (1995), Research Paper 11, 10 pages (electronic).

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

\bibitem{BeasleyBR2009} L. B. Beasley, D. E. Brown, K. B. Reid,  
Extending partial tournaments. \textit{Math. Comput.}   
\href{http://www.sciencedirect.com/science?\_ob=ArticleListURL\&\_method=list\&\_ArticleListID=1698301564\&\_sort
=r\&\_st=13\&view=c\&\_acct=C000043568\&\_version=1\&\_urlVersion=0\&\_userid=798018\&md5=5d6c97b3cdad4eddae528491f6693061\&
searchtype=a}{\textit{Modelling}} \textbf{50,} (1) (2009) 287--291.

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

\bibitem{Bodei2010} N. Bodei, Degree sequences of graphs, Master thesis, Dept. of Operation Research of Eötvös Loránd University 
(supervisor A. Frank), Budapest, 2010.

\bibitem{BozokiFP2011} S. \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Bozóki} S.,    
J. \href{http://www.oplab.sztaki.hu/cv_fj_hu.htm}{Fülöp},  
A. \href{http://portal.uni-corvinus.hu/index.php?id=801}{Poesz}: 
On pairwise comparison matrices that can be made consistent by the modification of a few elements. 
\href{}{\textit{CEJOR}} \textit{Cent. Eur. J. Oper. Res.} \textbf{19} (2011) 157--175.

\bibitem{BozokiFR2010} \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Bozóki} S.: 
J. \href{http://www.oplab.sztaki.hu/cv_fj_hu.htm}{Fülöp}, L. \href{http://www.sztaki.hu/~ronyai/}{Rónyai}:  
On optimal completion of incomplete pairwise comparison matrices.    
\textit{Math. Comput. Modelling} \textbf{52,} (2010) 318--333.

\bibitem{BrualdiK2009} A. R. \href{http://www.math.wisc.edu/~brualdi/}{Brualdi},   
K. Kiernan: Landau's and {R}ado's theorems and partial tournaments,   
\href{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{\textit{Electron.}}   
\textit{J. Combin.} \textbf{16(\#N2),} (2009) (6 pp).

\bibitem{Burns2007} 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} A. N. Busch, G. Chen, M. S. Jacobson,  
Transitive partitions in realizations of tournament score sequences.  
\textit{J.} \href{http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118/issues}{\textit{Graph Theory}} 
\textbf{64(1),} (2010), 52--62.

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

\bibitem{CormenLRS2009} T. H. \href{http://www.cs.dartmouth.edu/~thc/}{Cormen},   
Ch. E. \href{http://people.csail.mit.edu/cel/}{Leiserson},  
R. L. \href{http://people.csail.mit.edu/rivest/}{Rivest},  
C. \href{http://www.columbia.edu/~cs2035/}{Stein},     
\textit{Introduction to Algorithms.} Third edition, The
\href{http://mitpress.mit.edu/main/home/default.asp}{MIT} 
Press/\href{http://www.mhprofessional.com/category/?cat=1012}{McGraw} Hill, 
Cambridge/New York, 2009.

\bibitem{delGenioKTB2010} C. I. \href{http://www.biond.org/user/22}{Del Genio},  
Z. \href{http://icensa.nd.edu/kim.shtml}{Kim}, H., \href{http://obelix.phys.nd.edu/~toro/}{Toroczkai},     
K. E. \href{http://nsm.uh.edu/about/faculty/?155622-961-5=kbassler}{Bassler},   
Efficient and exact sampling of simple graphs with given arbitrary 
\href{http://www.plosone.org/article/info$\%$3Adoi$\%$2F10.1371$\%$2Fjournal.pone.0010012}{degree sequence}. 
\href{http://www.plosone.org/home.action}{PLoS ONE} \textbf{5(4)}, e10012 (2010).

\bibitem{ErdosG1960} P. \href{http://www-history.mcs.st-and.ac.uk/Mathematicians/Erdos.html}{Erd\H os},     
T. \href{http://hu.wikipedia.org/wiki/Gallai_Tibor}{Gallai},   
Graphs with vertices having prescribed degrees (Hungarian), \textit{Mat. Lapok} \textbf{11,} (1960) 264--274.

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

\bibitem{ErdosMT2010} P. L. \href{http://www.renyi.hu/~elp/}{Erd\H os},   
I. \href{http://www.renyi.hu/~miklosi/}{Miklós}, I., Z. \href{http://obelix.phys.nd.edu/~toro/}{Toroczkai},    
\textit{A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs.} 
\href{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{Electron.} J. Combin. \textbf{17(1),} (2010) R66 (10 pp).

\bibitem{Frank2011} A. \href{http://www.cs.elte.hu/~frank/}{Frank}, \textit{Connections in Combinatorial Optimization.}   
\href{http://oup.com/}{Oxford} University Press, Oxford, 2011.

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

\bibitem{Hakimi1962} S. L. \href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi},    
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} S. L. \href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi},  
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{Havel1955} V. Havel,  A remark on the existence of finite graphs (Czech); \textit{\u{C}asopis P\u{e}st. Mat.}  
\textbf{80} (1955), 477--480. 

\bibitem{HellK2009} P. Hell, D. Kirkpatrick,  
Linear-time certifying algorithms for near-graphical sequences. 
\href{http://www.sciencedirect.com/science/journal/0012365X}{Discrete} Math. \textbf{309(18)}, (2009) 5703--5713. 

\bibitem{Ivanyi2001} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},   
Testing of score sequences (Hungarian). In: (szerk. ???) \textit{XXV. Hungarian Conference of Operation Research} 
(Debrecen, 2001. október 17--20), 53--53.

\bibitem{Ivanyi2009} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},   
Reconstruction of complete interval tournaments. \textit{}Acta Univ. Sapientiae, 
\href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{Informatica}, 
\textbf{1,} (1) (2009) 71--88.

\bibitem{Ivanyi2010} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},     
Reconstruction of complete interval tournaments. II. \textit{Acta Univ. Sapientiae,}  
\href{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{\textit{Mathematica}}, 
\textbf{2(,} (1) (2010) 47--71.

\bibitem{Ivanyi2011Egres} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},    
Deciding the validity of the score sequence of a soccer tournament. In: \textit{Open problems of the}   
\href{http://lemon.cs.elte.hu/egres/open/Deciding_the_validity_of_the_score_sequence_of_a_soccer_tournament}
{\textit{Egerváry}} \textit{Research Group,} Budapest, 2011. 

\bibitem{Ivanyi2011Kyoto} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},   
Directed graphs with prescribed score sequences. In: \textit{The 7th Hungarian-Japanese Symposium on Discrete Mathematics 
and Applications} (Kyoto, May 31 - June 3, 2011), 114--123.

\bibitem{IvanyiL2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},
L. \href{http://people.inf.elte.hu/lulsaai}{Lucz}, Erdős-Gallai test in linear time. \textit{Combinatorica} (submitted).

\bibitem{IvanyiLS2011AML} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},
L. \href{http://people.inf.elte.hu/lulsaai}{Lucz}, P. \href{http://people.inf.elte.hu/sopsaai}{S\'ot\'er}, 
Linear Erdős-Gallai test (Hungarian). \textit{Alk. Mat. Lapok} (submitted).

\bibitem{IvanyiLS2012CEJOR} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
L. \href{http://people.inf.elte.hu/lulsaai}{Lucz}, P. \href{http://people.inf.elte.hu/sopsaai}{S\'ot\'er}, 
Parallel Erdős-Gallai algorithm. \textit{Central European J.} 
\href{http://www.springerlink.com/content/1435-246X}{Operation Research} (submitted).

\bibitem{IvanyiP2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},     
S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, Comparison based ranking, in: 
\href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{\textit{Algorithms of Informatics, Vol. 3,}}   
ed. A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
\href{http://www.antoncom.hu/books.htm}{AnTonCom}, Budapest 2011, 1262--1311.  

\bibitem{Katai2010} I. Kátai,  Personal communication, Budapest, 2010.

\bibitem{KayibiKPI2011} K. K. Kayibi, M. A. Khan, S. \href{http://www.dharwadker.org/pirzada/}{Pirzada},  
A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},  
Random sampling of minimally cyclic digraphs with given imbalance sequence. 
\textit{Acta Univ. Sapientiae, Math.} (submitted).

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

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

\bibitem{KernP2001}  K. Kern, D. Paulusma, The computational complexity of the elimination problem in
generalized sports competitions. \href{}

\bibitem{KimTME2009} H. \href{http://icensa.nd.edu/kim.shtml}{Kim},  
Z. \href{http://obelix.phys.nd.edu/~toro/}{Toroczkai},    
I. \href{http://www.renyi.hu/~miklosi/}{Miklós}, P. L. \href{http://www.renyi.hu/~elp/}{Erd\H os},   
l. A. \href{http://www.math.sc.edu/~szekely/}{Székely},   
\href{http://www.renyi.hu/~elp/KTEMS-IOP09.pdf}{Degree-based} graph construction. 
\textit{J. Physics: Math. Theor. A} \textbf{42,} (39) (2009) 392--401.

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

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

\bibitem{Knuth2011} D. E. \href{http://www-cs-faculty.stanford.edu/~uno/}{Knuth},    
\textit{The Art of Computer Programming. Volume 4A, Combinatorial 
Algorithms.} Addison--Wesley, Upper Saddle River, 2011.

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

\bibitem{KovacsP2002} G. Zs. Kovács, N. Pataki, 
Rangsorolási algoritmusok elemzése. Scientific student paper, Faculty of Sciences of Eötvös Loránd University,    
Budapest, 2002.  \href{http://compalg.inf.elte.hu/~tony/Oktatas/TDK/}{http://compalg.inf.elte.hu/$\sim$tony/Oktatas/TDK/}. 

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

\bibitem{Landau1953} H. G. Landau, On dominance relations and the structure of 
\href{http://www.springerlink.com/content/765042v152l07721/}{animal societies}. III. 
The condition for a score sequence. \textit{Bull. Math.} \href{}{\textit{Biophys.}} \textbf{15,} (1953) 143--148. 

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

\bibitem{Lovasz2007} L. \href{http://www.cs.elte.hu/~lovasz/}{Lovász},     
\textit{Combinatorial Problems and Exercises} (corrected version of 
the second edition).  AMS \href{http://www.ams.org/bookstore/chelsealist}{Chelsea} Publishing, Boston, 2007. 
 Magyarul: \textit{Kombinatorikai problémák és feladatok.} Typotex, Budapest, 1999.
 
 \bibitem{LuczISP2012MaCS} L. Lucz, A. Iványi, P. Sótér, S. Pirzada, Testing and enumeration of football sequences. 
 
\bibitem{Meierling2009} D. Meierling,   L. \href{http://www.math2.rwth-aachen.de/de/mitarbeiter/volkm}{Volkmann},  
L.: A remark on degree sequences of multigraphs. \textit{Math. Methods} 
\href{http://people.su.se/~liljeros/}{\textit{Oper. Res.}} \textbf{69(2),} (2009) 369--374. 

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

\bibitem{MiklosI2009} I. Miklós, Graphs with prescribed degree sequences (Hungarian). Lecture in Alfred Rényi Institute 
of Mathematics, 16 November 2009. 

\bibitem{MiklosES2011} I. \href{http://www.renyi.hu/~miklosi/}{Miklós},  
P. L. \href{http://www.renyi.hu/~elp/}{Erdős}, L. \href{http://www.renyi.hu/~soukup/}{Soukup},      
A remark on degree sequences of multigraphs. (2011) (submitted). 

\bibitem{Moon1968} J. W. Moon, \textit{Topics on Tournaments.} 
\href{http://www.harcourt.com/bu\_info/hrw.html}{Holt}, Rinehart, and Winston, New York, 1968.

\bibitem{NewmanB2006} M. E. J. \href{http://www-personal.umich.edu/~mejn/}{Newman},    
A. L. \href{http://www.nd.edu/~alb/}{Barabási},  
\textit{The Structure and Dynamics of Networks}. Princeton University Press, Princeton, NJ. 2006.

\bibitem{PecsySz2000} G. Pécsy, L. Szűcs,   
Parallel verification and enumeration of tournaments. 
\textit{Stud. Univ. Babe\c s-Bolyai, Inform.} \textbf{45(2),} (200) 11--26. 

\bibitem{Pirzada2011} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, \textit{Graph Theory.} 
\href{http://www.orientlongman.com/}{Orient} Blackswan (to appear).

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

\bibitem{PirzadaIK2011} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada},   
A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},   
M. A. \href{http://faculty.kfupm.edu.sa/PYP/malikhan/}{Khan},  Score sets and kings. In: 
\href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{\textit{Algorithms of Informatics}}, Vol. 3, 
ed. by A. Iványi. \href{http://www.antoncom.hu/books.htm}{AnTonCom}, Budapest 2011, 1451--1490.

\bibitem{PirzadaNSI2010} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada},    
T. A. Naikoo, T. A., U. T. Samee, U. T., A. \href{http://compalg.inf.elte.hu/~tony}{Iványi},    
Imbalances in directed multigraphs. \textit{Acta Univ. Sapientiae,} 
\href{http://www.acta.sapientia.ro}{\textit{Informatica}} \textbf{2(1),} (2010) 47--71. 
 
\bibitem{PirzadaZI2010} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada},   
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},  
\href{http://math.nju.edu.cn/~gfzhou/EnglishVersion.html}{Zhou},  
On $k$-hypertournament losing scores, \textit{Acta Univ. Sapientiae,} 
\href{http://www.acta.sapientia.ro}{\textit{Informatica}} \textbf{2(2),} (2010) 184--193.  
   
\bibitem{RodsethST2009} {\O} J. R{\o}dseth, J. A. Sellers, H. Tverberg, 
Enumeration of the degree sequences of non-separable graphs and connected graphs. 
\textit{European J. Comb.} \textbf{30,} (5), 1309--1319.

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

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

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

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

\bibitem{Sloane2011} N. J. A. \href{http://www2.research.att.com/~njas/}{Sloane} (Ed.), 
\textit{\href{http://oeis.org/Seis.html}{Encyclopedia} \textit{of Integer Sequences.}} 2011.

\bibitem{Sloane2011A001700} N. J. A. \href{http://www2.research.att.com/~njas/}{Sloane}, 
\textit{The \href{http://oeis.org/A001700}{number} of ways to put $n+1$ 
indistinguishable balls into $n+1$ distinguishable boxes.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A004251} N. J. A. \href{http://www2.research.att.com/~njas/}{Sloane}, 
\textit{The \href{http://oeis.org/A004251}{number} 
of degree-vectors for simple graphs.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A005654} N. J. A. \href{http://www2.research.att.com/~njas/}{Sloane}, 
\textit{The \href{http://oeis.org/A005654}{number} Number of bracelets 
with $n$ red, 1 pink and $n - 1$ blue beads.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

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

\bibitem{Soroker1990} D. Soroker, \textit{Optimal parallel construction of prescribed tournaments.} 
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Appl. Math.} 
\textbf{29(1),} (1990) 113--125.  

\bibitem{Stanley1991} R. \href{}{Stanley}, A zonotope associated with graphical degree sequence. In: 
\textit{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{TripathiT2008} A. Tripathi, H. Tyagy, 
A simple criterion on degree sequences of graphs. 
\textit{Discrete Appl. Math.} \textbf{156,} (18) (2008) 3513--3517.

\bibitem{TripathiV2003} A Tripathi, S. \href{http://www.math.illinois.edu/~sujith/}{Vijay},   
A note on a theorem of Erd\H os \& Gallai.  
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Math.} 
\textbf{265,} (1--3) (2003) 417--420.

\bibitem{TripathiVW2010} A. Tripathi, S. Venugopalanb, D. B. \href{http://www.math.uiuc.edu/~west/}{West},  
A short constructive proof of the Erdős-Gallai characterization of graphic lists.
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Math.} 
\textbf{310,} (4) (2010) 833--834.  

\bibitem{Weisstein2011DS} E. W. \href{http://mathworld.wolfram.com/about/author.html}{Weisstein},  
\href{http://mathworld.wolfram.com/DegreeSequence.html}{\textit{Degree Sequence.}} 
From MathWorld---Wolfram Web Resource, 2011. 
 
\bibitem{Weisstein2011GS} E. W. \href{http://mathworld.wolfram.com/about/author.html}{Weisstein},  
\href{http://mathworld.wolfram.com/GraphicSequence.html}{\textit{Graphic Sequence.}}
From MathWorld---Wolfram Web Resource, 2011.

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

\end{thebibliography}

\end{document}

