\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
MULTIGRÁFOK FOKSOROZATAI 

\vspace{8mm}
\normalsize
IVÁNYI ANTAL (2012. január 5b.)
\end{center}


\short{%
IVÁNYI ANTAL, LUCZ LORÁND
}{%
\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 és 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. 1974-ben Chungphaisan \cite{Chungphaisan1974} kiterjesztette 
a csúcspárok között legfeljebb $b \geq 1$ élet tartalmazó multigráfokra mind a Havel-Hakimi, mind pedig at Erdős-Gallai tételt. 
Ezeknek az ismert algoritmusoknak a legrosszabb futási ideje legalább négyzetes. Cikkünkben bemutatjuk a Chungphaisan-Erdős-Gallai 
algoritmus lineáris változatát és annak gyorsított változatait. A Havel-Hakimi algoritmusnak olyan változatát mutatjuk be, amely 
$1 \leq b \leq 2$ esetén lineáris.    
\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,IvanyiLMS2011Acta,IvanyiP2011,KayibiKPI2011,PirzadaIK2011,PirzadaZI2010} alkalmazásokra hivatkoztak. 

Legyenek $a, \ b$ és $n$ egészek, $n \geq 1$ és $b \geq a \geq 0.$ Az $(a,b,n)$\textit{-gráfok} olyan hurokmentes gráfok, 
melyek csúcshalmaza $V = \{v_1,\ldots,v_n \}$ és a a különböző $v_i$ és $v_j$ csúcsok legalább $a$ és legfeljebb $b$ éllel vannak 
összekötve. Eszerint az \textit{egyszerű irányítatlan gráfok} $(0,1,n)$-gráfok, míg az \textit{egyszerű irányított gráfok} 
(tournamentek) $(1,1,n)$-gráfok. 

Irányított gráfok esetén ha $v_i$ és $v_j$ összehasonlításakor $v_i$ kap egy pontot, akkor annak a gráfban $v_i$-ből $v_j$-be 
menő irányított él felel meg. Irányítatlan gráfok esetén viszont csúcspárok kapják a pontot és annak a két csúcsot összekötő 
irányítatlan él felel meg. 

Ebben a cikkben csak irányítatlan gráfokkal foglalkozunk és első sorban azt vizsgáljuk, hogy nemnegatív egész számok 
$s = (s_1,\ldots,s_n)$ nemnövekvő sorozata és adott $a$ alsó korlát, valamint $b$ felső korlát esetén létezik-e olyan 
$(a,b,n)$-gráf, amelynek foksorozata $s$. Emellett foglalkozunk a foksorozatok számával, amelyet $G(a,b,n)$-nel jelölünk. 

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,IvanyiP2011,
KimTMESz2009,Knuth2011,LaMar2010,MiklosES2011,Pirzada2011,PirzadaIK2011,PirzadaNSI2010}).

Legyenek $l, \ m$ és $u$ egész számok, továbbá $1 \leq m$ és $l \leq u.$  Egész számok 
$s = (s_1,\ldots,s_m)$ sorozatát \textit{$(l,u,m)$-korlátosnak} (röviden: korlátosnak) nevezzük, ha 
$l \leq s_i \leq u$ minden $1 \leq i \leq m$ indexre. Az $s = (s_1,\ldots,s_m)$ $(l,u,m)$-korlátos sorozatot 
\textit{$(l,u,m)$-szabályosnak} mondjuk, ha  $u \geq s_1 \geq \cdots \geq s_m \geq l$. 

A vizsgálatok során kitüntetett szerepet játszanak az $(a(n - 1),b(n - 1),n)$-szabályos sorozatok. Ezeket a sorozatokat 
$(a,b,n)$\textit{-grafikusnak}  (vagy röviden grafikusnak) nevezzük, ha létezik olyan $(a,b,n)$-gráf, melynek kifoksorozata $s.$

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 összeadandó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 $(0,2k-1,2k)$-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 grafikus sorozatok ellenőrzésétől, 
ezért ezek a megszorítások nem jelentik az általánosság korlátozását. 

A cikkben csak \textit{teljes} gráfokkal foglalkozunk. Ezekre az jellemző, hogy ha $a \leq c \leq b,$ akkor bármely két csúcs 
között $c$ él is meg van engedve, és az irányított esetben azok tetszőlegesen irányíthatók. A \textit{hiányos} gráfoknál bizonyos 
lehetőségek tiltva vannak. Például a labdarúgásnak \cite{Frank2011,Ivanyi2011Egres,IvanyiLMS2011Acta,KovacsP2002} 
olyan irányított $(2,3,n)$-gráfok felelnek meg, amelyekben a csúcsokat 2 vagy 3 él köti össze, azonban 2 él esetén 
azok ellentétesen, míg 3 él esetén azok azonosan vannak irányítva.

Míg teljes gráfok esetén a sorozatok tesztelése az operációkutatás folyamos módszereivel kényelmesen megoldható 
(bár gyakran vannak gyorsabb algoritmusok is), hiányos gráfok esetén ezek a módszerek nem alkalmazhatók. 

Cikkünk fő célkitűzése, hogy minél kisebb várható futási idejű algoritmusokat találjunk annak eldöntésére, hogy előírt $s$ 
szabályos sorozat grafikus-e. Eközben a minden sorozatot helyesen minősítő \textit{pontos}, és a csak a szabályos sorozatok 
egy részét minősítő \textit{közelítő} algoritmusokkal is foglalkozunk. 

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

Melléktermékként javítottuk és bővítettük az OEIS \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 grafikus  
sorozat gazdaságos előállítására is alkalmas (lásd Ruskey \cite{RuskeyCES1994} 1994-es, valamint Barnes és Savage 
\cite{BarnesS1997} 1997-es cikkét).

A cikk felépítése a következő. A bevezető első rész után a $(0,1,n)$ 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. A nyolcadik rész témája a $(0,b)$-gráfok potenciális 
foksorozatainak tesztelése, míg a 9. részben a $(a,b,n)$-gráfoké a főszerep. A tizedik részben a grafikus sorozatok 
párhuzamos leszámlálása a téma, a tizenegyedik részben nyitott problémákat mutatunk be, míg végül a tizenkettedik részben 
összefoglaljuk a cikk mondanivalóját.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Klasszikus pontos algoritmusok $(0,1,n)$-gráfokhoz \label{sec-pontos}}
Ebben a részben a $(0,1,n)$-gráfok potenciális foksorozatainak tesztelésére ismert két klasszikus algoritmust ismertetjük.


