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

\usepackage{epic}
\usepackage{eepic}

\title{%
Quick 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://people.inf.elte.hu/sopsaai}{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/lulsaai}{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.



A gyakorlatban különböző területeken szükség van objektumok rangsorolására. Ennek egyik elterjedt módszere, hogy az 
objektumokat páronként összehasonlítjuk, és az összehasonlítás eredményeképpen pontokat adunk az objektumoknak, végül pedig 
az objektumokat a kapott pontszámok alapján rangsoroljuk. Például Landau biológiai \cite{Landau1953}, Hakimi kémiai 
\cite{Hakimi1962}, Kim et al. \cite{KimTME2009} és Newman és Barabási \cite{NewmanB2006} hálózati,   
Bozóki, Fülöp, Poesz és Rónyai gazdasági \cite{BozokiFP2011,BozokiFR2010}, 
Liljeros et al. emberi kapcsolatokra vonatkozó \cite{LiljerosEASA2001}, Iványi és Pirzada pedig 
sportbeli \cite{Ivanyi2009,Ivanyi2010,IvanyiP2011,PirzadaIK2011,PirzadaZI2010} alkalmazásokra hivatkoztak. 

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

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

A hasonló feladatokkal kapcsolatban megjegyezzük, hogy mind az irányítatlan, mind pedig az irányított gráfokkal kapcsolatban  
az utóbbi néhány évben is számos cikk és könyvfejezet jelent meg (például \cite{BeregI2008,BrualdiK2009,delGenioKTB2010,
HellK2009,Ivanyi2011AML,KayibiKPI2011,Meierling2009,RodsethST2009,TripathiVW2010,Weisstein2011DS,Weisstein2011GS}, illetve   
\cite{BeasleyBR2009,BozokiFR2010,BuschCJ2010,ErdosMT2010,Frank2011,Ivanyi2009,Ivanyi2010,Ivanyi2011Kyoto,Ivanyi2011Opkut,
IvanyiP2011,KimTME2009,Knuth2011,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,Ivanyi2011Opkut,IvanyiMN2011,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 eleminek 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 $n \geq 3.$ The $n$-regular sequence $b = (b_1\ldots,b_n)$ 
is $n$-good if and only if 
\begin{equation}
\sum _{i=1}^n b_i \quad \mbox{páros}\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.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 HHR-nek (Rendező Havel-Hakimi) nevezzük, mert a 
tétel természetes alkalmazása minden menetben igényli a redukált bemenet rendezését.

A tétel alapján olyan megvalósítás is lehetséges, hogy a fokszámok redukálását a sorozat monotonitását megőrizve végezzük. 
Ekkor az Eltoló Havel-Hakimi algoritmust (HHE) kapjuk.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{tetel-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}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lineáris Erdős-Gallai algoritmus\label{subsec-EGlinearis}}
Recently we could improve this theorem \cite{IvanyiLS2011Acta}. 
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 thesequence $m(q)$ containing pointers.
 
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ős-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 elements of $H$ \\  
\hspace{-7mm}03              \> $H_i = H_{i-1} + q_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} \\
\hspace{-7mm}07 $q_0 = n - 1$                             \` $\rhd$ Line 07: initialization of $b_0$ \\ 
\hspace{-7mm}08 \textbf{for} \= $j = n$ \textbf{downto} $q_1 + 1$ \` $\rhd$ Lines 08--09: setting of some pointers  \\
\hspace{-7mm}09              \> $m_j = 0$ \\
\hspace{-7mm}10 \textbf{for} \= $i = 1$ \textbf{to} $n$         \` $\rhd$ Lines 10--16:  calculation of the pointers \\ 
\hspace{-7mm}11              \> \textbf{if} \= $q_i < q_{i-1}$  \\ 
\hspace{-7mm}12              \>             \> \textbf{for} \= $j = q_{i-1}$ \textbf{downto} $q_i + 1$ \\
\hspace{-7mm}15              \>             \>              \> $m_j = i - 1$ \\
\hspace{-7mm}16              \> $m_{q_i} = i$ \\ 
\hspace{-7mm}17 \textbf{for} \= $j = q_n - 1$ \textbf{downto} $1$  \` $\rhd$ Lines 17--18: setting of some pointers \\
\hspace{-7mm}18              \> $m_j = n - 1$ \\                            
\hspace{-7mm}19 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$            \` $\rhd$ Lines 19--25: test of $q$ \\  
\hspace{-7mm}20              \> \textbf{if} \= $i > m_i$ and $H_i >  i(i - 1) + H_n - H_i$ \\
\hspace{-7mm}21              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}22              \>             \> \textbf{return} $L$ \\           
\hspace{-7mm}23              \> \textbf{if} \= $i \leq m_i$ and $H_i >  i(i - 1) + H_n - H_i$ \\ 
\hspace{-7mm}24              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}25              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}26 $L = \textsc{True}$ \` $\rhd$ Lines 26--27: the program ends with \textsc{True} value  \\
\hspace{-7mm}27 \> \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} \emph{(Móri \cite{Mori2011})}. Ha\label{lemma-korsziv} $n \geq 1,$ akkor az $n$-korlátos 
sorozatok átlagos szivárvány száma 
\begin{equation}
\frac{n^2}{2n - 1}.\label{eq-Mori1}
\end{equation}
\end{lemma}
\begin{proof}
\end{proof}

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

\begin{lemma} \emph{(Móri \cite{Mori2011})}. Ha\label{lemma-szabsziv} $n \geq 1,$ akkor az $n$-szabályos 
sorozatok átlagos szivárvány száma 
\begin{equation}
\frac{n}{2} + \frac{1}{4} + \frac{3}{8n - 4}.
\end{equation}
\end{lemma}
\begin{proof} Egy $n$-szabályos sorozatban $1, \ 2, \ \ldots, \ n$ különböző elem lehet. $n$ különböző elem közül $k$ elemet 
$\textbinom{n}{k}$ féleképpen választhatunk ki. Ha már kiválasztottunk $k$ elemet, akkor ezeket $\textbinom{n - 1}{k - 1}$ 
módon rendezhetjük, hiszen az azonos elemekből álló részsorozatokat elválasztó $k - 1$ helyet a sorozat $n$ eleme közti 
$n - 1$ hely közül kell kiválasztanunk. Figyelembe véve, hogy a \ref{lemma-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, 2007)} 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{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},   
Gráfok előírt fokú pontokkal. \textit{Mat. Lapok} \textbf{11,} (1960) 264--274.

\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, 
\textit{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},    
\textit{On the realizability of a set of integers as degrees of the vertices 
of a simple graph.} J. SIAM Appl. Math. \textbf{10,} (1962) 496--506. 

\bibitem{Hakimi1963} S. L. \href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi},  
\textit{On realizability of a set of integers as degrees of the vertices 
of a linear graph {I}{I}. Uniqueness.} SIAM J. Appl. Math., \textbf{11(1),} (1963) 135--147.

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

\bibitem{HellK2009} P. Hell, D. Kirkpatrick,  
\textit{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},   
\textit{Pontsorozatok ellenőrzése.} In: (szerk. ???) \textit{XXV. Magyar Operációkutatási Konferencia} 
(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},   
\textit{Reconstruction of complete interval tournaments.} 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},     
\textit{Reconstruction of complete interval tournaments. II.} Acta Univ. Sapientiae,  
\href{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{Mathematica}, 
\textbf{2(1),} (2010) 47--71.

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

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

\bibitem{Ivanyi2011Opkut} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},  
\textit{Hiperversenyek helyreállítása.} In: (szerk. ???) \textit{XXIX. Magyar Operációkutatási Konferencia} 
(Balatonőszöd, 2001. október 17--20), 53--53.

\bibitem{Ivanyi2011AML} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
Gyors Erdős-Gallai és Haverl-Hakimi algorithms. \textit{Alk. Mat. Lapok} (benyújtva).

\bibitem{IvanyiMN2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi},   
 \textsc{Madarász, J., Németh, Zs.:} \textit{Algoritmusok hatékonyságának oktatása.} 
 In: (szerk. ???) Informatika a Felsőoktatásban 2011 (Debrecen, 2011. augusztus 24--26), Debrecen, 2011.

\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},     
\textit{Comparison based ranking.} In: 
\href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{Algorithms of Informatics}, Vol. 3, 
ed. by A. Iványi. \href{http://www.antoncom.hu/books.htm}{AnTonCom}, Budapest 2011, 1262--1311.  

\bibitem{Katai2010} I. Kátai,  Szóbeli közlés. 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.} (submiietd).

\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},   
\textsc{\href{http://www.math.sc.edu/~szekely/}{Székely}}, L. A.:  
\href{http://www.renyi.hu/~elp/KTEMS-IOP09.pdf}{\textit{Degree-based}} \textit{graph construction.} 
\textit{J. Physics: Math. Theor. A} \textbf{42(39),} (2009) 392--401.

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

\bibitem{KleitmanW1981} D. J. Kleitman, K. J. Winston,  
\textit{Forests and score vectors.} 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, 
\textit{Rangsorolási algoritmusok elemzése.} TDK dolgozat.   
ELTE TTK, 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{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{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},  \textit{Score sets and kings.} In: 
\href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{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, 
\textit{Enumeration of the degree sequences of non-separable graphs and connected graphs.} 
European J. Comb. \textbf{30(5),} 1309--1319.

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

\bibitem{SierksmaH1991} G. Sierksma, H. Hoogeveen,  
\textit{Seven criteria for integer sequences being graphic.}  
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}, \textit{A zonotope associated with graphical degree sequence}. In: 
Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee. 
DIMACS Series in Discrete Mathematics and Theoretical Computer Science. \textbf{4,} (1991) 555-570.   

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

\bibitem{TripathiV2003} A Tripathi, S. \href{http://www.math.illinois.edu/~sujith/}{Vijay},   
\textit{A note on a theorem of Erd\H os} \& \textit{Gallai.} 
\href{http://www.sciencedirect.com/science/journal/0012365X}{Discrete} 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}{Discrete} Math. \textbf{310(4),} (2010) 833--834.  

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

\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}

Ez itt: EG-szept8


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

\usepackage[latin2]{inputenc}
\frenchspacing

\usepackage{epic}
\usepackage{eepic}



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

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

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

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

\vspace{8mm}
\normalsize
IVÁNYI ANTAL, LUCZ LORÁND, SÓTÉR PÉTER
\end{center}


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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bevezetés\label{sec-Intro}}
A gyakorlatban különböző területeken szükség van objektumok rangsorolására. Ennek egyik elterjedt módszere, hogy az 
objektumokat páronként összehasonlítjuk, és az összehasonlítás eredményeképpen pontokat adunk az objektumoknak, végül pedig 
az objektumokat a kapott pontszámok alapján rangsoroljuk. Például Landau biológiai \cite{Landau1953}, Hakimi kémiai 
\cite{Hakimi1962}, Kim, Toroczkai, Miklós, Erdős és Székely \cite{KimTMESz2009} és Newman és Barabási \cite{NewmanB2006} hálózati,   
Bozóki, Fülöp, Poesz és Rónyai gazdasági \cite{BozokiFP2011,BozokiFR2010} Liljeros et al. emberi kapcsolatokra vonatkozó 
\cite{LiljerosEASA2001}, Iványi et al. pedig sportbeli 
\cite{Ivanyi2009,Ivanyi2010,IvanyiLS2011,IvanyiP2011,KayibiKPI2011,PirzadaIK2011,PirzadaZI2010} alkalmazásokra hivatkoztak. 

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

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

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

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

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

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

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

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

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

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Klasszikus pontos algoritmusok\label{sec-pontos}}
Ebben a részben a témakör két klasszikus algoritmusát ismertetjük.


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

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

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

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

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

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

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

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

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

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

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

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

Bár ez a tétel csak ellenőriz, futási ideje a legjobb $\Theta(n)$ és a legrosszabb $\Theta(n^2)$ 
között változik. A közelmúltban Tripathi et al. \cite{TripathiVW2010} publikáltak a tételre konstruktív bizonyítást, amely 
jó bemenet esetén $O(n^3)$ idő alatt egy megoldást is előállít.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Új pontos algoritmusok\label{sec-ujpontos}}
Ebben a részben a klasszikus algoritmusok néhány gyorsított változatát mutatjuk be.

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

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

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

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



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

A tétel alapján olyan megvalósítás is lehetséges, hogy a fokszámok redukálását a sorozat monotonitását megőrizve végezzük. 
Ekkor az Eltoló Havel-Hakimi algoritmust (HHE) kapjuk.


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Rövidített Erdős-Gallai algoritmus\label{sec-EGS}}
$H_i$ maximális értéke szabályos sorozat esetén $n(n - 1),$ ezért a \ref{tetel-EG}. 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ő lemma.

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

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

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

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

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

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

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

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

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

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

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

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

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

\textit{Munkaváltozók.} $i$ és $j$: ciklusváltozók; \\
$H = (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ős-Gallai-Ugró}$(n,b,L,\gamma )$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $p = n$                                          \` $\rhd$ 01--03. sor: nullamentesítés \\
\hspace{-7mm}02 \textbf{while} \= $b_p = 0$ \\
\hspace{-7mm}03                \> $p = p -1$  \\
\hspace{-7mm}04 $H_1 = b_1$                                 \` $\rhd$ 04--09. sor: paritás ellenőrzése \\
\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$ páratlan \\
\hspace{-7mm}08             \> $L = \textsc{False}$ \\
\hspace{-7mm}09             \>  \textbf{return} $L$  \\
\hspace{-7mm}10 $b_{p + 1} = 0$                        \` $\rhd$ 11--23. sor: fej igényének ellenőrzése \\
\hspace{-7mm}11 $i = 1$ \\
\hspace{-7mm}12 \textbf{while} \= $i \leq p$ és $i(i - 1) < 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}

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

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

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

Ha viszont $i \leq m_i,$ akkor a $C_i$-t definiáló szummát két részre bontjuk: az első részhez a farok azon $b_j$ 
kezdő elemeinek hozzájárulása tartozik, amelyekre teljesül $b_j \geq i,$ a második részhez pedig a többi elem. Legyen 
$q(b) = q = \max _{1 \leq i \leq n} \{i \ | \ i(i - 1) \leq H_i \}.$  
    
\begin{theorem} Ha\label{theorem-EGL} $n \geq 1,$ a $b = (b_1\ldots,b_n)$ $n$-szabályos sorozat akkor és csak 
akkor $n$-jó, ha
\begin{equation}
H_n \quad \textrm{páros,}\label{eq-EGLparity}
\end{equation}
továbbá
\begin{equation}
H_i \leq i(k - 1) + H_n - H_k \quad(i = 1, \ldots, q),\label{eq-EGL}
\end{equation}
ahol
\begin{equation}
k(b) = k =  
\left \{ 
\begin{array}{cc}
m_i, & \mbox{ if } i \leq m_i, \\
i, & \mbox{ if } i > m_i. \\
\end{array}
\right.\label{eq-EGLk}
\end{equation}
\end{theorem}  

\begin{proof} Megmutatjuk, hogy a tételben szereplő feltétel ekvivalens a \ref{tetel-EG}. tétel feltételeivel.

A (\ref{eq-EGLparity}) feltétel pontosan megegyezik az (\ref{eq-EGparity}) feltétellel.

Ha $i \leq m_i,$ akkor
\begin{equation}
H_{i} \leq  i(i - 1) + (m_i - i + 1)i + H_n - H_{m_i} \label{eq-EGLsmalli} 
\end{equation}
és ha $i > m_i,$ akkor 
\begin{equation}
H_i \leq  i(i - 1) + H_n - H_i.\label{eq-EGLlargei} 
\end{equation}

Ha (\ref{eq-EGL-small}) jobb oldalán kiemeljük $i$-t, akkor a 
\begin{equation}
H_i \leq im_i + H_n - H_{m_i}
\end{equation}
egyenlőtlenséget kapjuk. Ha (\ref{eq-EGL-parity})-ba (\ref{eq-EGLk}) alapján behelyettesítjük $k$-t, akkor az 
$i \leq m_i$ esetben (\ref{eq-EGLsmall})-t, az $i > m_i$ esetben pedig (\ref{eq-EGLlarge})-t kapjuk.
\end{proof}  
 

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

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

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

\textit{Munkaváltozók.} $i$ és $j$: ciklusváltozók; \\
$H = (H_1,\ldots,H_n)$: $H_i$ az éppen tesztelt $b$ első $i$ elemének az összege; \\
$m = (m_1,\ldots,m_{n-1})$: $m_i$ a legnagyobb indexű olyan $b_j$ indexe, amely legalább $i$;
$H_0 = 0$: segédváltozó a $H$ sorozat elemeinek kiszámításához; \\
$b_0 = n -1$: segédváltozó az $m$ sorozat elemeinek kiszámításához; \\
$q$: ellenőrzésre eddig az indexig van szükség; \\
$k$: ellenőrzés egyszerűsítéséhez használt változó.

\medskip  
\noindent \textsc{Erdős-Gallai-Lineárisan}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = q = 0$                                            \` $\rhd$ 01. sor: kezdeti értékek beállítása \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$ 02--03. sorok: $H$ elemeinek kiszámítása    \\     
\hspace{-7mm}03              \> $H_i = H_{i-1} + b_i$ \\ 
\hspace{-7mm}04              \> \textbf{if} \= $i(i - 1) < H_i$       \` $\rhd$ 04--05. sorok: $q$ kiszámítása    \\
\hspace{-7mm}05              \>              \> $q = i$   \\
\hspace{-7mm}06 \textbf{if} \= $H_n$ \textrm{ páratlan}    \` $\rhd$ 06--08. sor: paritás ellenőrzése    \\ 
\hspace{-7mm}07             \> $L = \textsc{False}$ \\
\hspace{-7mm}08             \> \textbf{return} \\
\hspace{-7mm}09 $b_0 = n - 1$                             \` $\rhd$ 09. sor: segédváltozó beállítása \\ 
\hspace{-7mm}10 \textbf{for} \= $j = n$ \textbf{downto} $b_1 + 1$ \` $\rhd$ 10--11. sorok: nagy indexű mutatók beállítása \\
\hspace{-7mm}11              \> $m_j = 0$ \\
\hspace{-7mm}12 \textbf{for} \= $i = 1$ \textbf{to} $n$               \` $\rhd$ 12--16. sorok:  mutatók beállítása    \\ 
\hspace{-7mm}13              \> \textbf{if} \= $b_i < b_{i-1}$  \\ 
\hspace{-7mm}14              \>             \> \textbf{for} \= $j = b_{i-1}$ \textbf{downto} $b_i + 1$ \\
\hspace{-7mm}15              \>             \>              \> $m_j = i - 1$ \\
\hspace{-7mm}16              \> $m_{b_i} = i$ \\ 
\hspace{-7mm}17 \textbf{for} \= $j = b_n - 1$ \textbf{downto} $1$  \` $\rhd$ 17--18. sorok: nagy indexű mutatók beállítása \\
\hspace{-7mm}18              \> $m_j = n - 1$ \\                            
\hspace{-7mm}19 \textbf{if} \= $i \leq m_i$                         \` $\rhd$ 19--21. sorok: $k$ beállítása \\ 
\hspace{-7mm}20             \> $k = m_i$ \\
\hspace{-7mm}21 \textbf{else} \= $k = i$ \\
\hspace{-7mm}22 \textbf{for} \= $i = 1$ \textbf{to} $q$            \` $\rhd$ 22--25. sorok: sorozat ellenőrzése \\  
\hspace{-7mm}23              \> \textbf{if} \= $H_i >  i(k - 1) + H_n - H_k$ \\
\hspace{-7mm}24              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}25              \>             \> \textbf{return} $L$ \\           
\hspace{-7mm}26 $L = \textsc{True}$ \` $\rhd$ 26--27. sor: a program \textsc{True} értékkel befejeződik  \\
\hspace{-7mm}27 \> \textbf{return} $L$  \\ 
\end{tabbing}

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

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

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

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

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

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

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

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

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

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

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


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

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


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


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

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


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

\begin{lemma} Ha\label{lemma-kappan} $l, \ m$ és $u$ egész számok, továbbá $l \geq u$ és $1 \geq m,$ akkor az 
$(l,u,m)$-korlátos sorozatok $\kappa(l,u,m)$ száma
\begin{equation}
\kappa(l,u,m) = (u - l + 1)^m.\label{eq-kappan}
\end{equation}
\end{lemma}
\begin{proof} A korlátos sorozatok számára vonatkozó képlet közvetlen adódik abból, hogy a sorozat mind az 
$m$ eleme $u - l  + 1$ lehetséges értéket vehet fel.
\end{proof}

\begin{lemma} Ha\label{lemma-rhon} $1, \ m$ és $u$ egész számok, továbbá $l \geq u$ és $1 \geq m,$ akkor az 
$(l,u,m)$-szabályos sorozatok $\rho(l,u,m)$ száma
\begin{equation}
\rho(l,u,m) = \binom{m + u - l}{m}.\label{eq-rhon}
\end{equation}
\end{lemma}

\begin{proof} Egy $b = (b_1,\ldots,b_m)$ $(l,u,m)$-szabályos sorozat esetén legyen $b' = (b_1',\ldots, b_m')$, ahol 
$b_i' = b_i + m - i$. 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ő $l, \ l  + 1, \ \ldots, \ u + m - 1$ számok 
-- azaz $u + m - l$ szám -- közül $m$ 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ámát 
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{eq-rhonass} 
\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}, \label{eq-rhonbiz}
\end{equation} 
ahonnan (\ref{eq-rhonmon}) és (\ref{eq-rhonlim}) is közvetlenül adódik.

(\ref{eq-rhonass}) belátásához felhasználjuk a Stirling-formula következő alakját \cite{CormenLRS2009}: ha $n \geq 1,$ akkor 
\begin{equation}
n! = \left ( \frac{n}{e} \right)^n \sqrt{2\pi n} e^{\tau_n}\label{eq-Stirling}
\end{equation}
ahol
\begin{equation}
\frac{1}{12n + 1} < \tau _n < \frac{1}{12n}.\label{eq-Stirlingtau}
\end{equation}
\end{proof}

\begin{lemma} \emph{(Ascher \cite{Ascher1987}, Sloane and Pfoffe \cite{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 ( \binom{2n -1}{n} + \binom{n - 1}{\lfloor n \rfloor} \right ).\label{eq-epsen}
\end{equation}
\end{lemma}

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

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

\begin{lemma} Ha\label{lemma-epsntul} $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-epsnlim}
\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-epsnnass} 
\end{equation}
ahol $\delta _3(n)$ és $\delta _4(n)$ monoton csökkenve nullához tartó sorozatok.
\end{lemma}

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

Amint azt a következő állítás és a \ref{fig-parszabarany}. á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}

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

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

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

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

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

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

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



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

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

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

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

\begin{lemma} \emph{(Móri \cite{Mori2011})}. Ha\label{lemma-szabsziv} $n \geq 1,$ akkor az $n$-szabályos 
sorozatok átlagos szivárvány száma 
\begin{equation}
\frac{n}{2} + \frac{1}{4} + \frac{3}{8n - 4}.
\end{equation}
\end{lemma}
\begin{proof} Egy $n$-szabályos sorozatban $1, \ 2, \ \ldots, \ n$ különböző elem lehet. $n$ különböző elem közül $k$ elemet 
$\textbinom{n}{k}$ féleképpen választhatunk ki. Ha már kiválasztottunk $k$ elemet, akkor ezeket $\textbinom{n - 1}{k - 1}$ 
módon rendezhetjük, hiszen az azonos elemekből álló részsorozatokat elválasztó $k - 1$ helyet a sorozat $n$ eleme közti 
$n - 1$ hely közül kell kiválasztanunk. Figyelembe véve, hogy a \ref{lemma-rhon}. lemma szerint az $n$-szabályos sorozatok száma 
$\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}

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

konstans ???
\end{lemma}

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


A jó sorozatok $\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tesztelő algoritmusok\label{sec-teszt}}
Sorozatok megvalósíthatóságának vizsgálata során természetes észrevétel, hogy a $b$ sorozat $i$-hez tartozó fejének $H_i$ 
fokszámigényét részben belső (az adott fejen belüli), részben pedig külső (a fejnek megfelelő farokhoz tartozó) 
fokszámokkal elégítjük ki. 

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Paritás teszt\label{subsec-paritas}}
Első tesztünk az Erdős-Gallai tétel első szükséges feltételén alapul. Nagyon hatékony teszt, mivel 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} Ha\label{lemma-paritas} $n \geq 1$ és $b$ $n$-jó sorozat, akkor
\begin{equation}
H_n \quad \mbox{páros}.\label{eq-parossag}
\end{equation}
\end{lemma}

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

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

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

\textit{Kimenet}. $L$: logikai változó ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy a teszt \textit{nem tudta eldönteni,} hogy $b$ jó-e); \\
$H = (H_1, \ldots, H_n)$: $H_i$ a $b$ sorozat első $i$ elemének összege; \\
$\epsilon$: a vizsgált páros sorozatok  száma. 

\textit{Munkaváltozó.} $i$: ciklusváltozó. \\


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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Pozitív teszt\label{subsec-pozitivteszt}}
A farokban lévő nulla elemek nem növelik a farok párosítási lehetőségeit. Ez az észrevétel lehetővé teszi, 
hogy az $i$-edik elemhez tartozó farok foklekötési lehetőségeire (potenciáljára) $T_i$-nél pontosabb becslést adjunk. 
Ez a teszt a Havel-Hakimi algoritmus első menetének megfelelő ellenőrzést végzi el. 

\begin{corollary} Ha\label{lemma-pozitiv} $b$ $n$-jó sorozat, akkor
\begin{equation}
b_1  \leq p - 1.  \label{eq-pozitiv}
\end{equation}
\end{corollary}

\begin{proof} A (\ref{eq-pozitiv}) egyenlőtlenség azt a követelményt fejezi ki, amelyet a Havel-Hakimi algoritmus az 
első iterációs menetben, illetve az Erdős-Gallai algoritmus a (\ref{eq-EGbinom}) egyenlőtlenség $i = 1$ esetben való 
ellenőrzésével megvalósít.
\end{proof}

A \ref{lemma-pozitiv}. következményen alapuló tesztet a következő algoritmus végzi.

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

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

\textit{Munkaváltozó.} Nincs.


\medskip
\noindent \textsc{Pozitív-teszt}$(n,b,H,T,L,p,\pi)$
\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{if} \= $H_1 > p - 1$ \\
\hspace{-7mm}05             \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $L = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $L$
\end{tabbing}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Binomiális teszt\label{subsec-binom}}
Harmadik tesztünk az Erdős-Gallai tétel másik szükséges feltételének ötletét terjeszti ki. Lényege, hogy a 
fej igényének a fejen belül ki nem elégíthető részét a faroknak, a farok igényének belül ki nem elégíthető részét a fejnek 
kell kielégítenie, végül a teljes sorozat igényét a fej és farok együttműködésével, valamint a fej és a farok belső 
éleivel kell kielégíteni. Az algoritmus nevét arról kapta, hogy a fej és a  
farok belső éleinek a számát egy-egy binomiális együttható segítségével becsüljük. 
Legyen $p$ a $b$ sorozat pozitív elemeinek a száma.

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

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

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

\textit{Bemenet}. $n$: a csúcsok száma $(n \geq 1)$; \\
$b = (b_1, b_2, \ldots, b_n)$: $n$-páros sorozat; \\
$p$: a $b$ sorozat pozitív elemeinek a száma; \\
$H = (H_1, \ldots, H_n)$: $H_i$ a $b$ sorozat első $i$ elemének összege.

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

\textit{Munkaváltozók.} $i$: ciklusváltozó.

\medskip
\noindent \textsc{Binomiális-teszt}$(n,b,H,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $p = n$ \\
\hspace{-7mm}02 \textbf{while} \= $b_p == 0$ \\
\hspace{-7mm}03                \> $p = p - 1$ \\
\hspace{-7mm}04 \textbf{if} \= $p == 1$ \\
\hspace{-7mm}05             \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\               
\hspace{-7mm}07 $H_1 = 0$ \\
\hspace{-7mm}09 \textbf{for} $i = 2$ \= \textbf{to} $p$ \\
\hspace{-7mm}10                      \> $H_i = H_{i - 1} + b_i$ \\
\hspace{-7mm}11 \textbf{for} \= $i = 1$ \textbf{to} $p$ \\
\hspace{-7mm}12              \> \textbf{if} \> $2H_i > i(i - 1) + H_p$ \\
\hspace{-7mm}13              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}14              \>             \> \textbf{return} $H,T,L$ \\
\hspace{-7mm}15 $L = \textsc{True}$ \\
\hspace{-7mm}16 \textbf{return} $H,L$
\end{tabbing}

Az algoritmus azért kezdi $b$ végénél $p$ meghatározását, mert a 
\ref{lemma-nullaatl}. lemma szerint kevés nulla várható a sorozatokban. 

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

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 futási ideje szempontjából.  

Megjegyezzük, hogy \textsc{Binomiális-teszt} $i = 1$ esetén elvégzi \textsc{Pozitív-teszt} munkáját, ezért 
a \textsc{Pozitív-teszt} algoritmusra nincs szükségünk.   

Felmerült, hogy a \textsc{Binomiális-teszt} algoritmust is csak az ellenőrző pontokon alkalmazzuk, 
a szimulációs kísérletek azonban azt mutatták, hogy ezzel csökkenne az algoritmus hatékonysága. 
A rövidített változat ($n$ helyett csak $g$-ig végezzük az ellenőrzést) azonban nyilván igaz. 

$n$ helyett $p$ viszont gyengítené az algoritmust, mert például a rossz $(2,2,0)$ sorozatot \textit{nem} szűrné ki. Mivel azonban 
mi csak a páros nullamentes algoritmusokat vizsgáljuk, a $2,2,0$ és hasonló sorozatokat egyetlen algoritmusunk sem 
teszteli (mert ezeket már a sorozatok előállítása során kiszűrjük).  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Haszontalan teszt\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} Ha\label{lemma-hasz} $b$ $n$-jó sorozat, akkor
\begin{equation} 
H_i \leq \min \left ( i(i - 1), H_i \right ) + T_i  \quad (i = 1, \ldots, n - 1).\label{eq-hasz}
\end{equation}
\end{lemma}

\begin{proof} A (\ref{eq-hasz}) egyenlőtlenség bal oldalán szereplő $H_i$ a $b$ sorozat fejének fokszámigénye. 
Az egyenlőtlenség jobb oldalán $i(i - 1)$ a fejen belüli csúcspárok számából adódó korlát, míg $H_i$ abból adódik, 
hogy a fej belső éleihez 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 a minimum már $T_i$ nélkül is biztosítja 
az egyenlőtlenség teljesülését. 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 az 
\ref{sec-ujpontos}. részben a \ref{lemma-EGS}. lemmát), másrészt további, 
\textit{hasznos} közelítő algoritmusoknak lesz a kiindulási pontja.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Rövidített és ugró binomiális teszt\label{subsec-rovidbinom}}


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

\begin{lemma} Ha\label{lemma-fejfelez} $n \geq 1$ és $b$ $n$-jó sorozat, akkor
\begin{equation}
H_i  \leq 2\min(X_{i,1} + X_{i,2} , + X_{i,3} + \min(T_i, i(p - i)) \quad (i = 1, \ldots, p), 
\end{equation}
ahol
\begin{equation}
X_{i,1} \leq \min(H_{h_i},T_n - T_{h_i},h_i(p - i)),\label{eq-X1}
\end{equation}
\begin{equation}
X_{i,2} \leq \min(H_i - H_{h_i},T_n - T_{h_i},(i - h_i)(p - i))\label{eq-X2}
\end{equation}
és
\begin{equation}
X_{i,3} = \min(h_i(h_i - 1),H_i - H_{h_i} - X_{i,1}/2).\label{eq-X3} 
\end{equation}
\end{lemma} 

\begin{proof} Legyen $G$ a $b$ sorozatot megvalósító $G$ gráf. Ekkor az $i$ indexhez tartozó fej $H_i$ fokszámösszegét lekötő 
éleinek halmazát öt részhalmazra osztjuk: a fej eleje és a farok, a fej vége és a farok közötti, a fej két része közötti, 
valamint a fej részein belüli élekre. Az egyes részhalmazokba tartozó élek száma legyen 
rendre $X_{i,1}, \ \ldots, X_{i,5}.$  

$X_{i,1}$ legfeljebb a fej elemeinek $H_{h_i}$ összege, legfeljebb a farok elemeinek $T_n - T_{h_i}$ összege, és legfeljebb a 
fej elejéből és a farokból képezhető párok $h_{h_i}(n - h_i)$ szorzata lehet, azaz a (\ref{eq-X1}) 
egyenlőtlenségnek teljesednie kell. 

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

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

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

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

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

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

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

\textit{Kimenet}. $L$: logikai változó ($L = \textsc{False}$ azt jelzi, hogy $b$ biztosan nem jó, míg 
$L = \textsc{True}$ azt mutatja, hogy a teszt \textit{nem tudta eldönteni,} hogy $b$ jó-e). \\
$\beta$: a megvizsgált pozitív sorozatok közül elfogadott sorozatok száma.

\textit{Munkaváltozók}. $i$: ciklusváltozó \\
$X = (X_1,X_2,X_3)$: ahol $X_1$ a fej elejének és végének közös kapacitására adott felső korlát, $X_2$ a fej elejének 
belső kapacitására, $X_3$ pedig a fej végének belső kapacitására adott felső korlát; \\
$p$: a $b$ sorozatban lévő lévő pozitív elemek összege. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) \textsc{Binomiális-teszt}

3) \textsc{Fejfelező-teszt}

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

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

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

\begin{figure}[!ht]
\begin{small}
\begin{center}
\begin{tabular}{||c|c|c|c|c|c||}  \hline \hline
$n$  &   $\zeta(n)$ & $\beta(n)$  &$\varphi(n)$     & $\gamma(n)$  & $\gamma(n+1)/\gamma(n)$    \\ \hline \hline
$1$  &$\mathbf{0}$ & $\mathbf{1}$ &$\mathbf{0}$     & $\mathbf{1}$ & $2.000000$\\ \hline
$2$  &$\mathbf{1}$ &$\mathbf{2}$  &$\mathbf{2}$     & $\mathbf{2}$ & $2.000000$\\ \hline
$3$  &$\mathbf{4}$ &$\mathbf{4}$  & $\mathbf{4}$    & $\mathbf{4}$ & $2.750000$      \\ \hline
$4$  &$\mathbf{11}$&$\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$     &$343$            &$\mathbf{342}$ & $3.546784$    \\ \hline 
$8$  &   $???$     &    $1256$    &   $???$         &   $1213$      & $3.595218$\\ \hline 
$9$  &   $???$     &    $4577$    &   $???$         &  $4361$       & $3.672552$ \\ \hline 
$10$ &   $???$     &     $17040$  &   $???$         & $16016$       & $3.705544$\\ \hline 
$11$ &   $???$     &     $63944$  &   $???$         &  $59348$      & $3.742620$ \\ \hline 
$12$ &   $???$     &   $242218$   &   $???$         &  $222117$     & $3.765200$ \\ \hline 
$13$ &   $???$     & $922369$     &   $???$         & $836315$      & $3.786674$ \\ \hline 
$14$ &   $???$     &$???$         &   $???$         & $3166852$     & $3.802710$ \\ \hline 
$15$ &   $???$     &    $???$     &   $???$         &   $12042620$  & $3.817067$ \\ \hline 
$16$ &   $???$     & $???$        &   $???$         &   $45967479$  & $3.828918$ \\ \hline 
$17$ &   $???$     &    $???$     &   $???$         & $176005709$   & $3.839418$ \\ \hline 
$18$ &   $???$     &    $???$     &   $???$         & $675759564$   & $3.848517$ \\ \hline 
$19$ &   $???$     &    $???$     &   $???$         & $2600672458$  & $3.856630$ \\ \hline 
$20$ &   $???$     &    $???$     &   $???$         & $10029832754$ & $3.863844$  \\ \hline 
$21$ &   $???$     &   $???$      &   $???$         & $38753710486$ & $3.870343$ \\ \hline 
$22$ &   $???$     &   $???$      &   $???$         &$149990133774$       & $3.876212$ \\ \hline 
$23$ &   $???$     &   $???$      &   $???$         &$581393603996$       & $3.881553$\\ \hline 
$24$ &   $???$     &   $???$      &   $???$         &$2 256 710 139 346$  & $3.886431$        \\ \hline 
$25$ &   $???$     &   $???$      &   $??$          &$8 770 547 818 956$  & $3.890907$      \\ \hline 
$26$ &   $???$     &   $???$      &   $???$         &$34 125 389 919 850$ & $3.895031$\\ \hline 
$27$ &   $???$     &   $???$      &   $???$         &$132 919 443 189 544$& $3.897978$        \\ \hline 
$28$ &   $???$     &   $???$      &   $???$         &$518 232 001 761 434$& $3.898843$      \\ \hline \hline
\end{tabular}
\caption{Nullamentes, binomiális, fejfelező és jó sorozatok száma, valamint a jó sorozatok szomszédos helyeken 
vett értékeinek hányadosa.\label{fig-sorozatszam}}
\end{center}
\end{small}
\end{figure} 


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

\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||c|c|c|c|c||}  \hline \hline
$n$ &$\zeta(n)/\rho(n)$& $\beta(n)/\rho(n)$&$\varphi(n)/\rho(n)$&$\gamma(n)/\rho(n)$ \\ \hline \hline
$1$ &$0$               &$1.00000$          &$1.00000$           &$1.00000$   \\ \hline
$2$ &$0.33333$         &$0.66667$          &$0.66667$           &$0.66667$    \\ \hline
$3$ &$0.40000$         &$0.40000$          &$0.40000$           &$0.40000$     \\ \hline
$4$ &$0.31429$         &$0.31429$          &$0.31429$           &$0.31429$   \\ \hline
$5$ &$???$             &$0.24603$          &$0.24603$           &$0.24603$   \\ \hline
$6$ &$???$             &$0.22294$          &$0.22078$           &$0.22078$   \\ \hline 
$7$ &$???$             &$0.20338$          &$0.19988$           &$0.19930$   \\ \hline 
$8$ &$???$             &$0.19518$          &$???$               &$0.18850$ \\ \hline 
$9$ &$???$             &$0.18828$          &$???$               &$0.17939$ \\ \hline 
$10$&$???$             &$0.18446$          &$???$               &$0.17337$      \\ \hline 
$11$&$???$             &$0.18129$          & $???$              &$0.16826$      \\ \hline 
$12$&$???$             &$0.17914$          &$???$               &$0.16428$ \\ \hline 
$13$&$???$             &$???$              &$???$               &$0.16082$ \\ \hline 
$14$&$???$             &$???$              &$???$               &$0.15788$ \\ \hline 
$15$&$???$             &$???$              &$???$               &$0.15527$ \\ \hline 
$16$&$???$             &$???$              &$???$               &$0.15295$ \\ \hline 
$17$&$???$             &$???$              &$???$               &$0.15084$ \\ \hline 
$18$&$???$             &$???$              &$???$               &$0.14893$ \\ \hline 
$19$&$???$             &$???$              &$???$               &$0.14716$\\ \hline 
$20$&$???$             &$???$              &$???$               &$0.14552$\\ \hline 
$21$&$???$             &$???$              &$???$               &$0.14400$\\ \hline 
$22$&$???$             &$???$              &$???$               &$0.14257$\\ \hline 
$23$&$???$             &$???$              &$???$               &$0.14123$\\ \hline 
$24$&$???$             &$???$              &$???$               &$0.13996$ \\ \hline 
$25$&$???$             &$???$              &$???$               &$???$\\ \hline \hline
\end{tabular}
\caption{A nullamentes, binomiális, fejtesztelt és jó sorozatok számának részaránya a szabályos 
sorozatokhoz viszonyítva.\label{fig-kozrelativ}}
\end{center}
\end{footnotesize} 
\end{figure}

A \ref{fig-kozido}. ábra a közelítő algoritmusok elemenkénti átlagos futási idejét és műveletszámát tartalmazza. 
Az algoritmusok bemenete az összes páros nullamentes sorozat volt. 
A mikromásodpercben mért idő és a műveletszám is tartalmazza a sorozatok előállítására fordított időt és műveletszámot is.
  

\begin{figure}[!ht]
\begin{small}
\begin{center}
\begin{tabular}{||c|c|c|c|c||}  \hline \hline
$n$  & \textsc{Binomiális}, $\mu$s & \textsc{Binomiális}, művelet & \textsc{Fejfelező}, $\mu$s &\textsc{Fejfelező}, művelet   \\ \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 \hline
\end{tabular}
\caption{Közelítő algoritmusok elemenkénti átlagos műveletszáma.\label{fig-kozido}}
\end{center} 
\end{small}
\end{figure}

Ha $n = 2,$ akkor (\ref{eq-rhon}) 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 $\epsilon(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 jó, így $\varphi(3) = \tau(3) = \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 jó: 
(3,3,3,3), (3,3,2,2), (3,2,2,1), (3,1,1,1,), (2,2,2,2), (2,2,2,0), (2,2,1,1), (2,1,1,0), (1,1,1,1), (1,1,0,0) és (0,0,0,0). 
A 19 páros sorozat közül \textsc{Binomiális-teszt} is kizárja azt a nyolc sorozatot, amelyeket az \textsc{Erdős-Gallai} 
kizárna, így $\beta(4) = \gamma(4) = \varphi(4) = \gamma(4) = 11.$ 

A $\rho(5) = 126$ szabályos sorozat közül $\epsilon(5) = 66$ a páros, ezek között pedig $\beta(5) = 31$ 
a binomiális. Ezek a sorozatok mind jók, azaz $\varphi(5) = \tau(5) = \gamma(5) = 31.$ 

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


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

A \ref{fig-sorozatszam}. ábrán minden sorban az első pontos értéket félkövéren írtuk. Eszerint $n \leq 4$ esetén 
$\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.

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


A \ref{fig-kozrelativ}. ábrán $\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}. A többi értéket mi határoztuk meg: sem $\rho(25),\ldots\rho(40),$ 
sem $\epsilon(24),\ldots,\epsilon(40),$ sem a $\beta(n),$ $\pi(n),$ $\varphi(n)$ és $(\tau(n)$ értékek nem szerepelnek az EIS-ben. 

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

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

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

A pontos algoritmusok sorozatonkénti átlagos futási idejét $n$ függvényében mikromásodpercben az alábbi 
\ref{fig-pontosido}. ábra tartalmazza. Az algoritmusok csak a páros, nullamentes sorozatokat vizsgálták. 
A futási idő tartalmazza a sorozatok előállítási idejét is sorozatok előállítási idejét


\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||c|c|c|c|c|c|||}  \hline \hline
$n$  &      HH  &  HHE    &   EG      & EGU   &  EGL        \\ \hline \hline
$1$  &    ???   &  ???    &   ???     & ???   &  ???     \\ \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 \hline
\end{tabular}
\caption{Pontos algoritmusok elemenkénti átlagos futási ideje műveletszámban.\label{fig-pontosido}}
\end{center} 
\end{footnotesize}
\end{figure}

A következő pontos algoritmusokat vizsgáljuk:

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

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

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

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

5) EGL: Erdős-Gallai algoritmus ugrásokkal lineárisan (EGL).
  
A pontos algoritmusok sorozatonkénti átlagos futási idejét $n$ függvényében mikromásodpercben a \ref{fig-pontosido}. ábra 
tartalmazza. 


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

\begin{figure}[!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{Az \textsc{EG-Lineárisan} algoritmus elemenkénti futási ideje műveletszámban kifejezve.\label{fig-EG-Lineárisan}}
\end{center} 
\end{footnotesize}
\end{figure}

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

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


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


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

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

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

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

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

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

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

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

Nézzünk egy példát. Legyen $n = 6.$ Ekkor a most bizonyított \ref{corollary-rho1}. következmény szerint az  
$(1,5,6)$-szabályos sorozatok száma $\binom{10}{6} = = 210.$ Tegyük fel, hogy a 210 sorozatot tartalmazó halmazt 
8 hasonló méretű szeletre akarjuk bontani. Ekkor egy szelet átlagos mérete 
210/8 = 26.25 sorozat. Ennek felső egész része 27. Ez lesz a szeletek maximális megengedett mérete. A 210  
$(1,5,6)$-szabályos sorozat kezdőelem szerinti megoszlását a \ref{fig-rho1-6elso}. ábra tartalmazza. 

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,6)} = \binom{4 + i}{5}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $6$      \\ \hline
$3$  & $21$     \\ \hline
$4$  & $56$  \\ \hline
$5$  & $126$      \\ \hline \hline
\end{tabular}
\caption{Az $(1,5,6$-szabályos sorozatok megoszlása kezdőelem szerint.\label{fig-rho1-6elso}}
\end{center} 
\end{figure}

Mivel $1 + 6 \leq 27$ és $1 + 6 + 21 \geq 27,$ az 1-gyel és 2-vel kezdődő sorozatok kerülnek az S$_1$ szeletbe. Mivel 
$21 \leq 27$ és $21 + 56 \geq 27,$ a 3-mal kezdődő sorozatok alkotják az S$_2$ szeletet. Mivel  $\lceil 56/27 \rceil = 3,$ 
a 4-gyel kezdődő sorozatokat legalább 3 szeletre bontjuk. Végül $\lceil 126/27 \rceil = 5,$ így az 
öttel kezdődő sorozatokhoz legalább 5 szeletet rendelünk. Ez idáig legalább 10 szelet. 

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,5)} = \binom{4 + i}{5}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $5$      \\ \hline
$3$  & $15$     \\ \hline
$4$  & $35$  \\ \hline \hline
\end{tabular}
\caption{A 4-gyel kezdődő $(1,4,6$-szabályos sorozatok megoszlása második elemük szerint.\label{fig-rho1-4masodik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-4masodik}. ábra a 4-gyel kezdődő, $(1,4,6)$ sorozatok számának a második elem szerinti eloszlását mutatja. 
Eszerint az S$_3$ szeletbe a $(4,1),$ $(4,2)$ és $(4,3)$ kezdetű sorozatok kerülnek (összesen 21 sorozat), míg a $(4,4)$ 
kezdetű sorozatok legalább két szeletet elfoglalnak. 

A \ref{fig-rho1-4masodik}. ábra mutatja a $(4,4)$-gyel kezdődő sorozatok harmadik elem szerinti eloszlását.

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,4)} = \binom{2 + i}{3}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $4$      \\ \hline
$3$  & $10$     \\ \hline
$4$  & $20$  \\ \hline \hline
\end{tabular}
\caption{A $(4,4)$-gyel kezdődő, $(1,4,6$-szabályos sorozatok megoszlása harmadik elemük szerint.\label{fig-rho1-4masodik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-4masodik}. ábra alapján az S$_4$ szeletbe a $(4,4,1),$ $(4,4,2)$ és $(4,4,3)$ kezdetű, míg az S$_5$ szeletbe 
a $(4,4,4)$ kezdetű sorozatok kerülnek. 

A \ref{fig-rho1-5masodik}. ábra mutatja az 5-tel kezdődő $(1,5,6)$-szabályos sorozatok második elem szerinti eloszlását. 

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,4)} = \binom{3 + i}{4}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $5$      \\ \hline
$3$  & $15$     \\ \hline
$4$  & $35$     \\ \hline
$5$  & $70$  \\ \hline \hline
\end{tabular}
\caption{Az (5)-tel kezdődő $(1,5,5)$-szabályos sorozatok megoszlása masodik elemük szerint.\label{fig-rho1-5masodik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-5masodik}. ábra alapján az S$_6$ szeletbe az $(5,1),$ $(5,2)$ és $(5,3)$ kezdetű sorozatok (összesen 21 sorozat) 
kerülnek. A \ref{fig-rho1-54harmadik}. ábra az $(5,4)$ kezdetű sorozatok harmadik elem szerinti eloszlását mutatja.

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,3)} = \binom{2 + i}{3}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $4$      \\ \hline
$3$  & $10$     \\ \hline
$4$  & $20$     \\ \hline \hline
\end{tabular}
\caption{Az (5,4)-gyel kezdődő $(1,4,4)$-szabályos sorozatok megoszlása harmadik elemük szerint.\label{fig-rho1-54harmadik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-54harmadik}. ábra szerint az S$_7$ szelet az $(5,4,1),$ $(5,4,2)$ és $(5.4,3),$ míg az S$_8$ szelet az $(5,4,4)$ 
kezdetű sorozatokat tartalmazza. A \ref{fig-rho1-54harmadik}. ábra az $(5,5)$-tel kezdődő sorozatok harmadik elem 
szerinti megoszlását mutatja.  

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,3)} = \binom{2 + i}{3}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $4$      \\ \hline
$3$  & $10$     \\ \hline
$4$  & $20$     \\ \hline
$5$  & $35$     \\ \hline \hline
\end{tabular}
\caption{Az (5,5)-tel kezdődő $(1,5,4)$-szabályos sorozatok megoszlása harmadik elemük szerint.\label{fig-rho1-55harmadik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-55harmadik}. ábra szerint az S$_9$ szelet az $(5,5,1),$ $(5,5,2)$ és $(5,5,3)$ kezdetű, az S$_10$ szelet pedig 
az $(5,5,4)$ kezdetű sorozatokat tartalmazza. A \ref{fig-rho1-555negyedik}. ábra az $(5,5,5)$-tel kezdetű sorozatok 
negyedik elem szerint megoszlását mutatja.

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,2)} = \binom{1 + i}{2}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $3$      \\ \hline
$3$  & $6$     \\ \hline
$4$  & $10$     \\ \hline 
$5$  & $15$     \\ \hline \hline
\end{tabular}
\caption{Az (5,4)-gyel kezdődő $(1,5,3)$-szabályos sorozatok megoszlása a harmadik elem szerint.\label{fig-rho1-555negyedik}}
\end{center} 
\end{figure}

A \ref{fig-rho1-555negyedik}. ábra szerint az S$_{11}$ szelet az $(5,5,5,1),$ $(5,5,5,2),$ $(5,5,5,3)$ és $(5,5,5,4)$ kezdetű 
sorozatokat, míg az S$(_{12}$ szelet az $(5,5,5,5)$ kezdetű sorozatokat tartalmazza.

A \ref{fig-rho1-6osszesites}. ábra az $(1,5,6)$-szabályos sorozatok 12 szeletre bontását mutatja.

\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c|c||}  \hline \hline
$S_i$  & szelet kezdő sorozata & szelet elemszáma  \\ \hline \hline
$S_1$  & $(2,2,2,2,2,2)$ & 7    \\ \hline
$S_2$  & $(3,3,3,3,3,3)$ & 21    \\ \hline
$S_3$  & $(4,3,3,3,3,3)$ & 21    \\ \hline
$S_4$  & $(4,4,3,3,3,3)$ & 15    \\ \hline
$S_5$  & $(4,4,4,4,4,4)$ & 20  \\ \hline
$S_6$  & $(5,3,3,3,3,3)$ & 21     \\ \hline 
$S_7$  & $(5,4,3,3,3,3)$ & 15    \\ \hline
$S_8$  & $(5,4,4,4,4,4)$ & 20    \\ \hline
$S_9$  & $(5,5,3,3,3,3)$ & 15     \\ \hline
$S_{10}$ & $(5,5,4,4,4,4)$ & 20     \\ \hline
$S_{11}$ & $(5,5,5,4,4,4)$ & 20 \\ \hline
$S_{12}$ & $(5,5,5,5,5,5)$ & 15  \\ \hline \hline
\end{tabular}
\caption{A nullamentes $6$-szabályos sorozatok felbontása 12 szeletre.\label{fig-rho1-6osszesites}}
\end{center}  
\end{figure}

Most tekintsünk egy másik példát: legyen $n = 29.$ Az $n = 28$ esetben szerzett tapasztalatok alapján feltesszük, 
hogy a tiszta futási idő összesen 2500 nap lesz. Feltételezve, hogy a gépek egy részét csak éjszakára kapjuk meg, 
legyen egy szelet maximális futási ideje 12 óra. Ekkor egyenletes eloszlás mellett 5000 szelet lenne. 

A $29$-szabályos, nullamentes sorozatok száma a \ref{corollary-rho1}. következmény és a Stirling formula szerint 
\begin{equation}
\nu{(1,28,29)} = \binom{56}{29} = \frac{56!}{29!27!} \sim  \left( \frac{56}{e} \right )^{56} \left(\frac{e}{29} \right )^{29}  
\left( \frac{e}{27} \right)^{27} \left (\frac{\sqrt{2 \pi 56}}{\sqrt{2\pi 29} \sqrt{2\pi 27}}  \right) .
\end{equation}

 A ??? nullamentes, $(1,28,29)$-szabályos sorozat kezdőelem szerinti megoszlását a \ref{fig-rho1-29elso}. ábra tartalmazza.


\begin{figure}[!th]
\begin{center}
\begin{tabular}{||c|c||}  \hline \hline
$i$  & $\rho{(1,i,29)} = \binom{27 + i}{28}$  \\ \hline \hline
$1$  & $1$     \\ \hline
$2$  & $29$      \\ \hline
$3$  & $435$     \\ \hline
$4$  & $4495$  \\ \hline
$5$  & $81840$      \\ \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
$23$  & $???$     \\ \hline
$24$  & $???$  \\ \hline
$25$  & $???$      \\ \hline
$26$  & $???$     \\ \hline
$27$  & $???$      \\ \hline
$28$  & $???$     \\ \hline \hline
\end{tabular}
\caption{A $(1,28,29)$-szabályos sorozatok megoszlása kezdőelem szerint.\label{fig-rho1-29elso}}
\end{center} 
\end{figure} 

\textbf{???}


A $\gamma(n)$ függvény nagyságrendjére vonatkozó legpontosabb eredmény Jason Matthew Burnsnek Richard P. Stanley 
témavezetésével készített és a Massachusetts Institute of Technology Matematikai Tanszékén 2007-ben megvédett 
doktori értekezésében található. Eszerint léteznek olyan pozitív $c,$ $C$ és $k$ állandók, hogy a jó sorozatok  
$\gamma(n)$ száma a következő korlátok közé esik:
\begin{equation}
\frac{c4^n}{n} < \gamma(n) <  \frac{C4^n}{(\log n)^k \sqrt{n}} \ . \label{eq-Burns}
\end{equation}

Tegyük fel, hogy a felső becslés nagyságrendje alkalmas $k$ esetén pontos, azaz léteznek olyan pozitív $C$ és $k_n$ számok, hogy 
\begin{equation}
\gamma(n)=\frac{C 4^n}{(\log n)^{k_n} \sqrt{n}}+o\left (\frac{4^n}{(\log n)^{k_n} \sqrt{n}} \right),\label{eq-Burnsgamma}
\end{equation}
ahol $n$ növekedtével a $k_n$ sorozat konvergens.

Ekkor 
\begin{equation}
\frac{\gamma(n + 1)}{\gamma(n)} = 
4 \ \frac{\sqrt{n}}{\sqrt{n + 1}} \ \frac{(\log n)^k_n}{(\log(n+1))^k_n} ,\label{eq-Burnsratio}
\end{equation}

ahonnan a $k_{n+1} = k_n = k$ helyettesítéssel azt kapjuk, hogy
\begin{equation}
k = \frac{\log{\frac{\gamma(n + 1)}{\gamma(n)}} - \log{4} - \log{\frac{\sqrt{n}}{\sqrt{n + 1}}}}{\log{\frac{\log n}{\log(n + 1)}}}.
\end{equation}

A \ref{fig-k}. ábra $k$ számításának részeredményeit tartalmazza. 

\begin{figure}[!th]
\begin{scriptsize}
\begin{center}
\begin{tabular}{||c|c|c|c|c||}  \hline \hline
$n$  & $\ln{\frac{\gamma(n + 1)}{\gamma(n)}}$ & $\ln{\frac{\sqrt{n}}{\sqrt{n + 1}}}$  
& $\ln{\frac{\ln n}{\ln(n + 1)}}$ & $k$    \\ \hline \hline
$2$    &  0.3010   & 0.0880    &  -0.2000  & 1.064820717840770  \\ \hline
$3$    &  0.4393   & 0.0625    &  -0.1010  & 0.992544624686593     \\ \hline
$4$    &  0.4500   & 0.0485    &  -0.0649  & 1.598857474425710 \\ \hline
$5$    &  0.5172   & 0.0396    &  -0.0466  & 0.970505819319945     \\ \hline
$6$    &  0.5254   & 0.0335    &  -0.0358  & 1.204156239958088   \\ \hline
$7$    &  0.5496   & 0.0290    &  -0.0288  & 0.805904015852462   \\ \hline
$8$    &  0.5557   & 0.0256    &  -0.0240  & 0.867547492228616  \\ \hline
$9$    &  0.5650   & 0.0229    &  -0.0204  & 0.698741682404903    \\ \hline
$10$   &  0.5688   & 0.0207    &  -0.0176  & 0.710301436698686  \\ \hline
$11$   &  0.5732   & 0.0189    &  -0.0155  & 0.645354379756533  \\ \hline
$12$   &  0.5758   & 0.0174    &  -0.0137  & 0.645728379631260    \\ \hline
$13$   &  0.5783   & 0.0161    &  -0.0124  & 0.623261906868982   \\ \hline
$14$   &  0.5801   & 0.0150    &  -0.0113  & 0.623236569060196     \\ \hline
$15$   &  0.5817   & 0.0140    &  -0.0101  & 0.617468512786572    \\ \hline
$16$   &  0.5831   & 0.0132    &  -0.0094  & 0.619497652173067    \\ \hline
$17$   &  0.5843   & 0.0124    &  -0.0087  & 0.620531345029615     \\ \hline
$18$   &  0.5853   & 0.0117    &  -0.0081  & 0.624435032861388  \\ \hline
$19$   &  0.5862   & 0.0111    &  -0.0075  & 0.628464622512213    \\ \hline
$20$   &  0.5870   & 0.0106    &  -0.0070  & 0.633641383390237   \\ \hline
$21$   &  0.5877   & 0.0101    &  -0.0067  & 0.639087464420730    \\ \hline
$22$   &  0.5884   & 0.0097    &  -0.0062  & 0.645030554474696   \\ \hline
$23$   &  0.5891   & 0.0092    &  -0.0059  & 0.651169668041924  \\ \hline
$24$   &   ???     &  ???      &    ???    &    ???             \\ \hline
$25$   &   ???     &           &    ???    &    ???  \\ \hline \hline
\end{tabular}
\caption{$k$ becslése.\label{fig-k}}
\end{center} 
\end{scriptsize}
\end{figure}

A \ref{fig-k}. ábra szerint az első négy oszlop szigorúan monoton (ami a megfelelő képletek alapján természetes), míg a 
$k$ értékekre $(n = 2)$-től $(n = 13)$-ig az jellemző, hogy a páratlan $n$-hez tartozó $k$ értékek \textit{kisebbek} a szomszédos 
$n - 1$ és $n + 1$ értékhez tartozó $k$-nál. Ha pedig $n \geq 16,$ akkor a $k$ érték \textit{nagyobb}, mint az 
$n - 1$ csúcsszámhoz tartozó $k.$

Hasonló lokális minimumot találtak például a \cite{IvanyiK2011} cikk szerzői véletlen mátrixok vizsgálata során. 

 
\bigskip
\noindent \small \textbf{Köszönetnyilvánítás.} Authors thank program designer Antal S\'andor (E\"otv\"os Lor\'and University, 
Faculty of (Informatics) his help in solution of technical problems of the parallel computations,  and
the participation of Ádám Mányoki (TFM World Hosting) in the timeconsuming machine experiments.
The European Union and the European Social Fund have provided financial support to the project 
under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003.


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

\begin{footnotesize}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\bibitem{IvanyiLS2011AML} A. Iványi, L. Lucz, P. Sótér, \textit{Quick Erdős-Gallai tests.} 
(Hungarian, (submitted).

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

\bibitem{IvanyiLS2011} A. Iványi, L. Lucz, \textit{Linear Erdős-Gallai test.} 
\textit{Combinatorica} (submitted).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\bibitem{Lovasz2007} \textsc{Lovász, L.:}  \textit{Combinatorial Problems and Exercises} (corrected version of 
the second edition).  AMS Chelsea Publishing, Boston, 2007. 
Magyarul: \textit{Kombinatorikai problémák és feladatok.} Typotex, Budapest, 1999.
 
\bibitem{Meierling2009} \textsc{Meierling, D., Volkmann, L.:} \textit{A remark on degree sequences of multigraphs.} 
Math. Methods Oper. Res. \textbf{69(2),} (2009) 369--374. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\end{footnotesize}

\end{thebibliography}

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

\noindent IVÁNYI ANTAL \\
tony@compalg.inf.elte.hu \\ \\
LUCZ LORÁND \\
lorand.lucz@gmail.com \\ \\
SÓTÉR PÉTER \\
mapoleon@freemail.hu  \\ \\
Eötvös Loránd Tudományegyetem \\
Informatikai Kar \\
1117 Budapest, Pázmány Péter sétány 1/C \\


\vspace{4mm}
Budapest, 2011. szeptember 7.

\begin{center}
\vspace{6mm}

LINEAR ERDŐS-GALLAI TEST

\vspace{4mm}
\textsc{ANTAL IVÁNYI, LORÁND LUCZ, PÉTER SÓTÉR}
\end{center}

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

\end{document}