\subsection{Havel-Hakimi algoritmus (HH) \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 3$, az $(s_1,\ldots,s_n)$ $(0,1,n)$-szabályos  
sorozat akkor és csak akkor $(0,1,n)$-grafikus, ha az $(s_2 - 1, s_3 - 1, \ldots,  s_{s_1} - 1, s_{s_1 + 1} - 1, 
s_{s_1 + 2}, \ldots, s_n)$ sorozat $(0,1,n - 1)$-grafikus.
\end{theorem}

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

\textit{Bemenet.} $n$: csúcsok száma $(n \geq 1)$; \\ 
$s = (s_1, \ldots, s_n)$: $(0,1,n)$-szabályos sorozat. 

\textit{Kimenet.} $L$: $s$ grafikusságát jelző logikai változó. 

\textit{Munkaváltozók.} $i, \ j$: ciklus változók; \\
$r = (r_1,\ldots,r_n)$: $r_i$ az $s_i$ elemhez tartozó tartalék; \\
$w = (w_1,\ldots,w_n)$: $w_i$ az  $i$ indexhez tartozó súlypont.

\bigskip
\noindent \textsc{Havel-Hakimi-Test}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{if} \= $s_1 == 0$   \` \textbf{//}    01--03. sor: nullákból álló sorozat elfogadása \\ 
\hspace{-7mm}02             \> $L = 1$ \\
\hspace{-7mm}03             \> \textbf{return} $L$ \\
\hspace{-7mm}04 \textbf{if} \= $s_{s_1 + 1} == 0$   \` \textbf{//} 04--06. sor: $s_1$ tesztelése konstans idő alatt \\
\hspace{-7mm}05             \> $L = 0$     \\ 
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $w_1 = n$                   \`  \textbf{//} 07-12. sor: az első súlypont és tartalék számítása\\
\hspace{-7mm}08 $j = n$ \\
\hspace{-7mm}09 \textbf{while} \= $s_j < 1$ és $j > 0$         \\  
\hspace{-7mm}10              \> $w_1 = w_1 - 1$ \\
\hspace{-7mm}11              \> $j  = j - 1$ \\
\hspace{-7mm}12 $r_1 = w_1 - 1 + s_1$                              \\
\hspace{-7mm}13 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$    \`  \textbf{//} 13--19. sor: $s$ tesztelése    \\
\hspace{-7mm}14              \> $j = w_{i-1}$      \`  \textbf{//} 14--17. sor: új súlypont kiszámítása \\ 
\hspace{-7mm}15              \> \textbf{while} \= $s_j < i$ and $j > 0$       \\ 
\hspace{-7mm}16              \>                \> $w_i = w_i - 1$             \\ 
\hspace{-7mm}17              \>                \> $j = j - 1$ \\              
\hspace{-7mm}18              \>                \> \textbf{if} \= $s_i > w_i + r_{i-1}$  \`  \textbf{//} 18. sor: $s$ grafikus?  \\
\hspace{-7mm}19              \>                \>             \> $L = 0$       \`  \textbf{//} 19--20. sor: $s$ nem grafikus \\
\hspace{-7mm}20              \>                \>             \> \textbf{return} $L$ \\
\hspace{-7mm}21              \>                \> $r_i = w_i + r_{i-1} - b_i$ \\
\hspace{-7mm}22 $L = 1$                                            \` Lines 22--23: $b$ is graphical \\
\hspace{-7mm}23 \textbf{return} $L$ \\     
\end{tabbing}
  
A \textsc{Havel-Hakimi} algoritmus alapja a következő tétel.  

\begin{theorem} Ha\label{th-HHL} $n \geq 1$, az $(s_1,\ldots,s_n)$ (0,1,n)-szabályos sorozat akkor és csak akkor grafikus, ha  
\begin{equation}
s_1 < w_1\label{eq-HHL1}
\end{equation}
és
\begin{equation}
s_i \leq w_i + r_{i-1} \quad (i = 2, \ldots, n - 1), 
\end{equation}
ahol
\begin{equation}
w_i = \max (k \geq 0 \ | \ s_k \geq i)   \quad (i = 1, \ldots, n),
\end{equation}
és
\begin{equation}
r_i = w_i + r_{i-1} - s_i             \quad (i = 1, \ldots, n).
\end{equation}
\end{theorem}

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, a megvalósítást is biztosító RAM algoritmusok  
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 (EG) \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 $s = (s_1,\ldots,s_n)$ sorozata esetén a sorozat első $i$ elemét a sorozat $s_i$ eleméhez tartozó 
\textit{fejnek,} míg a többi elemét az $s_i$ elemhez tartozó \textit{faroknak} 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,s_k)$ összeget pedig $C_i$-vel jelöljük 
és a farok \textit{kapacitásának} nevezzük.  Ha egy $s$ 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,$ a \label{tetel-EG} $(0,1,n)$-szabályos $(s_1,\ldots,s_n)$ 
sorozat akkor és csak akkor $(0,1,n)$-grafikus, ha 
\begin{equation}
H_n \quad \mbox{páros}\label{eq-EGparity}
\end{equation}
és
\begin{equation}
H_i \leq i(i - 1) + 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}

A \ref{tetel-EG}. tételen alapul a következő \textsc{Erdős-Gallai} algoritmus.

\textit{Bemenet.} $n$: az $s$ sorozat hossza; \\ 
$s = (s_1,\ldots,s_n):$ $(0,1,n)$-szabályos sorozat.

\textit{Kimenet.} $L:$ logikai változó (ha $s$ $(0,1,n)$-grafikus, akkor $L = 1,$ egyébként $L = 0.$ 

\textit{Munkaváltozó.} $t$: az aktuális $C_i$ felső korlátja.

\bigskip
\noindent \textsc{Erd\H os-Gallai}$(n,s,L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = s_1$              \` \textbf{//} 01--03. sor: $H$ elemeinek kiszámítása\\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n$ \\
\hspace{-7mm}03              \> $H_i = H_{i-1} + s_i$\\
\hspace{-7mm}04 \textbf{if} \= $H_n$ páratlan          \` \textbf{//} 04--06. sor: paritás ellenőrzése \\
\hspace{-7mm}05             \> $L = 0$   \` \textbf{//} 05--06. sor: nemgrafikus sorozat elutasítása \\
\hspace{-7mm}06             \> \textbf{return} $L$\\
\hspace{-7mm}07 \textbf{for} \= $i = 1$ \textbf{to} $n-1$ \` \textbf{//} 07--15. sor: $s$ tesztelése\\
\hspace{-7mm}08              \> $t = 0$                   \` \textbf{//} 08. sor: $t$ kezdeti értékének beállítása\\
\hspace{-7mm}09 \>    \textbf{for} \= $k = i + 1$ \textbf{to} $n$ \` \textbf{//} 09--10. sor:  \\
\hspace{-7mm}10 \>                 \> $t = t + \min(i, b_k)$\\
\hspace{-7mm}11 \>    \textbf{if} \= $H_i - i(i - 1) > t$   \` \textbf{//} line 11: check the necessary condition\\
\hspace{-7mm}12 \>                \>  $L = 0$     \` \textbf{//} lines 12--13: the input is nongraphical\\
\hspace{-7mm}13 \>                \> \textbf{return} $L$\\
\hspace{-7mm}14 $L = 1$                          \` \textbf{//} lines 14--15: the input is graphical\\
\hspace{-7mm}15 \textbf{return} $L$\\
\end{tabbing} 

EG memóriaigénye $\Theta(n)$, futási ideje a legjobb $\Theta(n)$ és a legrosszabb $\Theta(n^2)$ között változik..

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 
grafikus bemenet esetén $O(n^3)$ idő alatt egy megoldást is előállít.  

A szabályos sorozatoknak aszimptotikusan a fele páros sorozat. Az \ref{tab-regevenratio}. táblázat a $(0,1,n)$-szabályos 
sorozatok számát megadó \ref{lemma-Rn}, valamint a $(0,1,n)$-páros sorozatok számát megadó \ref{lemma-En} lemmák alapján 
mutatja a konvergencia gyorsaságát (ami a képletek alapján természetes) $(E(n)/R(n))$ tartalmazza $n = 1,\ldots,38$ csúcs esetén. 

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Új pontos algoritmusok $(0,1,n)$-gráfokhoz \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 
grafikus-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$, az $(s_1,\ldots,s_n)$ $(0,1,n)$-szabályos  
sorozat akkor és csak akkor $(0,1,n)$-grafikus, ha $s_n = 0$ vagy az $(s_1, \ldots, s_p)$ sorozat $(0,p,p)$-grafikus.
\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-HHSh}}
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 (HHSh) kapjuk.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Paritásos Havel-Hakimi algoritmus\label{subsec-HH}}
Érdekes gondolat az Erdős-Gallai és a Havel-Hakimi feltételek együttes alkalmazása úgy, hogy először $s$ 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ő jelentősen csökken.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lineáris Havel-Hakimi tesztelő algoritmus (HHl)\label{subsec-HHT}}
Az EGl algoritmusban kulcsszerepe van az $s_i$ elemhez tartozó $w_i$ súlypontnak \cite{IvanyiLMS2011Acta},  
amely $i > s_i$ esetén 0, egyébként a legnagyobb olyan $k$ index, amelyre igaz, hogy $s_k \geq bi$ (ez az egyenlőtlenség a 
$(0,1,n)$-gráfok esetén az $s_k \geq i$ egyenlőtlenségre egyszerűsödik.)

Ez a súlypont arra is alkalmas, hogy a Havel-Hakimi algoritmus alábbi változatában fontos szereplő legyen. 
A pszeudokód a \cite{CormenLRS2009} tankönyvben ismertetett konvenciókat alkalmazza.

\textit{Bemenet.} $n$: csúcsok száma $(n \geq 1)$; \\ 
$s = (s_1,\ldots,s_n)$: a tesztelendő $(0,1,n)$-szabályos sorozat.

\textit{Kimenet.} $L$: $s$ grafikusságát jelző logikai változó.

\textit{Munkaváltozók.} $i$: ciklus változó; \\
$r = (r_1,\ldots,r_n)$: $r_i$ az $s_i$-hez tartozó maradék farokkapacitás ($r_1 = w_1 - 1$ és   
$r_i = w_i - 1 + r_{i-1} - s_i,$ ha $2 \leq i \leq n$); \\
$w = (w_1,\ldots,w_n)$: $w_i$ az $i$ indexhez tartozó súlypont (ha $i > s_1$, akkor $w_i = 0$, egyébként  
$w_i$ a legnagyobb olyan $k,$ amelyre teljesül $s_k \geq i$; \\
$H = (H_1, \ldots,H_n)$: $H_i$ az $s$ sorozat első $i$ elemének összege. 

\bigskip
\noindent \textsc{Havel-Hakimi-lineáris}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L = 0$                 \` \textbf{//} 01. sor: a gyakoribb érték beállítása \\
\hspace{-7mm}02 \textbf{if} \= $s_1 == 0$   \` \textbf{//} 02--04. sor: a nullákból álló sorozat grafikus \\ 
\hspace{-7mm}03             \> $L = 1$ \\
\hspace{-7mm}04             \> \textbf{return} $L$ \\
\hspace{-7mm}05 \textbf{if} \= $s_{s_1 + 1} == 0$   \` \textbf{//} 05--07. sor: $s_1$ ellenőrzése konstans idő alatt \\ 
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $H_1 = s_1$                             \` \textbf{//} 07. sor: $H_1$ egyenlő a sorozat első elemével \\
\hspace{-7mm}08 \textbf{for} \= $i = 2$ \textbf{to} $n$ \` \textbf{//} 08--08. sor: további $H_i$ értékek kiszámítása\\
\hspace{-7mm}09              \> $H_i = H_{i-1} + s_i$   \\
\hspace{-7mm}10 \textbf{if} \= $H_n$ páratlan         \`   \textbf{//} 10--11. sor: paritás ellenőrzés\\
\hspace{-7mm}11             \> \textbf{return} $L$\\
\hspace{-7mm}12 $w_1 = n$                   \`  \textbf{//} 12--15. sor: első súly és tartalék számítása\\
\hspace{-7mm}13 \textbf{while} \= $s_{w_1} < 1$ \\
\hspace{-7mm}14                \> $w_1 = w_1 - 1$ \\
\hspace{-7mm}15 $r_1 = w_1 - 1 - s_1$ \\ 
\hspace{-7mm}16 $s_{n+1} = 0$ \\
\hspace{-7mm}17 \textbf{for} \= $i = 2$ \textbf{to} $n - 1 $         \\ 
\hspace{-7mm}18              \> \textbf{if} \= $s_i \leq 1$ vagy $s_{i+1} = 0$  \\
\hspace{-7mm}19              \>             \> $L = 1$ \\
\hspace{-7mm}20              \>             \> \textbf{return} $L$ \\ 
\hspace{-7mm}21              \> $w_i = w_{i-1}$ \\
\hspace{-7mm}22              \> \textbf{while} \= $s_{w_i} < i$ és $w_i > 0$ \\
\hspace{-7mm}23              \>                \> $w_i = w_i - 1$ \\
\hspace{-7mm}24              \> \textbf{if} \= $w_i \geq i$                              \` 24. sor: esetszétválasztás  \\
\hspace{-7mm}25              \>             \> \textbf{if} \= $s_i > w_i - 1 + r_{i-1}$  \`\textbf{//} 25. sor: $s$ grafikus?  \\
\hspace{-7mm}26              \>             \>             \> \textbf{return} $L$     \`  \textbf{//} 26. sor: $s$ nem grafikus \\
\hspace{-7mm}27              \>             \> $r_i = w_i - 1 + r_{i-1} - s_i$ \\
\hspace{-7mm}28              \> \textbf{else} \= \textbf{if} \= $s_i > w_i + r_{i-1}$  \`\textbf{//} 28. sor: $s$ grafikus?  \\
\hspace{-7mm}29              \>               \>             \> \textbf{return} $L$    \`  \textbf{//} 29. sor: $s$ nem grafikus \\ 
\hspace{-7mm}30              \>               \> $r_i = w_i + r_{i-1} - s_i$ \\  
\hspace{-7mm}31 $L = 1$  \\
\hspace{-7mm}32  \textbf{return}
\end{tabbing}

\begin{theorem} A \textsc{Havel-Hakimi-lineáris-teszt} futási ideje legjobb esetben $\Theta(1)$, 
legrosszabb esetben $\Theta(n)$.
\end{theorem} 

\begin{proof} A 01--07. sorok időigénye $O(1),$ és például a $(0^n)$ bemenetre a program a 04. sorban megáll, ezért a 
legjobb futási idő $O(1).$ A 08--11. sorok időigénye $\Theta(n).$ Mivel a súlypontok számítása legfeljebb $n$ csökkentést 
igényel, a 14--30. sorok igénye $O(n),$ ezért a legrosszabb eset $\Theta(n).$
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Példák\label{subsec-HHL}}
\textbf{1. példa.} Legyen az első példánk $s = (3^3,1)$. A 01--15. sorok szerint $r_1 = 0$. Ha $i = 2,$ akkor   
$w_i = 3$ és a 25. sor feltétele nem teljesül, ezért $s$ \textit{nem} $(0,1,4)$\textit{-grafikus}. \hfill $\square$

\textbf{2. példa} A következő példa $s = (5,3^2,2,1^3)$. Az 01--15. sorokban azt kapjuk, hogy $w_1 = 7$ és $r_1 = 1.$ Ha $i = 2,$ 
akkor $w_i = 4$, a 25. sor feltétele nem teljesül és a 27. sor szerint $r_2 = 1.$  
Ha $i = 3,$ akkor $w_i = 3$ és nem teljesül a 25. sor feltétele. Ha $i = 4,$ akkor $w_i = 1$ és most sem teljesül 25. sor 
feltétele. Ha $i = 5,$ akkor teljesül a 16. sor $s_i \leq 1$ feltétele, és ezért $s$ $(0,1,7)$\textit{-grafikus.} \hfill $\square$
 
\textbf{3. példa} Legyen $s = (5, 4, 1^5).$ Erre a sorozatra $r_1 = 1,$ és ha $i = 2,$ akkor $w_i = 2,$ ezért  
a 25. sor feltétele teljesül, így $s$ \textit{nem} $(0,1,7)$-\textit{grafikus.} \hfill $\square$ 

\textbf{4. példa} Utolsó példánk legyen $s = (5^2,4,3^4).$ Az első 15 sor szerint $r_1 = 1.$ Ha $i = 2,$ akkor  
$w_i = 7$ és $r_2 = 1.$ Ha $i = 3,$ akkor $w_3 = 7$ és $r_3 = 2.$ Ha $i = 4,$ akkor teljesül a 18. sor $s_i \leq 1$ feltétele, 
ezért $s$ $(0,1,7)$\textit{-grafikus.} \hfill $\square$ 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{HHLT első hat sorának elemzése \label{subsec-HHL3}}
Nem nehéz belátni, hogy a $(l,u,m)$-korlátos sorozatok $B(l,u,m)$ száma
\begin{equation}
B(l,u,m) = \binom{u - l + m}{m} \, .\label{eq-lum}
\end{equation}

Ezért a HHl algoritmus lehetséges bemeneteinek a száma
\begin{equation}
B(0,n-1,n) = \binom{2n - 1}{n} \, .\label{eq-nreg} 
\end{equation}

HHl első három sora kiszűri például azokat a sorozatokat, amelyek $(n - 1)$-gyel kezdődnek és nullával végződnek. Ezek száma 
\eqref{eq-lum} szerint
\begin{equation}
B(0,n-1,n-2) = \binom{2n - 3}{n -2} \, .\label{eq-zeroone}
\end{equation}
Ezek közül a HHl által kiszűrt sorozatok $R_1(n)$ hányada
\begin{equation}
R_1(n) = \frac{\binom{2n - 3}{n - 2}}{\binom{2n - 1}{n}} = \frac{2(2n - 1)}{n} = \frac{1}{4} + \frac{1}{8n  - 4} \, .\label{eq-R1n}
\end{equation} 

HHl pontosan azokat a sorozatokat szűri ki, amelyek $(n - i)$-vel $(i = 1, \ldots, n - 2)$ kezdődnek és legalább 
$i$ nullát tartalmaznak. Rögzített $i$-re az ilyen sorozatok aszimptotikus részaránya $1/4^i,$ így HHl aszimptotikusan 
a szabályos sorozatoknak a 
\begin{equation}
\sum _{i = 1}^{\infty} \frac{1}{4^i} = \frac{1}{3}
\end{equation}
összegnek megfelelő hányadát, azaz egy harmad részét szűri ki.
 

Mivel a grafikus sorozatok aszimptotikus sűrűsége nulla, ezért minden $A$ pontos algoritmusra létezik egy 
$s_{1,A} + s_{2,A} + \ldots = 1$ sor (valószínűség-eloszlás), amelyben $s_i$ az $i$-edik menetben kiszűrt hányad. Például 
$s_{1,A} = 1/3$ minden olyan pontos algoritmusra, amelyik első menetben a PT algoritmust (vagy annak valamilyen lassú változatát) 
használja az első menetben -- ilyen a HH és az EG is.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tripathi és Vijay első javítása\label{subsec-TV1}}
Tripathi és Vijai 2003-ban megmutatta, hogy az Erdős-Gallai tétel következő változata is helyes.

\begin{lemma} \emph{(Tripathi, Vijay \cite{TripathiV2003})} Ha\label{lemma-EGS} $n \geq 1$, \label{theorem-EGS} akkor  
a $(0,1,n)$-szabályos $s$ sorozat akkor és csak akkor $(1,1,n)$-grafikus, ha   
\begin{equation}
H_n \quad  \mbox{páros} \label{eq-EGSparos} 
\end{equation}
és
\begin{equation}
H_i - i(i - 1) \leq \sum _{k=i+1}^n \min(i,s_k) \quad (i = 1,\ldots,q),\label{eq-EGStbinomold}
\end{equation}
ahol 
\begin{equation}
q = \max_{1 \leq k \leq n}(k \ | \ k(k - 1) < H_k).
\end{equation}
\end{lemma}

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

Ennél is hasznosabb a következő állítás,amelyben \eqref{eq-EGStbinomold} helyett 
a szigorúbb \eqref{eq-EGStbinomnew} szerepel, amelyet $q$ helyett csak $(q - 1)$-ig ellenőrzünk.

\begin{lemma} Ha\label{lemma-EGS} $n \geq 1,$\label{theorem-EGS} a $(0,1,n)$-szabályos  $s = (s_1, \ldots, s_n)$ sorozat akkor és 
csak akkor grafikus, ha    
\begin{equation}
H_n \quad  \mbox{páros} 
\end{equation}
és
\begin{equation}
H_i - \min(H_i,i(i - 1)) \leq \sum _{k=i+1}^n \min(i,s_k) \quad (i = 1,2,\ldots,q - 1),\label{eq-EGStbinomnew}
\end{equation}
ahol  
\begin{equation}
q = \max _{1 \leq k \leq n}(k \ | \ k(k - 1) < H_k).
\end{equation}
\end{lemma}

\begin{proof} Ha ???????????????????,
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tripathi és Vijay második javítása \label{subsec-TV2}}
Tripathi és Vijai a \cite{TripathiV2003} cikkben az Erdős-Gallai tétel következő, lényeges gyorsítást lehetővé tevő 
változatát is bizonyították.

Az ismétlődő elemeket gyakoriságuk segítségével tömörítve a $(0,1,n)$-szabályos $(s_1,\ldots,s_n)$ sorozat felírható az  
$(s_{i_1}^{e_1}, \ldots, s_{i_q}^{e_q})$ alakban, ahol $s_{i_1} < \cdots < s_{i_q},$ $e_1, \ \ldots, \ e_q \geq 1$ és  
$e_1 + \cdots + e_q = n.$ Legyen $g_j = e_1 + \cdots + e_j \ (j = 1, \ \ldots, \ q).$   

Az $s_i$ elemet az $s$ \textit{ugró elemének} nevezzük, ha $i = n$ vagy $1 \leq i \leq n - 1$ és $s_i > s_{i+1}$. 
Ekkor az ugró pontok az $s_{g_1},\ldots,s_{g_q}$ elemek. Az ugró (vagy ellenőrző) elemeket 
$c_1 = s_{g_1}, \ldots, c_q = s_{g_q}$ módon jelöljük.

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

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

Megjegyezzük, hogy az ellenőrzést elég a $(q - 1)$-edik ugrópontig folytatni.

Ehhez az állításhoz hasonló a következő \ref{th-HHLJ}. tétel.

Ha $s$ azonos elemekből áll, akkor mindig grafikus és nincs $n$-nél kisebb ugrópont benne. Ezért tegyük fel, hogy $s_1 > s_n,$  
továbbá $s$ ugrópontjainak sorozata $s = (s_1,\ldots,s_q)$. 

\begin{theorem} Ha\label{th-HHlu} $n \geq 1$, a szabályos $(s_1,\ldots,s_n)$ sorozat akkor és csak akkor grafikus, ha  
\begin{equation}
H_{s_i} \leq \sum _{j=1}^{s_i} w_j - 1 \quad (i = 1, \ldots, q - 1), 
\end{equation}
ahol 
\begin{equation}
w_j = \max (k \geq 0 \ | \ b_k \geq j).
\end{equation}
\end{theorem}
\begin{proof} Ha ???????????????????????????????????????????????????
\end{proof}

A következő táblázatokban bemutatjuk, hogyan oszlanak meg  a kizárt grafikus és nemgrafikus sorozatok az egyes menetek között. 
Azt is jellemezzük, hogy átlagosan hány meneten át kell egy grafikus, illetve nemgrafikus sorozatot a kizárásáig tesztelni, és 
azt is, hogy a menetek hányadrészét fordítjuk átlagosan egy sorozat tesztelésére.

A \ref{tab-undi-reg-graph}. táblázat az $(a,b,n)$-szabályos és $(a,b,n)$-grafikus sorozatok  számát tartalmazza 
$n = 1, \ \ldots, \ 11$ csúcs, valamint $a = 0$ és $ b = 1,$ $a = 0$ és $b = 2,$  $a = 2$ és $b = 5$ esetén. 

\begin{table}[!ht]
\begin{centering}
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
n	&	R(0,1,n)&G(0,1,n) &	R(0,2,n)   & G(0,2,n)  &	R(2,3,n)	&	G(2,3,n)	\\ \hline 
1	&	1	    &	1	  &	1	       &	1      &	1	        &	1	\\
2	&	3	    &	2	  &	6	       &	3      &	10	        &	4	\\
3	&	10	    &	4	  &	35	       &	10     &	84	        &	23	\\
4	&	35	    &	11	  &	210	       &	52     &	715	        &	189	\\
5	&	126	    &	31	  &1 287	   &	283	   &	6 188	    &	1 582	\\
6	&	462	    &	102	  &8 008	   &	1 706  &	54 264	    &	13 583	\\
7	&	1 716	&342	  &	50 388	   &10 436	   &	480 700	    &	122 345	\\
8	&	6 435	&1 213	  &	319 770    &65 370	   &	4 292 145	&	1 092 573	\\
9	&	24 310	&4 361	  &	2 042 975  &413 111	   &	38 567 100	&	9 816 598	\\
10	&	92 378	&16 016	  &	13 123 110 &2 633 537  &	348 330 136	&	88 680 716	\\
11	&	352 716	&59 348	  &	84 672 315 &16 882 153 & 3 159 461 968	&	804 480 107	\\
\hline \hline
\end{array}$
\end{scriptsize}
\caption{Az $(a,b,n)$-szabályos és $(a,b,n)$-grafikus sorozatok száma $n = 1, \ \ldots, \ 11$ csúcs,  valamint 
$a = 0$ és $ b = 1,$ $a = 0$ és $b = 2,$  $a = 2$ és $b = 5$ esetén.\label{tab-undi-reg-graph}}
\end{centering}
\end{table}

A \ref{tab-test01n}. táblázat a HHl által az $i$-edik $(i = 1, \ldots, 11)$ menetben kiszűrt nem grafikus sorozatok 
számát mutatja  $n = 1, \ \ldots, \ 11$ csúcs, valamint  $a = 0$ és $b = 1$ esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r|r|r|r|r|r||} \hline \hline
n/i & 1     &   2   & 3       & 4   & 5     &  6  &   7   &  8    &   9   &  10 & 11\\ \hline
1	&	0	&		&		&		&		&		&		&		&		&		&		\\
2	&	1	&	0	&		&		&		&		&		&		&		&		&		\\
3	&	6	&	0	&	0	&		&		&		&		&		&		&		&		\\
4	&	22	&	2	&	0	&	0	&		&		&		&		&		&		&		\\
5	&	85	&	8	&	2	&	0	&	0	&		&		&		&		&		&		\\
6	&	311	&	35	&	12	&	2	&	0	&	0	&		&		&		&		&		\\
7	&	1169	&	128	&	58	&	17	&	2	&	0	&	0	&		&		&		&		\\
8	&	4369	&	488	&	239	&	100	&	24	&	2	&	0	&	0	&		&		&		\\
9	&	16524	&	1805	&	942	&	471	&	173	&	32	&	2	&	0	&	0	&		&		\\
10	&	62650	&	6800	&	3601	&	2021	&	956	&	289	&	43	&	2	&	0	&	0	&		\\
11	&	239008	&	25571	&	13677	&	8147	&	4561	&	1877	&	470	&	55	&	2	&	0	&	0	\\ \hline \hline
\end{array} $
\end{scriptsize}
\caption{HHl $i$-edik $(i = 1,\ldots,11)$ menetében kiszűrt nem grafikus sorozatok száma $n = 1, \ \ldots, \ 11$ csúcs, valamint 
$a = 0, \ b = 1$ esetén.\label{tab-test01n}}
\end{table}

A \ref{tab-test01g}. táblázat HHl $i$-edik $(i = 1, \ \ldots, \ 11)$ menetében kiszűrt grafikus sorozatok számát 
tartalmazza $a = 0$ és $b = 1,$ $n = 1, \ \ldots, \ 11$ csúcs  esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrrr||} \hline \hline
  n/i   & 1    &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10 & 11\\ \hline
  1	&	1	&		&		&		&		&		&		&		&		&		&		\\
2	&	1	&	1	&		&		&		&		&		&		&		&		&		\\
3	&	1	&	3	&	0	&		&		&		&		&		&		&		&		\\
4	&	1	&	8	&	2	&	0	&		&		&		&		&		&		&		\\
5	&	1	&	16	&	12	&	2	&	0	&		&		&		&		&		&		\\
6	&	1	&	29	&	48	&	22	&	2	&	0	&		&		&		&		&		\\
7	&	1	&	47	&	130	&	127	&	35	&	2	&	0	&		&		&		&		\\
8	&	1	&	72	&	306	&	488	&	290	&	54	&	2	&	0	&		&		&		\\
9	&	1	&	104	&	618	&	1492	&	1475	&	591	&	78	&	2	&	0	&		&		\\
10	&	1	&	145	&	1158	&	3863	&	5757	&	3868	&	1112	&	110	&	2	&	0	&		\\
11	&	1	&	195	&	1998	&	8890	&	18440	&	18662	&	9053	&	1958	&	149	&	2	&	0	\\ \hline \hline
\end{array} $
\end{scriptsize}
\caption{HHl $i$-edik $(i = 1, \ \ldots, \ 11)$ menetében kiszűrt nem grafikus sorozatok száma $a = 0,$  $b = 1$ és  
$n = 1, \ \ldots, \ 11$ csúcs  esetén. \label{tab-test01g}}
\end{table}

Legyen $N_i(a,b,n,A),$ illetve $M_i(a,b,n,\emph{A})$ az A algoritmus által az $(a,b,n)$-szabályos sorozatok vizsgálata során az 
$i$-edik $(i = 1, \ldots, n)$ menetben kizárt nemgrafikus, illetve grafikus sorozatok száma, továbbá legyen
\begin{equation}
N = \sum _{i=1}^n \quad   \emph{\mbox{és}} \quad  M = \sum _{i = 1}^n m_i, \label{eq-NM}
\end{equation} 
\begin{equation}
X(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n in_i}{n},  \label{eq-X}
\end{equation}
\begin{equation}
Y(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n im_i}{n},  \label{eq-Y}
\end{equation}
\begin{equation}
Z(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n i(m_i + n_i)}{n}, \label{eq-Zp}
\end{equation}
\begin{equation}
X'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n in_i}{n^2},  \label{eq-Xp}
\end{equation}
\begin{equation}
Y'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n im_i}{n^2},   \label{eq-Yp}   
\end{equation}
\begin{equation}
Z'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^n i(m_i + n_i)n_i}{n^2}.  \label{eq-Zp}
\end{equation}

Az \ref{tab-HHl02hat}. táblázat a ChEGl algoritmus hatékonyságát jellemzi 
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGL02hat}

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
 $n$/\mbox{jellemző}  &    X     &   Y       &    Z    &   X'     &  Y'     &    Z'  \\ \hline
  2                   &  1.0000  & 1.5000    & 1.3333  &  0.5000  &	 0.7500 &  0.6667						\\
  3                   &  1.0000  & 1.7500    & 1.3000  &  0.3333  &  0.583  &  0.4333		      		\\
  4                   &  1.0833  & 2.0909    & 1.4000  &  0.2708  &	0.5018  &  0.3500					\\
  5                   &          & 	         &		   &	      &	        &				 \\
  6                   &          &    	     &	       &	      &	        &		       		\\
  7                   &          & 	         &	 	   &	      &	        &		       	\\
  8                   &          & 	         &	  	   &	      &	        &		       		\\
 10                   &          &   	     &		   &	      &	        &		    			\\
 11                   &          & 	         &	 	   &	      &	        &		    	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{HHl hatékonysági jellemzői $a = 0,$ $b = 1$ és $n = 2, \ \ldots, \ 11$ csúcs esetén.\label{tab-HHl02hat}}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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,$ a  
$(0,1,n)$-szabályos $s = (s_1,\ldots,s_n)$ sorozat akkor és csak akkor $(0,1,n)$-grafikus, 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 $c = (5^{100})$ sorozat esetén (\ref{eq-EGbinom}) jobb oldalát az Erdős-Gallai algoritmus szerint kilencvenkilencszer, míg 
a rövidített Erdős-Gallai algoritmus szerint csak hatszor 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 (EGu)\label{subsec-EGU}}
Az ismétlődő elemeket összevonva egy szabályos $(s_1,\ldots,s_n)$ sorozat 
$(s_{i_1}^{e_1},$ \linebreak 
\noindent $\ldots, s_{i_q}^{e_q})$ alakban is felírható, ahol $s_{i_1} > \cdots > s_{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).$   

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

\begin{theorem} \emph{(Tripathi, Vijay \cite{TripathiV2003})} Az\label{tetel-EGJ} $(1,1,n)$-szabályos $s = (s_1\ldots,s_n)$ 
sorozat akkor és csak akkor $(1,1,n)$-grafikus, 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,s_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)$; \\
$s = (s_1, \ldots, s_n)$: $n$-szabályos sorozat.

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó.
 
\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,s,L,\gamma )$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L = 0$     \` $\rhd$ 01--02. sor: kezdeti értékek beállítása \\
\hspace{-7mm}02 $l = 0$ \\
\hspace{-7mm}03 $p = n$                                           \` $\rhd$ 03--05. sor: nullamentesítés \\
\hspace{-7mm}04 \textbf{while} \= $s_p = 0$ \\
\hspace{-7mm}05                \> $p = p -1$  \\
\hspace{-7mm}06 $H_1 = s_1$                                 \` $\rhd$ 06--10. sor: paritás ellenőrzése \\
\hspace{-7mm}07 \textbf{for} \= $i = 2$ \textbf{to} $p$ \\
\hspace{-7mm}08              \> $H_i = H_{i-1} + s_i$ \\
\hspace{-7mm}09 \textbf{if} \= $H_p$ páratlan \\
\hspace{-7mm}10             \>  \textbf{return} $L$  \\
\hspace{-7mm}11 $s_{p + 1} = 0$                        \` $\rhd$ 11--23. sor: fej igényének ellenőrzése \\
\hspace{-7mm}12 $i = 1$ \\
\hspace{-7mm}13 \textbf{while} \= $i \leq p$ és $i(i - 1) < H_i$\\
\hspace{-7mm}14                \> \textbf{if} \= $s_i = s_{i+1}$ \\
\hspace{-7mm}15                \>            \> $i = i +1$ \\ 
\hspace{-7mm}16                \>             \> $E = 0$ \\
\hspace{-7mm}17                \>             \> \textbf{for} \= $j = i + 1$ \textbf{to} $p$ \\
\hspace{-7mm}18                \>             \> $E = E + \min(j,s_j)$ \\
\hspace{-7mm}19                \> \textbf{if} \= $H_i > i(i - 1) + E$ \\  
\hspace{-7mm}20                \>             \> \textbf{return} $L$ \\
\hspace{-7mm}21  $L = 1$ \\
\hspace{-7mm}22 \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 (EGl)\label{subsec-EGl}}
A következő \textsc{Erdős-Gallai-Lineárisan} algoritmus kihasználja, hogy az $s$ bemeneti sorozat monoton. 
Ennek köszönhetően a $C_i$ kapacitásokat minden $i$-re konstans időben meg tudja határozni, azaz nincs szüksége arra, 
hogy a megfelelő farok elemeit egyenként megvizsgálja. A gyors számolás kulcsa a súlypontokat tartalmazó $w(s)$ sorozat.
 
Adott $s$ sorozat esetén legyen $w(s) = (w_0,w_1,\ldots,w_{n-1}),$ ahol $i > s_1$  esetén $w_i = 0,$ egyébként pedig 
$w_i$ az $s$ sorozat legnagyobb indexű olyan elemének indexe, amelyik legalább akkora, mint $i.$ 

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

Ha viszont $i \leq w_i,$ akkor a $C_i$-t definiáló szummát két részre bontjuk: az első részhez a farok azon $s_j$ 
kezdő elemeinek hozzájárulása tartozik, amelyekre teljesül $s_j \geq i,$ a második részhez pedig a többi elem. Legyen 
$q(s) = q = \max _{1 \leq i \leq n} \{i \ | \ i(i - 1) \leq H_i \}.$  
    
\begin{theorem} Ha\label{theorem-EGl} $n \geq 1,$ az $s = (s_1, \ldots, s_n)$ $(0,1,n)$-szabályos sorozat akkor és csak 
akkor $(0,1,n)$-grafikus, 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(s) = k =  
\left \{ 
\begin{array}{cc}
w_i, & \mbox{ if } i \leq w_i, \\
i, & \mbox{ ha } i > w_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 w_i,$ akkor
\begin{equation}
H_{i} \leq  i(i - 1) + (w_i - i + 1)i + H_n - H_{w_i} \label{eq-EGLsmalli} 
\end{equation}
és ha $i > w_i,$ akkor 
\begin{equation}
H_i \leq  i(i - 1) + H_n - H_i.\label{eq-EGLlargei} 
\end{equation}

Ha (\ref{eq-EGLsmalli}) jobb oldalán kiemeljük $i$-t, akkor a 
\begin{equation}
H_i \leq iw_i + H_n - H_{w_i}
\end{equation}
egyenlőtlenséget kapjuk. Ha (\ref{eq-EGLparity})-ba (\ref{eq-EGLk}) alapján behelyettesítjük $k$-t, akkor az 
$i \leq w_i$ esetben (\ref{eq-EGLsmalli})-t, az $i > w_i$ esetben pedig (\ref{eq-EGLlargei})-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 
grafikus-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)$; \\
$s = (s_1,\ldots,s_n)$: $(0,1,n)$-szabályos sorozat.  

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó.

\textit{Munkaváltozók.} $i$: ciklusváltozó; \\
$H = (H_1,\ldots,H_n)$: $H_i$ az éppen tesztelt $s$ első $i$ elemének az összege; \\
$w = (w_1,\ldots,w_{n-1})$: $w_i$ a legnagyobb indexű olyan $s_j$ indexe, amely legalább $i$;
$H_0 = 0$: segédváltozó a $H$ sorozat elemeinek kiszámításához; \\
$s_0 = n - 1$: segédváltozó az $m$ sorozat elemeinek kiszámításához; \\
$y$: ellenőrzés egyszerűsítéséhez használt változó (az aktuális $s_i$ vágópontja, azaz $w$ és $i$ maximuma). 


\bigskip
\noindent \textsc{Erdős-Gallai-lineáris}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_{1} = s_1$                                  \` \textbf{//} 01. sor: $H_1$ beállítása \\
\hspace{-7mm}02 \textbf{for} \= $i=2$ \textbf{to} $n$      \` \textbf{//} 02--03. sor: $H$ további elemeinek számítása\\
\hspace{-7mm}03              \> $H_{i} = H_{i-1} + s_{i}$    \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ is odd                     \` \textbf{//} 04--06. sor: paritás ellenőrzése\\
\hspace{-7mm}05             \> $L = \textsc{0}$\\
\hspace{-7mm}06             \>  \textbf{return}\\
\hspace{-7mm}07 $w = n$                                      \` \textbf{//} 07. sor: súlypont beállítása \\
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n$      \` \textbf{//} 08--12. sor: $s$ elemeinek tesztelése\\
\hspace{-7mm}09              \> \textbf{while} \= $w > 1$ and $s_w < i$  \` \textbf{//} 08--10. sor: aktuális súlypont számítása\\
\hspace{-7mm}10              \>                \> $w = w - 1$ \\
\hspace{-7mm}11              \> $y = \max(i,w)$     \` \textbf{//}  11. sor: aktuális vágópont számítása\\
\hspace{-7mm}12              \> \textbf{if} \= $H_i > i(y - 1) + H_n - H_y$  \\
\hspace{-7mm}13              \>             \> $L = 0$ \` \textbf{//} lines 13--14: nemgrafikus $s$ elutasítása \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$   \\
\hspace{-7mm}15 $L = 1$                         \` \textbf{//} 15--16. sor: grafikus $s$ elfogadása\\
\hspace{-7mm}16 \textbf{return} $L$
\end{tabbing}


\begin{corollary} A $(0,1,n)$-szabályos $s = (s_1,\ldots,s_n)$ sorozatról az EGl algoritmus  
 $\Theta(n)$ idő alatt dönti el, hogy $s$ $(0,1,n)$-grafikus-e. 
\end{corollary} 

\begin{proof} A 01--03. sorok $\Theta(n)$ időt igényelnek. Mivel a $w$ súlypontot legfeljebb $n$-szer frissítjük, ezért 
a 04--16. sorok időigénye $O(n)$, így az algoritmus futási ideje $\Theta(n)$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Gyors Erdős-Gallai algoritmus (EGgy)\label{subsec-EGgy}} 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 a \textit{The On-Line Encyclopedia of Integer Sequences} című honlapon 
\cite{Sloane2011A001700,Sloane2011A004251,Sloane2011A005654} is. 

\begin{lemma} Ha\label{lemma-Kn} $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 $K(l,u,m)$ száma
\begin{equation}
K(l,u,m) = (u - l + 1)^m.\label{eq-Kn}
\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-Rn} $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 $R(l,u,m)$ száma
\begin{equation}
\rho(l,u,m) = \binom{m + u - l}{m}.\label{eq-Rn}
\end{equation}
\end{lemma}

\begin{proof} Egy $s = (s_1,\ldots,s_m)$ $(l,u,m)$-szabályos sorozat esetén legyen $s' = (s_1',\ldots, s_m')$, ahol 
$s_i' = s_i + m - i$. A lehetséges $s$ és $s'$ sorozatok halmazai között kölcsönösen egyértelmű kapcsolat áll fenn. 
A különböző $s'$ 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-Rnjell}
\begin{equation}
\frac{R(n + 2)}{R(n + 1)} > \frac{R(n + 1)}{R(n)},\label{eq-Rnmon}
\end{equation}
\begin{equation}
\lim R _{n \rightarrow \infty} = 4,\label{eq-Rnlim}
\end{equation}
továbbá
\begin{equation}
\frac{4^n}{\sqrt{4\pi n}}\large (1 - \frac{1}{2n} \large) < R(n) < 
\frac{4^n}{\sqrt{4\pi n}}\large(1 - \frac{1}{8n+8}\large).\label{eq-Rnass} 
\end{equation}
\end{lemma}

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

(\ref{eq-Rnass}) 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-En} $n \geq 1,$ 
akkor a $(0,1,n)$-páros sorozatok $E(n)$ száma
\begin{equation}
E(n) = \frac{1}{2} \left ( \binom{2n -1}{n} + \binom{n - 1}{\lfloor n \rfloor} \right ).\label{eq-En}
\end{equation}
\end{lemma}

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

A \ref{lemma-Rn}. és a \ref{lemma-En}. 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-En}. lemma alapján pontosan 
meg tudjuk adni $E(n)$ aszimptotikus nagyságrendjét.

\begin{lemma} Ha\label{lemma-Entul} $n \geq 1,$ akkor
\begin{equation}
\frac{E(n + 2)}{E(n + 1)} > \frac{E(n + 1)}{E(n)},\label{eq-Enmon}
\end{equation}
\begin{equation}
\lim E _{n \rightarrow \infty} = 4,\label{eq-Enlim}
\end{equation}
továbbá 
\begin{equation}
\frac{4^n}{\sqrt{\pi n}}(1 - \delta _3(n)) < E(n) < \frac{4^n}{\sqrt{\pi n}}(1 - \delta _4(n)),\label{eq-Ennass} 
\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-Rnjell}. lemma bizonyításához.
\end{proof}

Amint azt a következő állítás és a \ref{tab-regevenratio}. ábra is mutatja, az $E(n)/R(n)$ hányadosok sorozata 
monoton csökkenve $\frac{1}{2}$-hez tart. 

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

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

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

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

\begin{proof} A nullát tartalmazó $n$-szabályos sorozatok halmaza kölcsönösen egyértelműen leképezhető az $(n - 1,n)$-szabályos 
sorozatok halmazára. Az utóbbi halmaz elemszáma pedig a \ref{lemma-Rn}. 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} A $(0,1,n)$-szabályos sorozatokban $0, \ldots, n - 1$ vagy $n$ nulla van. Az $i$ nullát és $n - i$ pozitív elemet 
tartalmazó $(0,1,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, grafikus-e a vizsgált sorozat. Mivel a \ref{lemma-nullasszab}. lemma szerint a páros sorozatoknak 
aszimptotikusan csak nullmértékű hányada tartalmaz nullát (és ez a hányad a gyakorlat számára legérdekesebb $n$-ekre sem nagy), 
konkrét sorozatok vizsgálatánál nem jelentős az időmegtakarítás. Amikor viszont az összes $n$-páros sorozatot elemezzük 
(az átlagos futási idő vagy $G(n)$ meghatározása érdekében), nagyon hasznos a következő lemma.

Legyen $G_z(n)$ a nullamentes grafikus $n$-páros sorozatok száma.

\begin{lemma} Ha\label{lemma-nullaatl} $n \geq 2,$ akkor a $(0,1,n)$-grafikus sorozatok száma 
\begin{equation}
G(n) = G_z(n) + G(n - 1). \label{eq-zerofreegood}
\end{equation}  
\end{lemma}
\begin{proof} Az $n$-grafikus sorozatokban vagy $s_n = 0,$ vagy $s_n > 0.$ Az előbbiekben vagy $s_1 = n -1,$ vagy $s_1 < n_ 1.$ 
Ha $s_1 = n - 1$ és $s_n = 0,$ akkor az $s$ sorozat biztosan nem grafikus, mert nincs benne elég pozitív elem. Az $s_1 < n -1$ és 
$s_n = 0$ tulajdonságú sorozatok $n - 1$ hosszú fejei pontosan a $(0,1,n - 1)$-grafikus 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 $(1,1,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}

\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 $s = (s_1^{e_1},\ldots,s_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 grafikus sorozatok $G(n)$ számának jellemzésével kapcsolatos kutatások ígéretes iránya a páros számok pozitív összeadandókra 
való felbontása, és annak vizsgálata, hogy az ilyen felbontások közül melyek $(0,1,n)$-grafikusak 
\cite{BarnesS1995,BarnesS1997,Burns2007}. 
Ezek segítségével sikerült a grafikus 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 $(0,1,n)$-grafikus 
sorozatok  $G(n)$ száma a következő korlátok közé esik:
\begin{equation}
\frac{4^n}{cn} < G(n) <  \frac{4^n}{(\log n)^C \sqrt{n}} \ .
\end{equation}
\end{lemma}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tesztelő algoritmusok\label{sec-teszt}}
Sorozatok megvalósíthatóságának vizsgálata során természetes észrevétel, hogy az $s$ 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{pozitív}, majd egy \idez{paritásos}, egy \idez{binomiális}   
és végül egy \idez{fejfelező} tesztelő/szűrő algoritmust mutatunk be. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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. legyen $p$ az $s$ sorozat 
pozitív elemeinek a száma. 

\begin{corollary} Ha\label{lemma-pozitiv} $n \geq 1$ és $s = (s_1, \ldots , s_n)$ $(0,1,n)$-grafikus sorozat, akkor
\begin{equation}
s_1  \leq p - 1 \quad \mbox{vagy} \quad s_1 = 0.  \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)$; \\
$s = (s_1, \ldots, s_n)$: $(0,1,n)$-szabályos sorozat. 

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó.

\textit{Munkaváltozó.} $p$: a bemenetben lévő pozitív elemek száma.


\bigskip
\noindent \textsc{Pozitív-teszt}$(n,s,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 $L = 0$ \\
\hspace{-7mm}02 $p = n$ \\
\hspace{-7mm}03 \textbf{while} \= $s_p = 0$ \\
\hspace{-7mm}04                \> $p = p - 1$ \\
\hspace{-7mm}05 \textbf{if} \= $s_1 > p - 1$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $L = 1$ \\
\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. 
 
Ennek az algoritmusnak a javított változata az alábbi \textsc{Gyors-teszt} (GyT) \cite{LuczS2011}. 


\bigskip
\noindent \textsc{Gyors-teszt}$(n,s,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}01 \textbf{if} \= $s_{s_1} == 0$ \\
\hspace{-7mm}02             \> $L = 0$ \\
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\end{tabbing}

A \textsc{Gyors-teszt} ugyanazt az eredményt adja, mint \textsc{Pozitív-teszt}, a futási ideje azonban mindig $\Theta(1)$. 

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

\begin{lemma} Ha\label{lemma-paritas} $n \geq 1$ és $s$ $(1,1,n)$-grafikus 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)$; \\
$s = (s_1, \ldots, s_n)$: $(0,1,n)$-szabályos sorozat.

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó.

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


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

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Binomiális teszt (Bt)\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$ az $s$ sorozat pozitív elemeinek a száma.

\begin{lemma} Ha\label{lemma-binom} $n \geq 1$ és $s$ $(0,1,n)$-grafikus 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)$; \\
$s = (s_1, \ldots, s_n)$: páros sorozat; \\
$H = (H_1, \ldots, H_n)$: $H_i$ az $s$ sorozat első $i$ elemének összege.

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó. 

\textit{Munkaváltozók.} $i$: ciklusváltozó; \\
$p$: az $s$ sorozat pozitív elemeinek a száma. 

\bigskip
\noindent \textsc{Binomiális-teszt}$(n,s,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} \= $s_p == 0$ \\
\hspace{-7mm}03                \> $p = p - 1$ \\
\hspace{-7mm}04 \textbf{if} \= $p == 1$ \\
\hspace{-7mm}05             \> $L = 0$ \\
\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} + s_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 = 0$ \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}15 $L = 1$ \\
\hspace{-7mm}16 \textbf{return} $L$
\end{tabbing}

Az algoritmus azért kezdi $s$ 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. A várható futási idő szempontjából viszont a konstans idő alatt 
hatékony \textsc{Gyors-teszt} hasznos lehet.

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.  

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fej felezése (Ft) \label{subsec-fejfelezteszt}}
Az $s$ 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 az $(s_1,\ldots,s_{h_i})$ sorozatot az $i$ indexhez tartozó fej  
\textit{elejének}, az $(s_{h_i+1},\ldots,s_i)$ sorozatot pedig az $i$ indexhez tartozó fej \textit{végének} nevezzük.

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

\begin{proof} Legyen $G$ az $s $ 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  
\begin{equation}
X_{i,1} \leq \min(H_{h_i},T_n - T_i,h_i(n - i)).\label{eq-HS1}
\end{equation}

Hasonló gondolatmenettel kapjuk, hogy 
\begin{equation}
X_{i,2} \leq \min(H_i - H_{h_i},T_n - T_i,(i - h_i)(n - i)).\label{eq-HS2}
\end{equation}
 
$X_{i,3}$ legfeljebb $h_i(i - h_i)$ és legfeljebb $H_i$, ezért  
\begin{equation}
X_{i,3} \leq \min(h_i(i - h_i),H_i).\label{eq-HS3} 
\end{equation}

$X_{i,4}$ legfeljebb $\binom{h_i}{2}$ és legfeljebb $H_{h_i}$, így  
\begin{equation}
X_{i,4} \leq \min(\binom{h_i}{2},H_{h_i}),\label{eq-HS4} 
\end{equation}
míg $X_{i,5}$ legfeljebb $\binom{i - h_i}{2}$ és legfeljebb $H_i - H_{h_i},$, ahonnan  
\begin{equation}
X_{i,5} \leq \binom{i - h_i}{2}.\label{eq-HS5} 
\end{equation}
Az is követelmény, hogy a farok részei együtt nem léphetik túl a farok kapacitását, azaz,   
\begin{equation}
X_{i,1} + X_{i,2} \leq T_i.\label{eq-HS6}
\end{equation}

A \eqref{eq-HS1}, \eqref{eq-HS2}, \eqref{eq-HS3}, \eqref{eq-HS4} és \eqref{eq-HS5} egyenlőtlenségeket összegezve azt kapjuk, hogy   
\begin{equation}
H_i \leq X_{i,1} + X_{i,2} + X_{i,3} + 2X_{i,4} + 2X_{i,5}.\label{eq-HS7}
\end{equation}

Ha az \eqref{eq-HS1}, \eqref{eq-HS2}, \eqref{eq-HS3}, \eqref{eq-HS4} és \eqref{eq-HS5} egyenlőtlenségeket a \eqref{eq-HS7}  
egyenlőtlenségbe helyettesítjük, akkor \eqref{eq-HSa} adódik, míg \eqref{eq-HS6} ekvivalens a  \eqref{eq-HSb} egyenlőtlenséggel.
\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)$; \\
$s = (s_1, b_2, \ldots, s_n)$: $n$-faroktesztelt sorozat; \\
$H = (H_1,\ldots,H_n)$: $H_i$ az $s$ sorozat első $i$ elemének összege; \\
$T = (T_1,\ldots,T_n)$: $T_i$ az $s$ sorozat utolsó $n - i$ elemének összege.

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó. 
 

\textit{Munkaváltozók}. $i$: ciklusváltozó; \\
$X = (X_1,X_2,X_3,X_4,X_5)$: $X_j$ a fej vége $X_{i,j}$ paraméterének aktuális értéke.   

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

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

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





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\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 \ref{tab-sorozatszam}. táblázat a \textsc{Binomiális-teszt} és a  
\textsc{Fejfelező-teszt} programok futási eredményeit tartalmazza. 

A \ref{tab-numberofseq}. táblázat a nullamentes binomiális és nullamentes faroktesztelt sorozatok számát, továbbá a 
grafikus sorozatok számát és a grafikus sorozatok számának szomszédos $n$ helyeken felvett értékei hányadosát tartalmazza 
$n = 1, \ldots, 29$ esetén.  ?????????????????????????????????????

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

A \ref{tab-apprrelativ}. táblázat azt jellemzi, hogy a vizsgált közelítő algoritmusok a szabályos sorozatoknak milyen hányadát 
szűrik ki. A táblázat a nullamentes páros sorozatok száma $(E_z(n))$ mellett tartalmazza a nullamentes binomiális $(B_z(n))$, 
a nullamentes faroktesztelt $(F_z(n))$ és a grafikus sorozatok $(G(n))$ számának, valamint a szabályos sorozatok számának hányadosát.


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

\begin{table}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||c|r|c|c|c|c||}  \hline \hline
$n$ &   $E_z(n)$           & $E_z(n)/R(n)$       & $B_z(n)/R(n)$       &$F_z(n)/R(n)$         &$G(n)/R(n)$ \\ \hline \hline
$1$ &$0$               &$0.000000$         &$1.000000$         &$1.000000$          &$1.000000$  \\ \hline
$2$ &$1$               &$0.333333$         &$0.666667$         &$0.666667$          &$0.666667$ \\ \hline
$3$ &$2$               &$0.300000$         &$0.400000$         &$0.400000$          &$0.400000$ \\ \hline
$4$ &$9$               &$0.257143$         &$0.314286$         &$0.314286$          &$0.314286$ \\ \hline
$5$ &$28$              &$0.230159$         &$0.246032$         &$0.246031$          &$0.246032$ \\ \hline
$6$ &$110$             &$0.238095$         &$0.222943$         &$0.220779$          &$0.220779$ \\ \hline
$7$ &$396$             &$0.231352$         &$0.203380$         &$0.200466$          &$0.199301$ \\ \hline 
$8$ &$1 519$           &$0.236053$         &$0.195183$         &$0.191142$          &$0.188500$ \\ \hline
$9$ &$5 720$           &$0.235335$         &$0.188276$         &$0.183793$          &$0.179391$ \\ \hline
$10$&$21 942$          &$0.237524$         &$0.184460$         &$0.179502$          &$0.173375$ \\ \hline 
$11$&$83 980$          &$0.238098$         &$0.181290$         &$0.175977$          &$0.168260$ \\ \hline
$12$&$323 554$         &$0.239301$         &$0.179145$         &$0.173508$          &$0.164278$ \\ \hline
$13$&$1 248 072$       &$0.240000$         &$0.177368$         &$0.171500$          &$0.160821$ \\ \hline
$14$&$4 829 708$       &$0.240784$         &$0.176014$         &$0.169960$          &$0.157882$ \\ \hline
$15$&$18 721 080$      &$0.241379$         &$0.174884$         &$0.168684$          &$0.155271$ \\ \hline
$16$&$72 714 555$      &$0.241946$         &$0.173965$         &$0.167634$          &$0.152950$ \\ \hline
$17$&$282 861 360$     &$0.242424$         &$0.173188$         &$0.166738$          &$0.150844$ \\ \hline
$18$&$1 101 992 870$   &$0.242860$         &$0.172533$         &$0.165972$          &$0.148926$ \\ \hline
$19$&$4 298 748 300$   &$0.243243$         &$0.171970$         &$0.165306$          &$0.147158$ \\ \hline
$20$&$16 789 046 494$  &$0.243590$         &$0.171486$         &$0.164725$          &$0.145521$ \\ \hline
$21$&                  &                   &                   &                    &$0.143997$ \\ \hline
$22$&                  &                   &                   &                    &$0.142569$ \\ \hline
$23$&                  &                   &                   &                    &$0.141228$ \\ \hline
$24$&                  &                   &                   &                    &$0.139961$ \\ \hline
$25$&                  &                   &                   &                    &$0.138762$ \\ \hline 
$26$&                  &                   &                   &                    &$0.137625$ \\ \hline
$27$&                  &                   &                   &                    &$0.136542$ \\ \hline
$28$&                  &                   &                   &                    &$0.135509$ \\ \hline
$29$&                  &                   &                   &                    &$0.134521$ \\ \hline \hline
\end{tabular}
\caption{The number of zerofree even sequences, further the ratio of the numbers binomial/regular, headsplitted/regular and 
graphical/regular sequences.\label{tab-apprrelativ}}
\end{center}
\end{small} 
\end{table}

A \ref{tab-testtime}. táblázat 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{table}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||r|r|r|r|r||}  \hline \hline
$n$        & Bt, s              & Bt, művelet     & Ft, s              & Ft, művelet   \\ \hline
1          &         0          &         14        &         0          &         15        \\
2          &         0          &         41        &         0          &         43        \\
3          &         0          &         180       &         0          &         200      \\
4          &         0          &         716       &         0          &         815      \\
5          &         0          &         2 918     &         0          &         3 321   \\
6          &         0          &         11 918    &         0          &         13 675 \\
7          &         0          &         48 952    &         0          &         56 299 \\
8          &         0          &         201 734   &         0          &         233 182           \\
9          &         0          &         831 374   &         0          &         964 121           \\
10         &         0          &         3 426 742 &         0          &         3 988 542        \\
11         &         0          &     14 107 824    &         0          &         16 469 036      \\
12         &         0          &   58 028 152      &         0          &         67 929 342      \\
13         &         0          &    238 379 872    &         0          &         279 722 127    \\
14         &         0          &    978 194 400    &         1          &         1 150 355 240 \\
15         &         2          &     4 009 507 932 &         3          &         4 724 364 716 \\
16         &         6          & 16 417 793 698    &         13         &         19 379 236 737          \\
17         &         26         & 67 160 771 570    &         51         &         79 402 358 497          \\
18         &        106         & 274 490 902 862   &         196        &         324 997 910 595        \\
19         &       423          & 1 120 923 466 932 &         798        &         1 328 948 863 507     \\
20         &      1 627         & 4 573 895 421 484 &         3 201      &         5 429 385 115 097     \\ \hline \hline
\end{tabular}
\caption{Running time of \textsc{Binomial-Test} (BT) and \textsc{Headsplitter-Test} (HT) in secundum and 
as the number of operations for $n = 1, \ \ldots, \ 20$.\label{tab-testtime}}
\end{center} 
\end{footnotesize}
\end{table}

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 grafikus, í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 grafikus: 
(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 grafikusak, 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 grafikus 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 grafikus 
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 grafikus 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{tab-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{table}[!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{tab-pontosido}}
\end{center} 
\end{footnotesize}
\end{table}

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. 

Figure \ref{tab-precisetime} contains the total number of operations of the algorithms HHSo, HHSh, EG, and EGL 
required for the testing of all even sequences of length $n = 1, \ \ldots, 15$. The operations necessary to generate the sequences 
are included.

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

Comparison of the first two columns shows that algorithm HHSh is much quicker than HHSo, especially if $n$ increases. Comparison 
of the third and fourth columns shows that we get substantial decrease of the running time if we have to test 
the input sequence only in the check points. Finally  the comparison of the third and fifth columns demonstrates the 
advantages of a linear algorithm over a quadratic one. 

Figure \ref{tab-EGL} shows the running time of \textsc{Erd\H os-Gallai-Linear} in secundum and operation, and also 
the amortized number of operation/even sequence.

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

The most interesting data of Figure \ref{tab-EGL} are in the last column: they show that the number of 
operations/investigated sequence/length of the investigated sequence is monotone decreasing (see \cite{RuskeyCES1994}).

Figure \ref{tab-EGJrounds} shows the distribution of the $E(n) - G(n)$ even nongraphical sequences according to 
the number of tests made by \textsc{Erdős-Gallai-ugró} to exclude the given sequence for  
$n = 3, \ \ldots, \ 15$ vertices. $f_i(n) = f_i$ gives the frequency of even nongraphical sequences of length $n$, 
which requeired exactly $i$ round of the test.

These data show, that the maximal number of tests is about $\frac{n}{2}$ in all lines.  

\begin{table}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||r|r|r|r|r|r|r|r|r|r||}  \hline \hline
$E(n)-G(n)$&$n/i$    &$f_1$     & $f_2$     &  $f_3$&   $f_4$& $f_5$   & $f_6$ & $f_7$ \\ \hline \hline
  $2$     &  $3$     &$2$       & $0$       &  $0$  &   $0$  &   $0$   &  $0$  & $0$   \\
  $8$     &  $4$     &$6$       & $2$     &   $0$   &   $0$  &   $0$   &  $0$  & $0$  \\
  $35$    & $5$      &$33$      &   2     &  0      & 0      & 0       &  $0$  & $0$   \\
 $134$    & $6$      &$122$     &  $12$   & $0$     &   0    &   0     &  0    &   0   \\
$526 $    &  $7$     &$459$     &$65$     & $2$     & $2$    & 0       & 0     &  0     \\
$2022$    & $8$      &$1709$    &$289$    &$24$     & $0$    &  $0$    &  0    & 0     \\
$7829$    & $9$       &$6421$    &$1228$   &$176$    & $4$    &   $0$  &  0     & 0      \\
$30236$   & $10$      &$24205$   &$4951$   &$1013$   &$67$    &   $0$  &  0     & 0       \\
$115136$  & $11$      &$91786$   &$19603$  &$5126$   &  $610$ &   $11$ &  0     & 0       \\
$454153$  & $12$      &$349502$  &$76414$  &$23755$  & $4274$ &  $208$ &  0     & 0       \\
$1764297$ & $13$      &$1336491$ &$296036$ &$104171$ &$25293$ & $2277$ &  29    &$0$    \\
$6863156$ & $14$      &$5128246$ &$1142470$&$439155$ &$133946$&$18673$ & $666$  &$0$     \\
$26738476$& $15$      &$19739076$&$4404813$&$1803496$&$655291$&$127116$& $8603$ &$81$   \\ \hline \hline
\end{tabular}
\caption{Distribution of the even nongraphical sequences according to the number of tests made by \textsc{Erd\H os-Gallai-Jumping} 
to exclude the given sequence for $n = 3, \ \ldots, \ 15$.\label{tab-EGJrounds}}
\end{center} 
\end{footnotesize}
\end{table}

Figure \ref{tab-EGJavrounds} shows the average number of required rounds for the nongraphical, graphical and all even 
sequences. The data of the column belonging to $G(n)$ are computed using Lemma \label{cor-regrain}. It is remarkable that 
the sequences of the coefficients are monotone decreasing in the last three columns. 


\begin{table}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||r|r|r|r|c|c|c||}  \hline \hline
$n$       & $E(n)$    &$G(n)$    &  $E(n) - G(n)$ & átlagos     & átlagos   & átlagos          \\  
          &           &          &                &$E(n) - G(n)$& $G(n)$       & $E(n)$   \\ \hline \hline
$3$       &  $6$      &  $4$     &    $2$         &$0.3333n$ & $0.8000n$   & $0.6444n$ \\ \hline
$4$       &  $19$     &  $11$    &    $8$         &$0.3125n$ & $0.5714n$   & $0.4661n$    \\  \hline
$5$       &  $66$     &  $31$    &     $35$       &$0.2114n$ & $0.5555n$   & $0.3730n$ \\ \hline
$6$       &  $236$    &  $102$   &     $134$      &$0.1967n$ & $0.5455n$   & $0.3730n$    \\ \hline
$7$       &  $868$    &  $342$   &     $526$      &$0.1649n$ & $0.5385n$   & $0.3475n$    \\ \hline
$8$       &  $3233$   &  $1213$  &     $2020$     &$0.1458n$ & $0.5333n$   & $0.2911n$ \\ \hline
$9$       & $12190$   & $4363$   &     $7829$     &$0.1337n$ & $0.5294n$   & $0.2753n$ \\ \hline
$10$      &$46232$    & $16016$  &     $30216$    &$0.1249n$ & $0.5263n$   & $0.2700n$       \\ \hline
$11$      &$174484$   & $59348$  &     $115136$   &$0.1175n$ & $0.5238n$   & $0.2557n$       \\ \hline
$12$      &$676270$   & $222117$ &     $454153$   &$0.1085n$ & $0.5217n$   & $0.2444n$ \\ \hline
$13$      &$2603612$  & $836313$ &     $1767299$  &$0.1035n$ & $0.5200n$   & $0.2373n$ \\ \hline
$14$      &$10030008$ &$3166852$ &   $6863156$    &$0.0960n$ & $0.5185n$   & $0.2294n$       \\ \hline
$15$      &$38761096$ &$12042620$&  $26718476$    &$0.0934n$ & $0.5172n$   & $0.2251n$  \\ \hline \hline
\end{tabular}
\caption{Weighted average number of tests made by \textsc{Erdős-Gallai-ugró} által az $n = 3, \ldots, 15$ 
hosszú sorozatok vizsgálata során végzett tesztek átlagos száma.\label{tab-EGJavrounds}}
\end{center} 
\end{small}
\end{table}


Figure \ref{tab-EGs1} presents the distribution of the graphical sequences according to their first element. 
These data help at the design of the algorithm \textsc{Erdős-Gallai-leszámláló} which computes the new values of $G(n)$ 
(in the slicing of the computations belonging to a given value of $n$).

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

We see in Figure \ref{tab-EGs1} that from $n = 6$ the multiplicities increase up to $n - 2,$ and the last positive value is smaller 
then the last but one element.  

Az \textsc{EG-lineárisan-leszámláló} algoritmus teljes és az elemenkénti futási időit tartalmazza a \ref{tab-EG-lineárisan}. ábra. 

\begin{table}[!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{table}

A \ref{tab-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{table}[!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{table}


Az \ref{tab-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{table}[!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 grafikus sorozatokat is figyelembe vesszük, 
illetve ha nem.\label{tab-EGrounds-av}}
\end{footnotesize}
\end{table}

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

\begin{table}[!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 grafikus sorozatok $b_1$ szerinti eloszlása.\label{tab-EGb1}}
\end{center} 
\end{scriptsize}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{$(0,b,n)$-gráfok \label{sec-0bundi}}
Ebben a részben a klasszikus tételek $(0,b,n)$-gráfokra való kiterjesztésével foglalkozunk.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erdős-Gallai tétel és Chungphaisan tétele}
1974-ben Chungphaisan \cite{Chungphaisan1974} mind az Erdős-Gallai tételt, mind pedig a Havel-Hakimi tételt kiterjesztette 
$(0,b,n)$-gráfokra. Az EG tétel kiterjesztése a következő.

\begin{theorem} {\emph{(Chungphaisan \cite{Chungphaisan1974})}\label{th-ChEG}}
Legyen $n \geq 1$. A $(0,b,n)$-szabályos $s = (s_1, \ldots, s_n)$ sorozat akkor és csak akkor $(0,b,n)$-grafikus, ha  
\begin{equation}
\sum _{i=1}^n s_i \quad  \mbox{páros}
\label{eq-EG0} 
\end{equation}
és
\begin{equation}\label{eq-EG1} 
\sum_{i=1}^j s_i - bj(j-1) \leq \sum _{k = j  + 1}^n \min(bi, s_k) \quad (j=1, \ldots, n-1). 
\end{equation}
\end{theorem}

A tételen alapuló algoritmus legrosszabb esetben négyzetes időt igényel. A következő állítás lehetővé teszi, hogy  
a $(0,b,n)$-szabályos sorozatokat legrosszabb esetben $\Theta(n)$ idő alatt teszteljük.

\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})}  Ha\label{th-ChEGL} $n \geq 1$, a $(0,b,n)$-szabályos 
$s = (s_1,\ldots,s_n)$ sorozat akkor és csak akkor $(0,b,n)$-grafikus, ha
\begin{equation}
H_n  \quad   \mbox{páros}
\end{equation}
és 
\begin{equation}
H_i > bi(y_i - 1) + H_n - H_y    \quad (i = 1, \ldots, n - 1), 
\end{equation}
ahol 
\begin{equation}
y_i = \max(i,w_i)   \quad (i = 1, \ldots, n - 1).
\end{equation}
\end{theorem}

\begin{proof}
\end{proof}

A következő \textsc{Chungphaisan-Erdős-Gallai-lineáris} algoritmus (ChEGl) -- amely az EG algoritmus természetes általánosítása -- 
$O(n)$ idő alatt eldönti, hogy egy $(0,b,n)$-szabályos sorozat $(0,b,n)$-grafikus-e.

\textit{Bemenet.} $n$: csúcsok száma $(n \geq 1)$; \\ 
$s = (s_1, \ldots, s_n)$: $(0,b,n)$-szabályos sorozat;
$b$: a gráf két csúcsa között megengedett élek maximális száma. 

\textit{Kimenet.} $L$: $s$ grafikusságát jelső logikai változó.

\textit{Munkaváltozók.} $i$: ciklus változók; \\ 
$w = (w_1,\ldots,w_n)$: $w_i$ az  $i$ indexhez tartozó súlypont.


\bigskip
\noindent \textsc{Chungphaisan-Erdős-Gallai-lineáris}$(n, s, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_{1} = s_1$                                 \` \textbf{//} 01 sor: $H_1$ kezdeti értékének beállítása\\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$      \` \textbf{//} 02--03. sor: $H$ további elemeinek számítása\\
\hspace{-7mm}03              \> $H_{i} = H_{i-1} + s_{i}$    \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ páratlan                 \` \textbf{//} 04--06. sor: paritás ellenőrzése  \\
\hspace{-7mm}05             \> $L = 0$                        \` \textbf{//} 05--06. sor: páratlan sorozat elutasítása  \\
\hspace{-7mm}06             \> \textbf{return}\\
\hspace{-7mm}07 $w = n$                                      \` \textbf{//} 07. sor: első súlypont értékének beállítása \\
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$    \`  \textbf{//} 08--15. sor: $s$ tesztelése    \\ 
\hspace{-7mm}09              \> \textbf{while} \= $s_w < ib$ és $w > 0$       \\ 
\hspace{-7mm}10              \>                \> $w = w - 1$             \\ 
\hspace{-7mm}11              \> $y = \max(i,w)$ \\              
\hspace{-7mm}12              \> \textbf{if} \= $H_i > bi(y - 1) + H_n - H_y$  \\
\hspace{-7mm}13              \>             \> \textbf{return} $L$    \` \textbf{//} 13. sor: $s$ nem grafikus \\
\hspace{-7mm}14 $L = 1$                         \` \textbf{//} 14--15. sor:  $s$ grafikus \\
\hspace{-7mm}15 \textbf{return} $L$
\end{tabbing}  
  
  
\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})} \textsc{ChEGl} futási ideje minden esetben $\Theta(n).$
\end{theorem}

\begin{proof} A 01--06 sorok végrehajtása $\Theta(n)$ időt igényel. Mivel $w$ szigorúan monoton csökken a program végrehajtása 
során, ezért a 07--14 sorok  $O(n)$ időt igényelnek, így az algoritmus futási ideje minden esetben $\Theta(n).$ 
\end{proof}    

Legyen $b = 3$ és $s = (13,10,5,5,4,1).$  $H_6 = 38$ páros. Ha $i = 1,$ akkor $w_i = y = 5$ és a 11. sor feltétele 
$(13 \leq 3 \cdot 1 \cdot (5 - 1))$ nem teljesül. Ha $i = 2,$ akkor viszont $w_i = y = 2$ és a feltétel teljesül  
$(23 > 3 \cdot 2 \cdot (2 - 1)) + 5 + 5 + 4 + 1),$ ezért $s$ \textit{nem} $(0,3,6)$\textit{-grafikus.} 

Maradjon $b$ $3,$ de $s$-et változtassuk meg: legyen  $s' = (13,10,5,5,4,3).$ Az előző példához képest a futás során az első változás 
az, hogy amikor $i = 2,$ akkor $(23 \leq 3 \cdot 2 \cdot (2 - 1)) + 5 + 5 + 4 + 3,$ és így a 11. sorban lévő feltétel 
nem teljesül, és ugyanez az eredmény $i = 3, \ 4$ és $4$ esetén is, ezért $s'$ $(0,3,6)$\textit{-grafikus}.   

A következő táblázatokban bemutatjuk, hogyan oszlanak meg  a kizárt grafikus és nemgrafikus sorozatok az egyes menetek között. 
Azt is jellemezzük, hogy átlagosan hány meneten át kell egy grafikus, illetve nemgrafikus sorozatot a kizárásáig tesztelni, és 
azt is, hogy a menetek hányadrészét fordítjuk átlagosan egy sorozat tesztelésére.

A \ref{tab-ChEGl02n}. táblázat a ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok számát 
tartalmazza $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 6   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	  	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	 &	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok száma   
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl02n}}
\end{table}

A \ref{tab-CgEGl02g}. táblázat a ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok számát 
tartalmazza $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 6   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	  	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	 &	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok száma   
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl02g}}
\end{table}

A következő \ref{tab-ChEGl02hat} táblázat a ChEGl algoritmus hatékonyságát jellemzi 
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl02hat}

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrr||} \hline \hline
n/\mbox{jellemző}  &  X      &  Y    &    Z    &   X'          &  Y'  &    Z'  \\ \hline
  1                &         & 	     &         &	           &	  &			\\
  2                &         & 	     &	       &               &	  &						\\
  3                &         & 	     &	  	   &               & 	  &		      		\\
  4                &         & 	     &	       &	           &	  &					\\
  5                &         & 	     &		   &	           &	  &				 \\
  6                &         &    	 &	       &	           &	  &		       		\\
  7                &         & 	     &	 	   &	           &	  &		       	\\
  8                &         & 	     &	  	   &	           &	  &		      	\\
  9                &         &   	 &		   &	           &	  &		       		\\
 10                &         &   	 &		   &	           &	  &		    			\\
 11                &         & 	     &	 	   &	           &	  &		    	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGl hatékonysági jellemzői $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl02hat}}
\end{table}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Az első 6 és 18 sor elemzése \label{subsec-0bn-analysis}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Gyors ChEGgy algoritmus (ChEGgy)\label{subsec-GyChung}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi tétel és Chungphaisan tétele}
Chungphaisan \cite{Chungphaisan1974} a következő módon terjesztette ki a Havel-Hakimi tételt. 

\begin{theorem}  \emph{(Chungphaisan \cite{Chungphaisan1974})} Legyen $n \geq 2$ és $b \geq 1.$ Az $s = (s_1, \ldots, s_n)$ 
$(0,b,n)$-szabályos sorozat akkor és csak akkor $(0,b,n)$-grafikus, ha a $j$-edik $b$-redukált $w^*_j = (w_1^*,\ldots,w_{n-1}^*)$ 
sorozat $(0,b,n)$-grafikus minden $1 \geq j \geq n$ indexre.
\end{theorem}

A tételen alapuló algoritmus nagyon lassú. A tétel következő javítása azonban lehetővé teszi, hogy 
a tesztelést legrosszabb esetben is el tudjuk végezni $O(n)$ idő alatt.

\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})} Legyen $n \geq 1$ és $b \geq 1$ Nemnegatív egészek $s = (s_1, \ldots, s_n)$ 
$(0,1,n)$-szabályos sorozata akkor és csak akkor $(0,b,n)$-grafikus, ha
\begin{equation}
???
\end{equation}
és
\begin{equation}
???.
\end{equation}
\end{theorem}

A következő \textsc{Chungphaisan-Havel-Hakimi-lineáris} algoritmus (ChHHl) -- amely a HH algoritmus természetes általánosítása -- 
$O(n)$ idő alatt eldönti, hogy egy $(0,b,n)$-szabályos gráf $(0,b,n)$-grafikus-e.

\textit{Bemenet.} $n$: csúcsok száma $(n \geq 1)$; \\ 
$s = (s_1, \ldots, s_n)$: $(0,b,n)$-grafikus sorozat;
$b$: a gráf két csúcsa között megengedett élek maximális száma. 

\textit{Kimenet.} $L$: $s$ grafikusságát jeltő logikai változó.

\textit{Munkaváltozó.} $i$: ciklus változó; \\
$w = (w_1,\ldots,w_n)$: $w_i$ az  $i$ indexhez tartozó súlypont.


\bigskip
\noindent \textsc{Chungphaisan-Havel-Hakimi-lineáris}$(n, s, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L = 0$                 \` \textbf{//} 01. sor: a gyakoribb érték beállítása \\
\hspace{-7mm}02 \textbf{if} \= $s_1 == 0$   \` \textbf{//} 02--04. sor: a nullákból álló sorozat grafikus \\ 
\hspace{-7mm}03             \> $L = 1$ \\
\hspace{-7mm}04             \> \textbf{return} $L$ \\
\hspace{-7mm}05 \textbf{if} \= $s_{\lceil s_1/b + 1 \rceil} == 0$   \` \textbf{//} 05--07. sor: $s_1$ ellenőrzése konstans idő alatt \\ 
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $H_{1} = s_1$                                 \` \textbf{//} 07 sor: $H_1$ kezdeti értékének beállítása\\
\hspace{-7mm}08 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$      \` \textbf{//} 08--09. sor: $H$ további elemeinek számítása\\
\hspace{-7mm}09              \> $H_{i} = H_{i-1} + s_{i}$    \\
\hspace{-7mm}10 \textbf{if} \= $H_n$ páratlan                 \` \textbf{//} 10--11. sor: paritás tesztelése   \\
\hspace{-7mm}11             \>  \textbf{return}  $L$ \\
\hspace{-7mm}12 $w_1 = n$                                      \` \textbf{//} 12. sor: első súlypont kezdeti értékének beállítása \\
\hspace{-7mm}13 \textbf{while} \= $s_{w_1} < b$ and $w_1 > 0$       \\ 
\hspace{-7mm}14                \> $w_1 = w_1 - 1$             \\ 
\hspace{-7mm}15 \textbf{if} \= $s_1 > b(w_1 - 1) + H_n - H_{w_1}$ \\
\hspace{-7mm}16             \> \textbf{return} $L$ \\
\hspace{-7mm}17 $r_1 = b(w_1 - 1) + H_n - H_{w_1} - s_1$  \` \textbf{//} 12. sor:  első maradék számítása \\       
\hspace{-7mm}18 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$    \`  \textbf{//} 18--26. sor: $s$ tesztelése \\ 
\hspace{-7mm}19              \> \textbf{if} \= $H_{i-1} \geq H_n/2$ vagy $s_i \leq 1$ vagy $s_{i+1} = 0$ \` \textbf{//} 19--21. sor: $s$ elfogadása \\ 
\hspace{-7mm}20              \>             \> $L = 1$ \\
\hspace{-7mm}21              \>             \> \textbf{return} $L$     \\
\hspace{-7mm}22              \> $w_i = w_{i-1}$                       \` \textbf{//} 22--24. sor: \\ 
\hspace{-7mm}23              \> \textbf{while} \= $s_i < bi$ és $w_i > 0$ \\              
\hspace{-7mm}24              \>                \> $w_i = w_i - 1$  \\
\hspace{-7mm}25              \> \textbf{if} \= $w_i \geq i$    \` \textbf{//} 25--27. sor:  esetszétválasztás  \\
\hspace{-7mm}26              \>             \> \textbf{if} \= $s_i > b(w_i-1) + r_{i-1} + H_{w_{i-1}} -H_{w_i}$ \\ 
                             \>             \>             \> \quad $ - b(w_{i-1} - w_i)(i - 1)$  \` \textbf{//} 26. sor: $s_i$ tesztelése \\
\hspace{-7mm}27              \>             \>             \> \textbf{return} $L$ \\
\hspace{-7mm}28              \>             \> $r_i = b(w_i - 1) + r_{i-1} + H_{w_{i-1}} - H_{w_i}$ \\
                             \>             \> \quad $- b(w_{i-1} - w_i)(i - 1) - s_i$       \` \textbf{//}28. sor: maradék frissítése\\
\hspace{-7mm}29              \> \textbf{else} \textbf{if} \= $s_i > bw_i + r_{i-1} + H_{w_{i-1}} -H_{w_i}$ \\ 
\hspace{-7mm}30              \>             \> \quad $- b(w_{i-1} - w_i)(i - 1)$       \\
\hspace{-7mm}31              \>                           \> \textbf{return} $L$ \\
\hspace{-7mm}32              \>             \> $r_i = bw_i + r_{i-1} + H_{w_{i-1}} -H_{w_i}$ \\
                             \>             \> \quad $- b(w_{i-1} - w_i)(i - 1) - s_i$       \` \textbf{//}31. sor: maradék frissítése\\
\hspace{-7mm}33 $L = 1$    \` \textbf{//} 33--34. sor:  $s$ elfogadása \\
\hspace{-7mm}34 \textbf{return} $L$
\end{tabbing}  
  
A következő állítás jellemzi \textsc{ChHHl} futási idejét.
  
\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})} \textsc{ChHHl} futási ideje minden esetben $\Theta(n).$
\end{theorem}

\begin{proof} A 01--06 sorok végrehajtása $\Theta(n)$ időt igényel. A 07--11 sorok végrehajtása $O(n)$ ideig tart. 
Mivel $w$ szigorúan monoton csökken a program végrehajtása során, ezért a 12--24 sorok  $O(n)$ időt igényelnek, 
így az algoritmus futási ideje minden esetben $\Theta(n).$ 
\end{proof}    

Legyen $b = 3$ és $s = (13,10,5,5,4,1).$  Az ötödik és tizedik sorok feltételei nem teljesülnek és $r_1 = 0.$ Ha $i = 2,$ 
akkor $w_i = 5$ és teljesül a 20. sor feltétele, így $s$ \textit{nem} $(0,1,6)$\textit{-grafikus.}  

A következő példában $b$ maradjon $3,$ viszont $s$-et változtassuk meg: legyen $s' = (13,10,5,5,4,3).$ Az előző esethez képest 
annyi a változás, hogy $r_1 = 2$ az első maradék, majd $i = 2$ esetén $w_i = 2,$ nem teljesül a 20. sor feltétele és $r_2 = 0$. 
$i = 3$ esetén teljesül a 19. sor $H_{i-1} \geq H_n/2$ feltétele, ezért $s'$ $(0,1,6)$\textit{-grafikus.} 

A következő példában legyen $b = 1$ és $s = (4,3^3,1).$ A 05. és 10. sorok feltételei nem teljesülnek és $r_1 = 0.$ Ha $i = 2,$ 
akkor $w_i = 4$ és nem teljesül a 20. sor feltétele, az $i = 3$ esetben pedig a 19. sorban teljesül a $H_{i-1} \geq H_n/2$ 
feltétel, azaz $s$ $(0,1,5)$\textit{grafikus}.  

A \ref{tab-ChHHL02n}. táblázat a ChHHL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok számát 
tartalmazza $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 6   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	  	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	 &	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChHHL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok száma   
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHL02n}}
\end{table}

A \ref{tab-ChHHL02g}. táblázat a ChHHL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok számát 
tartalmazza $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 6   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	  	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	 &	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChHHL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok száma   
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHL02g}}
\end{table}

A következő \ref{tab-ChHHL02hat} táblázat a ChHHL algoritmus hatékonyságát jellemzi 
$a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGL02g}

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrr||} \hline \hline
n/\mbox{jellemző}&    X   &   Y   &    Z      &    X'     &  Y' &    Z'  \\ \hline
  1             &         & 	     &         &	 	  &			&					\\
  2             &         & 	     &	       &     	  &			&					\\
  3             & 	     &	  	   &           &		  &		    &		       		\\
  4             & 	     &	       &	  	  &			  &	        &			\\
  5             & 	     &		   &	 	  &		 		&		&		 \\
  6             &    	 &	       &		  &		 		&       &       		\\
  7             & 	     &	 	   &		  &		 		&	    &       	\\
  8             & 	     &	  	   &		  &		 		&		&       	\\
  9             &   	 &		   &		  &		 		&	    &       		\\
 10             &   	 &		   &		  &		 		&		&	    			\\
 11             & 	     &	 	   &		  &				&		&	    	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChHHl hatékonysági jellemzői $a = 0,$ $b = 2$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHL02hat}}
\end{table}


A \ref{tab-ChHHL25n}. táblázat a ChEGL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok számát 
tartalmazza $a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén. 

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 4   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	 	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	&	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChHHL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok száma 
$a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHL25n}}
\end{table}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{$(a,b,n)$-gráfok \label{sec-abn}}
Egy $(a,b,n)$-gráfban minden csúcspár elemei legalább $a$ éllel össze vannak kötve. Ezért ha minden csúcspár esetén eltávolítunk 
$a$ élet, egy $(0,b-a,n)$\textit{-gráfot} kapunk. Ezért a Chungphaisan tételnek közvetlen következménye az alábbi állítás. 

\begin{corollary} Legyen $n \geq 2$.\label{cor-abn} Az $s = (s_1, \ldots, s_n)$ $(a,b,n)$-szabályos sorozat akkor és csak akkor 
$(0,b,n)$-grafikus, ha az $s' = (s_1 - a(n - 1), \ldots, s_n - a(n - 1))$ sorozat $(0, b-a, n)$-grafikus.
\end{corollary} 

A \ref{cor-abn}. következmény szerint a következő három táblázat adatai megegyeznek a $(0,3,n)$-szabályos sorozatokra 
vonatkozó hasonló adatokkal.

A \ref{tab-ChEGl25n}. táblázat a ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok számát 
tartalmazza $a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén. 

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 4   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	 	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	&	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nemgrafikus sorozatok száma 
$a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl25n}}
\end{table}

A \ref{tab-ChEGl25g}. táblázat a CL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok számát 
tartalmazza $a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrrrrrr||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10\\ \hline
  1   &  0   & 	     &         &	 &	  &		&		&		&		&		\\
  2   &  0   & 	 4   &	       &     &	  &		&		&		&		&			\\
  3   &      & 	     &	 	   &     & 	  &		&		&		&       &		\\
  4   &      & 	     &	       &	&	  &		&		&	    &		&	\\
  5   &      & 	     &		   &	 &	  &		&		&		&		& \\
  6   &      &    	 &	       &	&	  &		&		&       &       &		\\
  7   &      & 	     &	 	   &	&	  &		&		&	    &       &	\\
  8   &      & 	     &	  	   &	&	  &		&		&		&       &	\\
  9   &      &   	 &		   &	&	  &		&		&	    &       &		\\
 10   &      &   	 &		   &	&	  &		&		&		&	    &			\\
 11   &      & 	     &	 	   &	&	  &		&		&		&	    &	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt grafikus sorozatok száma 
$a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl25g}}
\end{table}

A következő \ref{tab-ChEGl25hat} táblázat a ChEGl algoritmus hatékonyságát jellemzi 
$a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGL25hat}

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||rrrrrr||} \hline \hline
 n/\mbox{jellemző}&    X &   Y   &    Z   &    X'     &  Y' &    Z'  \\ \hline
  1            &         & 	     &         &	           &	   &			\\
  2            &         & 	     &	       &               &	  &						\\
  3            &         & 	     &	  	   &               & 	  &		      		\\
  4            &         & 	     &	       &	           &	  &					\\
  5            &         & 	     &		   &	           &	  &				 \\
  6            &         &    	 &	       &	           &	  &		       		\\
  7            &         & 	     &	 	   &	           &	  &		       	\\
  8            &         & 	     &	  	   &	           &	  &		      	\\
  9            &         &   	 &		   &	           &	  &		       		\\
 10            &         &   	 &		   &	           &	  &		    			\\
 11            &         & 	     &	 	   &	           &	  &		    	 \\
\hline \hline
\end{array} $
\end{scriptsize}
\caption{ChEGl hatékonysági jellemzői $a = 2,$ $b = 5$ és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl25hat}}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Grafikus sorozatok száma\label{sec-grafikusszam}}
A \ref{tab-sorozatszam}. ábra $1$-től $29$ 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. 

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

Az alábbi \textsc{Erdős-Gallai-leszámláló} (EGE) algoritmus a lineáris legrosszabb eset mellett azt is igyekszik 
kihasználni, hogy ha lexikografikus sorrendben ellenőrizzük a szóba jö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 várható 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ó $(0,1,n)$-grafikus sorozatok között ugyanis a \ref{lemma-nullaatl}. lemma szerint pontosan 
$G(n - 1)$ grafikus 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 EGE program azt is kihasználja, hogy a szomszédos sorozatok ellenőrző 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ő -- $q = (n - 1)^n$ -- sorozatra a $C$ lista üres (azaz egyáltalán nem kell ellenőrzést végeznünk), 
a súlypontok listája pedig kezdetben $w = \left ((n - 1)^{n - 1} \right ).$

Az \textsc{Erdős-Gallai-Gyorsan} algoritmus előállítja és megvizsgálja az $n$-páros, nullamentes sorozatokat,  
és kimenetként megadja a $G(n)$ értéket. Az algoritmus kihasználja, hogy a páros sorozatok lexikografikusan 
csökkenő sorozatában szomszédos sorozatok több lényeges paramétere hasonló, ezért ezek a paraméterek a vizsgált $s'$ 
sorozatot megelőző $s$ 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(s)$ listával, és legfeljebb a végén változik egy vagy két elem.  

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


\textit{Kimenet}. $G$: a $(0,1,n)$-grafikus sorozatok száma. 

\textit{Munkaváltozók.} $i$ és $j$: ciklusváltozók; \\
$s = (s_1,\ldots,s_n)$: $b_i$ az éppen tesztelt páros, nullamentes sorozat $i$-edik eleme; \\
$s_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(s) = 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; \\
$w = w_1,\ldots,w_{n-1}$: $w_i$ a legnagyobb indexű olyan $s_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ó.


\bigskip
\noindent \textsc{Erdős-Gallai-leszámláló}$(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}69                  \> \textbf{go to} 07  \\
\end{tabbing}




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.


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. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Nyitott problémák \label{sec-open}}
Az alábbiakban néhány nyitott problémát, további feladatot mutatunk be. 

\subsection{Különböző gráfosztályok foksorozatainak leszámlálása}
Explicite formulas are not known for the numbers of degree sequences of $(a,b,n)$-graphs. 

Kleitman \cite{KleitmanW1981} gave asymptotic bounds for the number of $(1,1,n)$-digraphs, while Burns \cite{Burns2007}  
proved bounds for the number of $(0,1,n)$-undigraphs. Narayana and Bent \cite{NarayanaB1964} gave recursive formulas  
to compute the number of degree-sequences of $(0,1,n)$-digraphs. P\'ecsy and Sz\H ucs \cite{PecsySz2000} used the 
formulas of Narayana and Bent to compute quickly the concrete values of the function $D(0,1,n)$. Using a quick parallel program 
in 2011 Iványi et al. \cite{IvanyiLMS2011} computed the values $G(n)$ until $n = 29.$ 


\subsection{Konkrét problémák bonyolultsága}

\cite{Frank2011}

\subsection{Optimalizálás}
\cite{Ivanyi2010}

\subsection{Közelítő problémák} 

\subsection{Befokok és kifokok egyidejű vizsgálata}

\subsection{További gráfosztályok potenciális foksorozatainak tesztelése}
Páros gráfok, többrészes gráfok, hipergráfok

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Összefoglalás \label{sec-summary}}
\textbf{?????????????????????}


 
\bigskip
\noindent \small \textbf{Köszönetnyilvánítás.} A szerzők köszönik ??? A kutatás az Európai Unió támogatásával, az 
Európai Szociális Alap társfinanszírozásával valósul meg (a támogatás száma TÁMOP 4.2.1/B-09/1/KMR-2010-0003). 


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

\begin{footnotesize}

\bibitem{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{Chungphaisan1974} \textsc{Chungphaisan, V.} \textit{Conditions for sequences to be $r$-graphical.}   
Discrete Math. \textbf{7,} (1974) 31--39. 
 
\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{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{Ivanyi2012} \textsc{Iványi, A.:} \textit{Test of degree sequences of multigraphs.}  
Annales Univ. Budapest., Computatorica (benyújtva).

\bibitem{IvanyiLMS2011Acta} \textsc{Iványi, A., Lucz, L., Móri F. T., Sótér, P.:} \textit{On the Erdős-Gallai and 
Havel-Hakimi algorithms.} Acta Univ. Sapientiae, Inform. \textbf{3(2),} (2011) 230--268.
 
\bibitem{IvanyiP2011} \textsc{Iványi, A., Pirzada, S.:} \textit{Comparison based ranking.} In (ed. A. Iványi): 
Algorithms of Informatics, Vol. 3. AnTonCom, Budapest 2011, 1262--1311.  

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

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

\bibitem{KimTMESz2009} \textsc{Kim, H., Toroczkai, Z., Miklós, I., Erdős, P. L., Székely, L. A.:}  
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{LuczS2011} \textsc{Lucz, L., Sótér, P.:}  \textit{Foksorozatokat ellenőrző algoritmusok.} 
TDK dolgozat. ELTE IK, Budapest, 2011.
 
\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{NarayanaB1964} \textsc{Narayana, T. V.,  Bent, D. H.:} Computation of the number of score sequences in 
round-robin tournaments. Canad. Math. Bull. \textbf{7(1),} (1964) 133--136.

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

\bibitem{Ozkan2011} \textsc{\"Ozkan, S.}: \textit{Generalization of the Erd\H os-Gallai inequality.} 
Ars Combin. \textbf{98,} (2011) 295--302. 

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

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

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

\bibitem{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 \\
Eötvös Loránd Tudományegyetem \\
Informatikai Kar \\
1117 Budapest, Pázmány Péter sétány 1/C \\ \\
LUCZ LORÁND \\
lorand.lucz@gmail.com \\
Eötvös Loránd Tudományegyetem \\
Informatikai Kar \\
1117 Budapest, Pázmány Péter sétány 1/C \\ \\

\vspace{4mm}
Budapest, 2012. január 5b.

\begin{center}
\vspace{6mm}

DEGREE SEQUENCES OF MULTIGRAPHS

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

\noindent Let $a,$ $b$ and $n$ integers, $0 \leq a < b$ and $n \geq 1$. $(a,b,n)$-graphs are loopless multigraphs in which 
any two vertices are connected with an least $a$ and at most $b$ edges. Havel in 1955 \cite{Havel1955}, Erdős and Gallai in 1960 
\cite{ErdosG1960}, Hakimi in 1962 \cite{Hakimi1962}, 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 $(0,1,n)$-graph.  
Chungphaisan in 1974 \cite{Chungphaisan1974} extended Havel-Hakimi and Erdős-Gallai theorem for $(0,b,n)$-graphs. All the mentioned 
algorithms require at least quadratic time in worst case. We extend Erdős-Gallai-Chungphaisan theorem for $(a,b,n)$-graphs and 
propose a linear time algorithm, based on our theorem. We also propose a linear time version of the testing part of Havel-Hakimi 
algorithm and extend it for $(0,2,n)$-graphs.
\end{small}

\end{document}

