\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 és LUCZ LORÁND (2012. február 7.)
\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}, Tripathi, 
Venugopalan és West 2010-ben \cite{TripathiVW2010}, Özkan \cite{Ozkan2011} 2011-ben 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 és annak gyorsított változatát. A Chungphaisan-Havel-Hakimi algoritmust pedig úgy javítjuk és 
gyorsítjuk, hogy $b = 1$ mellett $b = 2$ esetén is lineáris futási idejű.    
\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 et al. \cite{KimTMESz2009} és Newman és Barabási \cite{NewmanB2006} hálózati,   
Bozóki, Fülöp, Kéri, Poesz és Rónyai gazdasági \cite{BozokiFP2011,BozokiFR2010,Keri2011}, 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 
-- irányított vagy irányítatlan -- gráfok, 
melyek csúcshalmaza $V = \{v_1,\ldots,v_n \}$ és 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 a \textit{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 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 irányítatlan $(a,b,n)$-gráf, amelynek foksorozata $s$. Ennek 
megfelelően -- ha mást nem mondunk -- a gráf kifejezés irányítatlan gráfot jelent. 

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,BergerM2010,BrualdiK2009,
delGenioKTB2010,HellK2009,KayibiKPI2011,Meierling2009,Ozkan2011,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 foksorozata $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 (azaz eltérünk a teljes gráfok szokásos 
definíciójától). 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 mindig ellentétesen, míg 3 él esetén azok mindig 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{BergerM2010,delGenioKTB2010,KayibiKPI2011,MiklosES2011}) van, hogy véletlen mintavétellel 
becsüljük ezeket a számokat.

Melléktermékként bővítettük az On-Line Encyclopedia of Integer Sequences \cite{Sloane2011} adatbázist. 
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 negyedikben általános leszámlálási eredményeket, az ötödikben  
pedig új tesztelő algoritmusokat ismertetünk. A hatodik részben a közelítő algoritmusok hatékonyságát és futási idejét,  
míg a hetedikben a pontos algoritmusok futási idejét elemezzük. A nyolcadik rész témája a $(0,b,n)$-gráfok potenciális 
foksorozatainak tesztelése, míg a kilencedikben az $(a,b,n)$-gráfoké a főszerep. A tizedik részben a $(0,1,n)$-grafikus sorozatok 
párhuzamos leszámlálása a téma.  

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

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

\begin{theorem} \emph{(Hakimi \cite{Hakimi1962}, Havel \cite{Havel1955})} Ha\label{tetel-HH} $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{Hakimi1962,Havel1955}.
\end{proof}


A továbbiakban sorozatok ismétlődő elemeinek tömör jelölésére használjuk az $s = (c^d)$ típusú jelölést, 
ami azt jelzi, hogy a sorozat $d$ darab $c$-t tartalmaz.

Ha ezen tétel alapján írunk egy rekurzív algoritmust, akkor annak futási ideje 
legjobb esetben -- például az $(n-1,0^{n - 1})$ bemenetre -- $\Theta(1)$, 
legrosszabb esetben pedig -- például a \textit{homogén} $((n-1)^n)$ 
bemenetre -- $\Theta(n^2)$. Ez ugyanis grafikus sorozat, ezért minden elemét ellenőrizni kell. 
Másrészt az elemek összege négyzetes, és az algoritmus az 
elemeket egyesével csökkenti nullára. É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). Az alábbi algoritmus csak a bemenet tesztelését végzi el.

A következő \textsc{Havel-Hakimi} algoritmus az \ref{tetel-HH}. tételen alapul. A cikk programjaiban a \cite{CormenLRS2009} 
tankönyvben leírt pszeudokód konvenciókat követjük. 

\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ó (ha $s$ $(0,1,n)$-grafikus, akkor $L = 1,$ egyébként $L = 0).$  

\textit{Munkaváltozók.} $i, \ j$: ciklus változók.

\bigskip
\noindent \textsc{Havel-Hakimi}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= x\=x\=x\=x\=x\=x\=x\=x \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$  \` \textbf{//} 01--06. sor: $s$ elemeinek tesztelése\\
\hspace{-7mm}02              \> \textbf{if} \= $s_{s_i + i} == 0$  \` \textbf{//} 02--03. sor: $s$ nem grafikus  \\
\hspace{-7mm}03              \>             \> \textbf{return} $0$ \\
\hspace{-7mm}04              \> \textbf{for} \= $j = i + 1$ \textbf{to} $s_i + i$ \\
\hspace{-7mm}05              \>               \> $s_j = s_j - 1$ \\ 
\hspace{-7mm}06              \> $(s_{i+1},\ldots,s_n)$ \= rendezése nemnövekvő sorrendbe \\
\hspace{-7mm}07  \textbf{return} $1$ \` \textbf{//} 07. sor: $s$ grafikus
\end{tabbing}

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{becsült kapacitásának} nevezzük.  Ha egy $s$ sorozatra $H_n$ páros, akkor a sorozatot $n$\textit{-párosnak,} 
egyébként $n$\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 tétel alapgondolata az, hogy az első i csúcs fokait egyrészt ezen csúcsok közötti élekkel -- ezekből legfeljebb 
$i(i - 1 )$ van -- másrészt a nagyobb indexű csúcsok fokaival lehet lekötni. A nagyobb indexű csúcsokra pedig az 
jellemző, hogy egyrészt legfeljebb $i$ csúcs egy-egy fokát tudják lekötni,másrészt legfeljebb annyi fokot, mint a saját fokszámuk. A 
tétel szépségét az adja, hogy ezeknek a természetes szükséges feltételeknek az elégségességét is tartalmazza.

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:$ $s$ grafikusságát jelző logikai változó.  

\textit{Munkaváltozók.} $C$: aktuális $C_i;$ \\
$i, \ k$: ciklusváltozók.

\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--05. sor: paritás ellenőrzése \\
\hspace{-7mm}05             \> \textbf{return} $0$\\
\hspace{-7mm}06 \textbf{for} \= $i = 1$ \textbf{to} $n-1$ \` \textbf{//} 06--11. sor: $s$ tesztelése\\
\hspace{-7mm}07              \> $C = 0$                   \` \textbf{//} 07. sor: $t$ kezdeti értékének beállítása\\
\hspace{-7mm}08 \>    \textbf{for} \= $k = i + 1$ \textbf{to} $n$ \` \textbf{//} 08--09. sor: $C$ frissítése \\
\hspace{-7mm}09 \>                 \> $C = C + \min(i, s_k)$\\
\hspace{-7mm}10 \>    \textbf{if} \= $H_i - i(i - 1) > C$   \` \textbf{//} 10. sor: szükséges feltétel ellenőrzése\\
\hspace{-7mm}11 \>                \> \textbf{return} $0$   \` \textbf{//} 11. sor: $s$ nemgrafikus \\
\hspace{-7mm}12 \textbf{return} $1$   \` \textbf{//} 12. sor: $s$ grafikus  \\
\end{tabbing} 

EG memóriaigénye $\Theta(n).$ Bár ez a program 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 $\Theta(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ázathoz a $(0,1,n)$-szabályos 
sorozatok számát a majd a \ref{sec-leszam} szakaszban szereplő \eqref{eq-Rn} képlet alapján, 
míg a $(0,1,n)$-páros sorozatok számát 
az ugyancsak a \ref{sec-leszam} szakaszban következő \ref{lemma-En}. lemma alapján számítottuk. 
A táblázat harmadik oszlopa a 
két számosság hányadosának gyors konvergenciáját szemlélteti $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$ az $s$ 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_1 = 0$ vagy az $(s_1, \ldots, s_p)$ sorozat $(0,1,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 Erdős-Gallai (EGn), illetve nullamentes Havel-Hakimi (HHn)  
algoritmusnak nevezzük.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Rövidített Erdős-Gallai algoritmus  (EGr) \label{sec-EGr}}
$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 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,s_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 az $s = (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 $g _j = e_1 + \cdots + e_j \ (j = 1, \ \ldots, q).$   

Az $s_i$ elemet az $s$ 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 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.

Tripathi és Vijai 2003-ban 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.

\begin{theorem} \emph{(Tripathi, Vijay \cite{TripathiV2003})} A\label{tetel-EGJ} $(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-TVparos}
\end{equation}
és
\begin{equation}
H_{g_i} - g_i(g_i - 1) \leq \sum _{k=g _i + 1}^n \min(g_i,s_k) \quad (i = 1,\ldots,q).\label{eq-TVbinom}
\end{equation}
\end{theorem}

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

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)$: $(0,1,n)$-szabályos sorozat.

\textit{Kimenet}. $L$: $s$ grafikusságát jelző logikai változó.
 
\textit{Munkaváltozó.} $i, \ j$: ciklusváltozók; \\
$H = (H_1,\ldots,H_n)$: $H_i$ $s$ első $i$ elemének az összege; \\
$p$: $s$ pozitív elemeinek a száma; \\
$s_{p + 1}$: segédváltozó annak eldöntéséhez, hogy $s_p$ ugró elem-e.  

\bigskip
\noindent \textsc{Erdős-Gallai-ugró}$(n,s,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $p = n$                                           \` \textbf{//} 01--03. sor: nullamentesítés \\
\hspace{-7mm}02 \textbf{while} \= $s_p = 0$ \\
\hspace{-7mm}03                \> $p = p -1$  \\
\hspace{-7mm}04 $H_1 = s_1$                                 \` \textbf{//} 04--08. sor: paritás ellenőrzése \\
\hspace{-7mm}05 \textbf{for} \= $i = 2$ \textbf{to} $p$ \\
\hspace{-7mm}06              \> $H_i = H_{i-1} + s_i$ \\
\hspace{-7mm}07 \textbf{if} \= $H_p$ páratlan \\
\hspace{-7mm}08             \>  \textbf{return} $0$  \\
\hspace{-7mm}09 $s_{p + 1} = 0$                        \` \textbf{//} 09--19. sor: fej igényének ellenőrzése \\
\hspace{-7mm}10 $i = 1$ \\
\hspace{-7mm}11 \textbf{while} \= $i \leq p$ és $i(i - 1) < H_i$\\
\hspace{-7mm}12                \> \textbf{while} \= $s_i == s_{i+1}$ \\
\hspace{-7mm}13                \>                \> $i = i +1$ \\ 
\hspace{-7mm}14                \> $E = 0$ \\
\hspace{-7mm}15                \> \textbf{for} \= $j = i + 1$ \textbf{to} $p$ \\
\hspace{-7mm}16                \>              \> $E = E + \min(j,s_j)$ \\
\hspace{-7mm}17                \> \textbf{if} \= $H_i > i(i - 1) + E$ \\  
\hspace{-7mm}18                \>             \> \textbf{return} $0$ \\
\hspace{-7mm}19                \> $i = i + 1$ \\ 
\hspace{-7mm}21 \textbf{return} $1$    \` \textbf{//} 20. sor: $s$ grafikus
\end{tabbing}

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

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

A \ref{tab-EGumenetek}.  táblázat azt mutatja, hogy $n = 3, \ \ldots, \ 15$ csúcs esetén EGu hány menet alatt tudja 
kizárni a nem $(0,1,n)$-grafikus sorozatokat a $(0,1,n)$-szabályos sorozatok tesztelése során.  $f_i(n) = f_i$ 
azoknak az $n$ hosszúságú nem $(0,1,n)$-grafikus sorozatoknak a száma, amelyek pontosan $i$ tesztelési menetet igényeltek. 
A táblázat minden sorára jellemző, hogy a maximális menetszám körülbelül $\frac{n}{2}.$ 

\begin{table}[!t]
\begin{scriptsize}
\begin{center}
\begin{tabular}{||r|r|r|r|r|r|r|r|r||}  \hline \hline
$n/i$    &$R(n)-G(n)$ & $f_1$     & $f_2$     &  $f_3$&   $f_4$& $f_5$   & $f_6$ & $f_7$ \\ \hline \hline
3	&	6	&	6	&		&		&		&		&		&		\\ \hline
4	&	24	&	24	&		&		&		&		&		&		\\ \hline
5	&	95	&	91	&	4	&		&		&		&		&		\\ \hline
6	&	360	&	338	&	22	&		&		&		&		&		\\ \hline
7	&	1 374	&	1 262	&	102	&	10	&		&		&		&		\\ \hline
8	&	5 222	&	4 729	&	409	&	84	&		&		&		&		\\ \hline
9	&	19 949	&	17 841	&	1 587	&	487	&	34	&		&		&		\\ \hline
10	&	76 362	&	67 645	&	6 025	&	2 294	&	398	&		&		&		\\ \hline
11	&	293 368	&	257 779	&	22 802	&	9 820	&	2 825	&	142	&		&		\\ \hline
12	&	1 129 961	&	986 274	&	86 292	&	39 745	&	15 554	&	2 096	&		&		\\ \hline
13	&	4 363 985	&	3 787 213	&	327 644	&	156 295	&	74 542	&	17 632	&	659	&		\\ \hline
14	&	16 891 448	&	14 586 597	&	1 248 368	&	605 592	&	327 404	&	111 872	&	11 615	&		\\ \hline
15	&	65 516 140	&	56 330 831	&	4 774 119	&	2 331 442	&	1 363 561	&	599 615	&	113 316	&	3 256	\\ \hline \hline
\end{tabular}
\caption{A $(0,1,n)$-szabályos nem $(0,1,n)$-grafikus sorozatok eloszlása $n = 3, \ \ldots, \ 15$ csúcsra aszerint, hogy 
az EGu algoritmus hány menet alatt tudja őket kizárni. \label{tab-EGumenetek}} 
\end{center} 
\end{scriptsize}
\end{table}


A \ref{tab-EGuhat}. táblázat tartalmazza a $(0,1,n)$-szabályos, -grafikus és -nemgrafikus sorozatok számát, valamint  
az EGu algoritmus számára a nemgrafikus, grafikus és összes sorozat kiszűréséhez szükséges menetek 
átlagos számát $n = 3, \ldots, 15$ csúcs esetén. A táblázatban szereplő $X', \ Y'$ és $Z'$ hatékonysági jellemzők definícióját 
a \eqref{eq-Xp}, \eqref{eq-Yp} and \eqref{eq-Zp} képletek tartalmazzák. Figyelemre méltó, hogy az utolsó 3 
oszlopban az együtthatók monoton csökkennek.

\begin{table}[!t]
\begin{scriptsize}
\begin{center}
\begin{tabular}{||r|r|r|c|c|c||}  \hline \hline
$n$ & $R(n)$    &$G(n)$    &  $X'$       &  $Y'$    &  $Z'$     \\  \hline \hline		  
3	&	10	    &	4	   &0,3333333333 &	0,5833333333	&	0,4333333333	\\ \hline
4	&	35	    &	11	   &0,2500000000 &	0,5909090909	&	0,3571428571	\\ \hline
5	&	126	    &	31	   &0,2084210526 &	0,6064516129	&	0,3063492063	\\ \hline
6	&	462	    &	102	   &0,1768518519 &	0,6192810458	&	0,2745310245	\\ \hline
7	&	1 716	&	342	   &0,1555416927	&	0,6219715957	&	0,2485014985	\\ \hline
8	&	6 435	&	1 213   &	0,1388117579	&	0,6267518549	&	0,2307886558	\\ \hline
9	&	24 310	&	4 361   &	0,1259433778	&	0,6312007949	&	0,2165821107	\\ \hline
10	&	92 378	&	16 016	&	0,1154618789	&	0,6336476024	&	0,2053021282	\\ \hline
11	&	352 716	&	59 348	&	0,1068633005	&	0,6357110908	&	0,1958472384	\\ \hline
12	&1 352 078	&	222 117	&	0,0996191461	&	0,6373495350	&	0,1879565503	\\ \hline
13	&5 200 300	&	836 315	&	0,0934514246	&	0,6386612700	&	0,1811323607	\\ \hline
14	&20 058 300	&3 166 852	&	0,0881205642	&	0,6397881871	&	0,1752191576	\\ \hline
15	&77 558 760	& 120 426 20&	0,0834688999	&	0,6407780422	&	0,1700028030	\\ \hline \hline
\end{tabular}
\caption{A $(0,1,n)$-szabályos és -grafikus sorozatok száma, valamint  az \textsc{Erdős-Gallai-ugró} 
algoritmus által az $n = 3, \ldots, 15$ hosszú sorozatok vizsgálata során végzett tesztek átlagos száma.\label{tab-EGuhat}}
\end{center} 
\end{scriptsize}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lineáris Erdős-Gallai algoritmus (EGl)\label{subsec-EGl}}
A következő \textsc{Erdős-Gallai-Lineáris} 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,\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} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} 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{ ha } 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 a \eqref{eq-EGl} egyenlőtlenségbe (\ref{eq-EGlk}) alapján behelyettesítjük $k$-t, akkor az 
$i \leq w_i$ esetben a (\ref{eq-EGlsmalli}), az $i > w_i$ esetben pedig a \eqref{eq-EGllargei} egyenlőtlenséget 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$ az $s_i$-hez tartozó súlypont; \\
$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$ páratlan                     \` \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 - 1$      \` \textbf{//} 08--16. 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{//}  13--14. sor: nemgrafikus $s$ elutasítása \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$   \\
\hspace{-7mm}15 $L = 1$                         \` \textbf{//} 15--16. sor: $s$ grafikus \\
\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 \emph{EGl} algoritmus  
 $\Theta(n)$ idő alatt dönti el, hogy $(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}} 
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ó pontjának} 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. 

\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_{g_i} - g_i(g_i - 1) \leq \sum _{k=c_i + 1}^n \min(g_i,s_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. 

A következő tétel -- EGe és EGu előnyeit egyesítve -- a tesztelési idő további csökkentését teszi lehetővé.

\begin{theorem} A {\label{th-egl}} $(0,1,n)$-szabályos $s = (s_1, \ldots, s_n)$ sorozat akkor és csak akkor $(0,1,n)$-grafikus, 
ha igaz az, hogy 
\begin{equation} H_n \quad \mbox{páros}  
\end{equation}
és
\begin{equation} \label{eq-egltheorem}  H_{g_i} \leq
\begin{cases} 
H_n - H_{g_i} + g_i (g_i -1), & \textit{ha}\;\; w_i \leq g_i \\ 
H_n - H_{w_i} + g_i (w_i -1), & \textit{ha}\;\; w_i > g_i \quad  (i = 1,\ldots,q - 1).
\end{cases}
\end{equation}
\end{theorem}
\begin{proof}
A csak az ugró pontokban való tesztelés elégségességét Tripathi és Vijay \cite{TripathiV2003} már bebizonyították. 
A tételben megadott feltétel ezeket az ellenőrzéseket végzi el, kihasználva a sorozat elemeinek monoton csökkenését, azaz a
\begin{equation} 
\sum^{n}_{k=g_i + 1} \min (g_i, s_k)  
\end{equation}
összeget nem számolja újra minden esetben, pontosabban nem ebben a formában végzi el a számítást, hanem explicit módon.

A kifejezés értéke a (\ref{eq-eqlproof0}) formában adható meg, mégpedig azért, mert a sorozat monotonitása garantálja, hogy a 
$k \leq w_i$ esetén a $\min (i,s_k)$ kifejezés értéke $i,$ míg $k > w_i$ esetén $s_k.$ Ebből következik, hogy
\begin{equation} \sum^{n-1}_{k=g_i + 1} \min (g_i, s_k) = 
\begin{cases} 
H_n - H_{g_i},\;\; \mbox{ha} \;\; w_i \leq g_i \\
H_n - H_{w_i} + g_i  (w_i - g_i),\;\; \mbox{ha} \;\; w_i > g_i.
\end{cases} \label{eq-eqlproof0} 
\end{equation}
 
Az eddigiek alapján az eredeti feltételt átírhatjuk a következő alakba:
\begin{equation} H_{g_i} - g_i (g_i - 1 ) \leq 
\begin{cases} 
H_n - H_{g_i},\;\; \mbox{ha} \;\; w_i \leq g_i \\
H_n - H_{w_i} + g_i  (w_i - g_i),\;\; \mbox{ha} \;\; w_i > g_i.
\end{cases} \label{eq-eglproof1} \end{equation}
  
A (\ref{eq-eglproof1}) egyenlőtlenséget átrendezve megkapjuk a \eqref{eq-egltheorem} egyenlőtlenséget.  
\end{proof}

A most megadott tétel alapján megvalósított EGgy algoritmus és az eddigi legjobb (ugró Erdős-Gallai) algoritmus sorozatonkénti 
átlagos műveletszámait, valamint a sorozat egyetlen elemére jutó átlagos műveletszámot tartalmazza a \ref{tab-EGuegl}. táblázat.

\begin{table}
\centering
$\begin{array}{||c|rrrrrrrrrrrrrr||} \hline \hline
n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\
\hline
\mathrm{EGu} & 4 & 12 & 16 & 21 & 26 & 32 & 37 & 43 & 49 & 56 & 63 & 70 & 77 & 85 \\
\frac{\mathrm{EGu}}{n} & 2.0 & 4.0 &	4.0 & 4.2 & 4.3 & 4.6 & 4.6 & 4.8 & 4.9 & 5.1 & 5.3 & 5.4 & 5.5 & 5.7\\ \hline
\mathrm{EGgy} & 12 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29 & 31 & 33 & 35 & 37 & 39 \\
\frac{\mathrm{EGgy}}{n} & 6.0 & 5.0 & 4.3 & 3.8 & 3.5 & 3.3 & 3.1 & 3.0 & 2.9 & 2.8 & 2.8 & 2.7 & 2.6 & 2.6 \\ \hline \hline
\end{array}$
\caption{Az ugró és a gyors Erdős-Gallai algoritmusok egy sorozatra jutó átlagos műveletigénye.}\label{tab-EGuegl}
\end{table}

A táblázatból leolvasható, hogy az átlagos műveletszám a lineáris algoritmus esetében kevesebb, mint fele annyi, mint az 
ugró algoritmus esetébn és az $n$ érték növelésével minden lépésben ugyanannyival növekszik. Az utóbbi azért fontos, mert így 
az $n$ növelésével lépésről lépésre nagyobb az új algoritmussal elért gyorsulás a korábbiakhoz képest. Az utóbbi kijelentés 
azonban nem meglepő, ha figyelembe vesszük, hogy a korábbi ismert algoritmusok négyzetesek, míg az új algoritmus 
lineáris futási idejű. Jól látható, hogy a régi módszer esetén a sorozatok egy eleméhez tartozó átlagos műveletszám 
az $n$ érték növekedésével együtt nőtt, az új módszernél azonban ez a szám lépésről lépésre csökken.

A \ref{th-egl}. tétel feltételeit ellenőrzi a következő algoritmus.

\textit{Bemenet.} $n$: az $s$ sorozat hossza; \\
$s = (s_1, \ldots, s_n)$: az ellenőrizendő sorozat.

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

\bigskip
\noindent \textsc{Erdős-Gallai-gyors}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= x\=x\=x\=x\=x\=x\=x\=x \+ \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--04. sor: $H$ további értékeinek 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--07. 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}\\
\hspace{-7mm}07 $w = n$                                  \` \textbf{//} 07. sor: súlypont kezdeti értéke\\
\hspace{-7mm}08 \textbf{for} \= $i=1$ \textbf{to} $n-1$   \` \textbf{//} 08--26. sor: sorozat tesztelése\\
\hspace{-7mm}09              \> \textbf{if} \= $s_{i} == s_{i+1}$ \` \textbf{//} 09--11 sor: ugrópont tulajdonság ellenőrzése\\
\hspace{-7mm}10              \>             \>  \textbf{continue} \` \textbf{//} 10. sor: nem ugrópont átlépése\\
\hspace{-7mm}11              \> \textbf{while} \= $w > 1$ és $s_{w} \leq i$ \` \textbf{//} 11--12. sor: súlypont frissítése\\
\hspace{-7mm}12              \>                \>    $w = w - 1$  \\
\hspace{-7mm}13              \> \textbf{if} \= $w < i$    \` \textbf{//} 13--16. sor: súlypont az ugrópont előtt van\\
\hspace{-7mm}14              \>             \> \textbf{if} \= $H_{i}>H_{n}-H_{i}+i(i-1)$ \`  14--18. sor: tétel feltételének ellenőrzése\\
\hspace{-7mm}15              \>             \>             \> $L = 0$ \` \textbf{//} 15--16. sor: nemgrafikus sorozat elutasítása\\
\hspace{-7mm}16              \>             \>             \> \textbf{return}\\
\hspace{-7mm}17              \> \textbf{else} \= \textbf{if} \= $H_i>H_n-H_w+i(w-1)$ \` \textbf{//} 17--19. sor: súlypont az ugrópont után van\\
\hspace{-7mm}18              \>               \>             \> $L = 0$    \` \textbf{//} 18--19. sor: nemgrafikus sorozat elutasítása \\
\hspace{-7mm}19              \>               \>             \> \textbf{return}\\
\hspace{-7mm}20 $L = 1$ \`                                              \` \textbf{//} 20--21. sor: grafikus sorozat elfogadása\\
\hspace{-7mm}21 \textbf{return L}\\
\end{tabbing}

\begin{theorem}
A lineáris Erdős-Gallai ugró algoritmus műveletigénye lineáris.
\end{theorem}

\begin{proof}
A 01. sor időigénye $O(1)$, a 02--03. soré $\Theta (n)$, a 04--07. soré $O(1)$, a 08--20. soré $O(n)$, a 
21--22. soré pedig $O(1).$ Így az algoritmus teljes műveletigénye $\Theta (n).$ 
\end{proof}

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Paritásos Havel-Hakimi algoritmus  (HHp) \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 volt az $s_i$ elemhez tartozó $w_i$ súlypontnak \cite{IvanyiLMS2011Acta},  
amely $i > s_1$ 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 lineáris változatában fontos szereplő legyen. Az 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 
$(0,1,n)$-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} 

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

\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ó.} $i$: ciklusváltozó; \\
$r = (r_1,\ldots,r_n)$: $r_i$ az $s_i$-hez tartozó maradék; \\
$w = (w_1,\ldots,w_n)$: $w_i$ az $i$ indexhez tartozó súlypont; \\
$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 \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 \leq 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--21. 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 \leq i$ and $j > 0$       \\ 
\hspace{-7mm}16              \>                \> $w_i = w_i - 1$             \\ 
\hspace{-7mm}17              \>                \> $j = j - 1$ \\              
\hspace{-7mm}18              \> \textbf{if} \= $w_i \geq i$     \`  \textbf{//} 18--??. sor: $s$ grafikus?  \\ \\
\hspace{-7mm}19              \>             \> \textbf{if} \= $s_i > w_i + r_{i-1}$    \\
\hspace{-7mm}20              \>             \>             \> $L = 0$       \`  \textbf{//} 20--21. sor: $s$ nem grafikus \\
\hspace{-7mm}21              \>             \>             \> \textbf{return} $L$ \\
\hspace{-7mm}22              \>             \> $r_i = w_i - 1 + r_{i-1} - s_i$    \`  \textbf{//} 22. sor: $r_i$ frissítése  \\ 
\hspace{-7mm}23              \> \textbf{if} \= $w_i < i$      \\ 
\hspace{-7mm}24              \>             \> \textbf{if} \= $s_i > w_i + r_{i-1}$    \\
\hspace{-7mm}25              \>             \>             \> $L = 0$       \`  \textbf{//} 25--26. sor: $s$ nem grafikus \\
\hspace{-7mm}26              \>             \>             \> \textbf{return} $L$ \\
\hspace{-7mm}27              \>             \> $r_i = w_i + r_{i-1} - s_i$    \`  \textbf{//} 22. sor: $r_i$ frissítése  \\
\hspace{-7mm}28 $L = 1$                                            \` 28--29. sor: $s$ grafikus \\
\hspace{-7mm}29 \textbf{return} $L$ \\     
\end{tabbing}

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

\begin{proof} A 01--06. sorok időigénye $O(1),$ és például a $(0^n)$ bemenetre a program a 03. sorban megáll, ezért a 
legjobb futási idő $O(1).$ A 07--11. sorok időigénye $\Theta(n).$ Mivel a súlypontok számítása legfeljebb $n$ csökkentést 
igényel, a 12--29. sorok idő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--12. sorok szerint $r_1 = 0$. Ha $i = 2,$ akkor   
$w_i = 3$ és a 19. 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--12. sorokban azt kapjuk, hogy $w_1 = 7$ és $r_1 = 1.$ Ha $i = 2,$ 
akkor $w_i = 4$, a 19. sor feltétele nem teljesül és a 22. sor szerint $r_2 = 1.$  
Ha $i = 3,$ akkor $w_i = 3$ és nem teljesül a 24. sor feltétele. Ha $i = 4,$ akkor $w_i = 1$ és most sem teljesül a 24. sor 
feltétele. Ha $i = 5,$ akkor teljesül a 09. sor $s_j \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 24. 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ő 12 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 15. sor $s_i \leq 1$ feltétele, 
ezért $s$ $(0,1,7)$\textit{-grafikus.} \hfill $\square$ 

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-test01n}. táblázat a HHl által az $i$-edik $(i = 1, \ldots, 11)$ menetben kiszűrt nem $(0,1,n)$-grafikus sorozatok 
számát mutatja  $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{small}
$\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	&		&		&		&		&		&		&		&		&		&		\\ \hline 
2	&	1	&	0	&		&		&		&		&		&		&		&		&		\\ \hline 
3	&	6	&	0	&	0	&		&		&		&		&		&		&		&		\\ \hline 
4	&	22	&	2	&	0	&	0	&		&		&		&		&		&		&		\\ \hline 
5	&	85	&	8	&	2	&	0	&	0	&		&		&		&		&		&		\\ \hline 
6	&	311	&	35	&	12	&	2	&	0	&	0	&		&		&		&		&		\\ \hline 
7	&	1169	&	128	&	58	&	17	&	2	&	0	&	0	&		&		&		&		\\ \hline 
8	&	4369	&	488	&	239	&	100	&	24	&	2	&	0	&	0	&		&		&		\\ \hline 
9	&	16524	&	1805	&	942	&	471	&	173	&	32	&	2	&	0	&	0	&		&		\\ \hline 
10	&	62650	&	6800	&	3601	&	2021	&	956	&	289	&	43	&	2	&	0	&	0	&		\\ \hline 
11	&	239008	&	25571	&	13677	&	8147	&	4561	&	1877	&	470	&	55	&	2	&	0	&	0	\\ \hline \hline
\end{array} $
\end{small}
\caption{HHl $i$-edik $(i = 1,\ldots,11)$ menetében a $(0,1,n)$-szabályos sorozatok közül kiszűrt nemgrafikus sorozatok száma 
$n = 1, \ \ldots, \ 11$ csúcs  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 $(0,1,n)$-grafikus sorozatok számát 
tartalmazza $n = 1, \ \ldots, \ 11$ csúcs  esetén.

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

Legyen $N_i(a,b,n,\mathrm{A}),$ illetve $M_i(a,b,n,\mathrm{A})$ az A algoritmus által az $(a,b,n)$-szabályos 
vagy $(a,b,n)$-páros 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-1} n_i \quad   \emph{\mbox{és}} \quad  M = \sum _{i = 1}^{n-1} m_i, \label{eq-NM}
\end{equation} 
\begin{equation}
X(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} in_i}{N},  \label{eq-X}
\end{equation}
\begin{equation}
Y(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} im_i}{M},  \label{eq-Y}
\end{equation}
\begin{equation}
Z(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} i(m_i + n_i)}{N + M}, \label{eq-Z}
\end{equation}
\begin{equation}
X'(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} in_i}{N(n-1)},  \label{eq-Xp}
\end{equation}
\begin{equation}
Y'(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} im_i}{M(n-1)},   \label{eq-Yp}   
\end{equation}
\begin{equation}
Z'(a,b,n,\mathrm{A}) = \frac{\sum _{i=1}^{n-1} i(m_i + n_i)}{(N + M)(n-1)}.  \label{eq-Zp}
\end{equation}

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

\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.000000000	&	1.000000000	&	1.000000000	&	1.000000000	&	1.000000000	&	1.000000000	\\ \hline
3	&	1.000000000	&	1.750000000	&	1.300000000	&	0.500000000	&	0.875000000	&	0.650000000	\\ \hline
4	&	1.083333333	&	2.454545455	&	1.514285714	&	0.361111111	&	0.818181818	&	0.504761905	\\ \hline
5	&	1.126315789	&	3.032258065	&	1.595238095	&	0.281578947	&	0.758064516	&	0.398809524	\\ \hline
6	&	1.180555556	&	3.588235294	&	1.712121212	&	0.236111111	&	0.717647059	&	0.342424242	\\ \hline
7	&	1.220524017	&	4.111111111	&	1.796620047	&	0.203420670	&	0.685185185	&	0.299436674	\\ \hline
8	&	1.262734584	&	4.629843364	&	1.897435897	&	0.180390655	&	0.661406195	&	0.271062271	\\ \hline
9	&	1.299062610	&	5.140793396	&	1.988235294	&	0.162382826	&	0.642599175	&	0.248529412	\\ \hline
10	&	1.335323852	&	5.650162338	&	2.083407305	&	0.148369317	&	0.627795815	&	0.231489701	\\ \hline
11	&	1.368874588	&	6.157056683	&	2.174534186	&	0.136887459	&	0.615705668	&	0.217453419	\\ \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}

Az \ref{tab-HHl02hat}. táblázat 11. sorában található $X'(0,1,11) = 0.136887459$ és $Y'(0,1,11) = 0.615705668.$ Eszerint 11 
csúcs esetén a nemgrafikus sorozatok kiszűréséhez átlagosan a menetek 14 $\%$-ára, míg a grafikus sorozatok kiszűréséhez 
átlagosan $62$ $\%$-ára van szükség, ahonnan az következik, hogy az összes szűréshez átlagosan a menetek 22 $\%$-át kell 
végrehajtani. 

Érdemes megjegyezni, hogy Tripathi és Vijay ugrópontokról szóló tétele a HHl algoritmus gyorsítására is felhasználható.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Általános 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. 

Ha $l, \ m$ és $u$ egész számok, továbbá $l \geq u$ és $1 \geq m,$ akkor az $s = (s_1, \ldots, s_n)$  
$(l,u,m)$-korlátos sorozatok $B(l,u,m)$ száma
\begin{equation}
B(l,u,m) = (u - l + 1)^m.\label{eq-Blum}
\end{equation}

A \eqref{eq-Blum} képlet közvetlen adódik abból, hogy az $s$ sorozatnak mind az 
$m$ eleme $u - l  + 1$ lehetséges értéket vehet fel.

Az is közvetlenül belátható, hogy ha $l, \ 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}
R(l,u,m) = \binom{m + u - l}{m}.\label{eq-Rlum}    
\end{equation}

Legyen ugyanis az $s = (s_1,\ldots,s_m)$ $(l,u,m)$-szabályos sorozat esetén $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.

Ha $l = 0, \ u = n - 1$ és $m = n,$ akkor az 
\begin{equation}
R(0,n-0,n) = R(n) = \binom{2n - 1}{n} \label{eq-Rn}
\end{equation} 
alakot kapjuk. 

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}}\left (1 - \frac{1}{2n} \right) < R(n) < 
\frac{4^n}{\sqrt{4\pi n}}\left (1 - \frac{1}{8n+8} \right ).\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}

1987-ben Ascher \cite{Ascher1987} a következő képletet vezette le a $(0,1,n)$-páros sorozatok $E(n)$ számára).

\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{Ascher1987,SloaneP1995}.
\end{proof}

A \eqref{eq-Rn} képlet és a \ref{lemma-En}. lemma 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} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} 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} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} 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} Lásd \cite{IvanyiLMS2011Acta}.
\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 a $(0,1,n)$-szabályos sorozatok közül
\begin{equation}
R_z(n) = \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ó $(0,1,n)$-szabályos sorozatok halmaza kölcsönösen egyértelműen leképezhető az 
$(0,n - 1,n)$-szabályos sorozatok halmazára. Az utóbbi halmaz elemszáma pedig \eqref{eq-Rn} 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} = \frac{n}{2n - 1}R(n).
\end{equation}
\end{proof}

Egész számokból álló sorozat különböző elemeinek a számát az adott sorozat \textit{szivárványszámának} nevezzük. 
Legyen $q_n(s)$ valószínűségi változó, amely egy véletlen $(0,1,n)$-korlátos sorozat szivárványszámát jellemzi. 
$q_n(b)$ szivárványszámának várható értékét és szórását a következő állítás tartalmazza.

\begin{lemma}\label{lemma-boundedrain} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} Legyen $\sigma$ egy véletlen 
$(0,n-1,n)$-korlátos sorozat és $q_n(\sigma)$ a szivárványszáma. Ekkor $\sigma$ $E[q_n(\sigma)]$ várható értéke és $V[q_n(\sigma)]$ 
szórása a következő:  
\begin{align}
E[q_n(\sigma)]  & = n\left[1-\left(1-\frac{1}{n}\right)^n\right] =
n\left(1-\frac{1}{e}\right)+O(1), \label{exp_rain}\\
Var[q_n(\sigma)]& = n\left(1-\frac{1}{n}\right)^n
\left[1-\left(1-\frac{1}{n}\right)^n\right]\notag\\
& \hspace{1cm}+n(n-1)\left[\left(1-\frac{2}{n}\right)^n
-\left(1-\frac{1}{n}\right)^{2n}\right]\notag\\
& = \frac{n}{e}\left(1-\frac{2}{e}\right)+O(1). \label{var_rain}
\end{align}
\end{lemma}

A következő állítás a $k$ szivárványszámú $(0,n-1,n)$-szabályos sorozatok számát adja meg. 

\begin{lemma}\label{lemma-regrain} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} Ha $1 \leq k \leq n$ és $m \geq 1,$ 
akkor a $k$ szivárványszámú $(0,n-1,m)$-szabályos sorozatok $S(k,m,n)$ száma
\begin{equation}
S(k,m,n) = \dbinom{n}{k}\dbinom{m-1}{k},\ k=1,\dots,n.
\end{equation}
\end{lemma}

Eszerint a véletlen $\sigma$ $(0,n-1,m)$-szabályos sorozatok  $r_n(\sigma)$ szivárványszáma hipergeometriai eloszlású az  
$n+m-1,$ $n$ és $m$ paraméterekkel. Legyen $\rho _n(\sigma)$ egy véletlen $(0,1,n)$-szabályos sorozat és 
$E[r_n(\sigma)],$ illetve $V[r_n(\sigma)]$ $\sigma$ várható értéke, illetve szórása. Ekkor  
$\rho _n(\sigma)$ szivárványszámának várható értékét és szórását a következő állítás tartalmazza.

\begin{corollary} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})}  
Legyen\label{cor-regrain} $\rho$ egy véletlen $(0,1,n)$-szabályos sorozat. Ekkor $\rho$ $E[r_n(\rho)]$ 
várható értéke és $V[r_n(\rho)]$ szórása a következő:
\begin{align}
E[r_n(\rho)]&=\frac{n^2}{2n-1} = \frac{n}{2} + \frac{n}{4n - 2} = \frac{n}{2} + O(1),\label{eq-regrainexp}\\
V[r_n(b)]& = \frac{n^2(n-1)}{2(2n-1)^2} = \frac{n}{8} + \frac{n}{128n^2 - 128n + 32} = \frac{n}{8} + O(1).
\label{eq-regrainvar}
\end{align}
\end{corollary}

A pontos algoritmusokról szóló \ref{subsec-nullamentes}. részben beláttuk, hogy elég a $(0,1,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 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} \emph{(Iványi, Lucz, Móri, Sótér \cite{IvanyiLMS2011Acta})} 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} A $(0,1,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}
 
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}


Nézzük meg, mit várhatunk a HHl algoritmus első hat sorától. Az algoritmus lehetséges bemenetei a $(0,n-1,n)$-szabályos 
sorozatok. Ezek $R(n)$ száma a \eqref{eq-Rn} képlet szerint
\begin{equation}
R(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-Rlum} 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 sorozatokból a 
\begin{equation}
\sum _{i = 1}^{\infty} \frac{1}{4^i} = \frac{1}{3}
\end{equation}
összegnek megfelelő hányadot, 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.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 + 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,s,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} + s_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 = s_1$ \\
\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-fejfelez} $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 \left( \binom{h_i}{2},H_{h_i}) \right ),\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 \min \left (\binom{i - h_i}{2},H_i - H_{h_i}, \right ) .\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 telesüljön   
\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, \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),H_i)$ \\
\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$ vagy $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 $E_{\textsc{A}}(n)$-nel jelöljük és az A algoritmus $n$ hosszúságú sorozatokra vonatkozó 
\textit{hatékonyságának} nevezzük. 

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

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

2) \textsc{Binomiális-teszt} (Bt);

3) \textsc{Fejfelező-teszt} (Ft).
 

A \ref{tab-sorozatszam}. táblázat a binomiális és faroktesztelt sorozatok számát, továbbá a 
(0,1,n)-grafikus sorozatok számát és a grafikus sorozatok száma szomszédos $n$ helyeken felvett értékei hányadosát tartalmazza 
$n = 1, \ldots, 29$ csúcs esetén.

\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 binomiális $(B_(n))$, faroktesztelt $(F(n))$ $(0,1,-n)$-szabályos sorozatok száma, valamint a 
$(0,1,n)$-grafikus sorozatok száma $(G_n)$ és a grafikus sorozatok halmazának szomszédos $n$ helyeken felvett 
számosságai hányadosa $(G(n+1))/G(n)$ $n = 1, \ldots, 28$ csúcs esetén.\label{tab-sorozatszam}}
\end{center}
\end{small}
\end{table} 

A \ref{tab-kozrelativ}. 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.


\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{A nullamentes sorozatok száma, továbbá a binomiális/szabályos, fejtesztelt/szabályos és grafikus/szabályos 
számarányok.\label{tab-kozrelativ}}
\end{center}
\end{small} 
\end{table} 

A \ref{tab-testtime}. táblázat a \textsc{Binimiális-teszt} és a \textsc{Fejfelező-teszt} algoritmusok futási idejét adja meg 
másodpercben és műveletszámban $n =  1, \ldots, 20$ csúcsra.  

 
\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        \\ \hline
2          &         0          &         41        &         0          &         43        \\ \hline
3          &         0          &         180       &         0          &         200      \\ \hline
4          &         0          &         716       &         0          &         815      \\  \hline
5          &         0          &         2 918     &         0          &         3 321   \\  \hline
6          &         0          &         11 918    &         0          &         13 675 \\  \hline
7          &         0          &         48 952    &         0          &         56 299 \\   \hline
8          &         0          &         201 734   &         0          &         233 182           \\  \hline
9          &         0          &         831 374   &         0          &         964 121           \\  \hline
10         &         0          &         3 426 742 &         0          &         3 988 542        \\  \hline
11         &         0          &     14 107 824    &         0          &         16 469 036      \\  \hline
12         &         0          &   58 028 152      &         0          &         67 929 342      \\  \hline
13         &         0          &    238 379 872    &         0          &         279 722 127    \\ \hline
14         &         0          &    978 194 400    &         1          &         1 150 355 240 \\ \hline
15         &         2          &     4 009 507 932 &         3          &         4 724 364 716 \\  \hline
16         &         6          & 16 417 793 698    &         13         &         19 379 236 737          \\  \hline
17         &         26         & 67 160 771 570    &         51         &         79 402 358 497          \\  \hline
18         &        106         & 274 490 902 862   &         196        &         324 997 910 595        \\ \hline
19         &       423          & 1 120 923 466 932 &         798        &         1 328 948 863 507     \\ \hline
20         &      1 627         & 4 573 895 421 484 &         3 201      &         5 429 385 115 097     \\ \hline \hline
\end{tabular}
\caption{A \textsc{Binomiális-teszt} (Bt) és a  \textsc{Fejfelező-teszt} (Ht) futási ideje másodpercben és a műveletek 
számával megadva $n = 1, \ \ldots, \ 20$ csúcs esetén.\label{tab-testtime}}
\end{center} 
\end{footnotesize}
\end{table}

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

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

Ha $n = 4,$ akkor a szabályos sorozatok száma $R(4) = 35.$ Ezek közül 19 a páros, és a következő 11 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 $B(4) = F(4) = G(4) = 11.$ 

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

Az $R(6) = 462$ szabályos sorozat közül $E(6) = 236$ a páros, amelyek között $B(6) = 103$ 
binomiális sorozat van. \textsc{Binomiális-teszt} a 102 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 $F(6) = G(6) = 102.$


Az $R(7) = 1716$ szabályos sorozat között $E(6) = 868$ a páros, melyek közül $B(7) = 376$ a binomiális. 
A binomiális sorozatok között még 34 rossz van, melyek közül a \textsc{Pozitív-teszt} a 27 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 $F(7) = 343.$ A cikkben nem ismertetett \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 a \textsc{Farokfelező-teszt} 
a 7 hosszú bemenetek közük $T(7) = 342$ sorozatot fogad el, így $G(7) = 342.$

A \ref{fig-sorozatszam}. táblázatban minden sorban az első pontos értéket félkövéren írtuk. Eszerint $n \leq 4$ esetén 
$B(n) = G(n),$ azaz a \textsc{Binomiális-teszt} ugyanannyi 
sorozatot fogad el, mint a pontos algoritmusok. $n > 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 nemgrafikus, $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{tab-regevenratio}. táblázatban $R(n)$ értéke $n = 24$-ig az OEIS A001700 sorozata \cite{Sloane2011A001700}, 
$E(n)$ értéke $n = 23$-ig az EIS A005654 sorozata \cite{Sloane2011A005654}, a \ref{tab-sorozatszam}. táblázatban $G(n)$ értéke 
pedig $n = 23$-ig az EIC A0004251-es sorozata \cite{Sloane2011A004251}. A többi értéket mi határoztuk meg: 
$R(25),\ldots,R(40),$ $E(24),\ldots,E(40),$ valamint $B(n)$ és $F(n)$ értékek nem szerepelnek az EIS-ben. 

Ebben a cikkben első sorban a soros algoritmusokkal kapott eredményekről számolunk 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 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-precisetime}. ábra 
tartalmazza $n = 1, \ \ldots, 15$ csúcsra. A sorozatok előállításához szükséges műveleteket beszámítottuk. 
are included.

\begin{table}[!t]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||r|r|r|r|r|r||}  \hline \hline
$n$  &      HHr &  HHe   &   EG      &       EGu    &  EGl        \\ \hline 
 1	 &	    10	 &	15	    &   87	   &        -     &  -	\\ \hline
 2	 &	    40	 &	61	    &  119	   &        12    &  37	\\ \hline
 3	 &	   231	 &	236	    &  267	   &       116    & 148	\\ \hline
 4	 &	1 170	 &	1 052   &  946	   &       551    & 585	\\ \hline
 5	 &	5 969	 &	4 477   & 4 000	   &     2 677    & 2 339	\\ \hline
 6	 &	31 121	 &	20 153  & 18 206	   &    12 068    & 9 539	\\ \hline
 7	 &	157 345	 &	88 548  & 82 154	   &    54 184    & 38 984	\\ \hline
 8	 &	784 341	 &  393 361   & 372 363   &    238 813   & 160 126	\\ \hline
 9	 &3 628 914  & 1 726 484 &1 666 167  &  1 666 167   &  656 575	\\ \hline
10	 &17 345 700 &7 564 112  &7 418 447  & 4 552 276    & 2 692 240	\\ \hline
11	 &80 815 538 &32 895 244 &32 737 155 & 19 680 986   &  11 018 710	\\ \hline
12	&385 546 527 &142 460 352&143 621 072&84 608 529   &  45 049 862	\\ \hline
13	&1 740 003 588&613 739 913&626 050 861& 362 141 061&  183 917 288	\\ \hline
14	&8 066 861 973&	2 633 446 908&2 715 026 827&1 543 745 902 &750 029 671	\\ \hline
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{Az elvégzett műveletek száma $n$ függvényében a HHr, HHe, EG, EGu, és EGl algoritmusok esetén.\label{fig-precisetime}}
\end{center} 
\end{footnotesize}
\end{table}

A \ref{fig-precisetime}. ábra első két oszlopának összehasonlítása azt mutatja, hogy HHe lénygesen gyorsabb, mint HHr, 
különösen ha $n$ nő. A harmadik és negyedik oszlop összehasonlítása azt mutatja, hogy a futási idő lényegesen csökken, ha 
a csak az ugró pontokban kell az elemeket tesztelni. Végül a harmadik és ötödik oszlopok együtt a lineáris algoritmusnak a 
négyzetessel szembeni előnyét jelzik. 

A \ref{tab-EGl}. táblázat \textsc{Erd\H os-Gallai-Linear} futási idejét tartalmazza másodpercben és az elvégzett műveletek 
számával megadva, továbbá az egy páros sorozatra jutó amortizált műveletszámot. 

\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   
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.00000000712149  &         5.34132654018    \\
15   &38 781 096&      5      &3 055 289 271&0.00000000859525&         5.25219687963   \\
16   &150 273 315&    23      &12 434 367 770&0.00000000956590&        5.17156346504    \\
17   &583 407 990&    79      &50 561 399 261&0.00000000796537&        5.09797604337    \\
18   &2 268 795 980&  297     &205 439 740 365&0.00000000727258&        5.03056202928    \\ \hline \hline
\end{tabular}
\caption{Az \textsc{Erdős-Gallai-lineáris} 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}

A \ref{tab-EGl}. táblázat legérdekesebb adatai az utolsó oszlopban vannak. Azt mutatják, hogy a műveletek számát osztva a 
vizsgált sorozatok hosszával és számával monoton csökkenő sorozatot kapunk (lásd \cite{RuskeyCES1994}).

A \ref{tab-EGs1}. táblázat a $(0,1,n)$-grafikus sorozatok első elem szerinti eloszlását mutatja 
$n = 1, \ldots, 12$ csúcs esetén.  Ezek az adatok hasznosak az \textsc{Erdős-Gallai-leszámláló} algoritmus tervezéséhez 
(a feladat szeletekre osztásához).

\begin{table}[!ht]
\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 
$1$      &1      &     &     &     &     &     &     &     &     &    &      &           \\ \hline
$2$      &1      &   1 &     &     &     &     &     &     &     &     &     &          \\ \hline
$3$      &   1   &   1 &  2  &     &     &     &     &     &     &     &     &  \\ \hline
$4$      &   1   &   1 &  4  &  4  &     &     &     &     &     &     &     &   \\ \hline
$5$      &   1   &   2 &  7  &10   &  11 &     &     &     &     &     &     &    \\ \hline
$6$      &   1   &   3 &10   &  22 &  35 & 31  &     &     &     &     &     &    \\ \hline
$7$      &   1   &   3 &14   &  34 &  78 & 110 & 102 &     &     &     &     &    \\ \hline
$8$      &   1   &   4 & 18  &  54 & 138 & 267 & 389 & 342 &     &     &     &    \\ \hline
$9$      &   1   &   4 & 23  &  74 & 223 & 503 & 968 & 1352& 1213&     &     &     \\ \hline
$10$     &   1   &   5 & 28  & 104 & 333 & 866 & 1927& 3496& 4895&4361 &     &    \\ \hline
$11$     &   1   &   5 & 34  &134  &479  &1356 &3471 &7221 &12892&17793&16016&        \\ \hline 
$12$     &   1   &   6 & 40  &176  &661  &2049 &5591 &13270&27449&47757&65769&59348     \\ \hline \hline
\end{tabular}
\caption{A $(0,1,n)$-grafikus sorozatok eloszlása $s_1$ szerint, $n = 1, \ \ldots, \ 12$ csúcs esetén\label{tab-EGs1}}
\end{center} 
\end{scriptsize}
\end{table}

A \ref{tab-EGs1}. táblázatban azt látjuk, hogy  a gyakoriságok $(n = 6)$-tól nőnek $(n - 2)$-ig, és az utolsó pozitív érték 
kisebb, mint az utolsó előtti.  


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

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

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ó; \\ 
$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--16. 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              \>             \> $L = 0$ \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$    \` \textbf{//} 14. sor: $s$ nem grafikus \\
\hspace{-7mm}15 $L = 1$                         \` \textbf{//} 15--16. sor:  $s$ grafikus \\
\hspace{-7mm}16 \textbf{return} $L$
\end{tabbing}  
  
  
\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})} \emph{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 \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. A szabályos sorozatok 
számát a \eqref{eq-Rn} képlettel, az $(a,b,n)$-grafikus sorozatok számát pedig a \textsc{Chungphaisan-Erdős-Gallai-lineáris} 
algoritmussal határoztuk meg. Az utolsó oszlop elemeinek meghatározásánál hasznosítottuk a \ref{cor-Chungab}. következményt. 

\begin{table}[!ht]
\begin{centering}
\begin{small}
$\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,5,n)	\\ \hline 
1	&	1	    &	1	  &	1	       &	1      &	1	        &	1	\\  \hline 
2	&	3	    &	2	  &	6	       &	3      &	10	        &	4	\\  \hline 
3	&	10	    &	4	  &	35	       &	10     &	84	        &	23	\\  \hline 
4	&	35	    &	11	  &	210	       &	52     &	715	        &	189	\\  \hline 
5	&	126	    &	31	  &1 287	   &	283	   &	6 188	    &	1 582	\\  \hline 
6	&	462	    &	102	  &8 008	   &	1 706  &	54 264	    &	13 583	\\  \hline 
7	&	1 716	&342	  &	50 388	   &10 436	   &	480 700	    &	122 345	\\  \hline 
8	&	6 435	&1 213	  &	319 770    &65 370	   &	4 292 145	&	1 092 573	\\  \hline 
9	&	24 310	&4 361	  &	2 042 975  &413 111	   &	38 567 100	&	9 816 598	\\   \hline 
10	&	92 378	&16 016	  &	13 123 110 &2 633 537  &	348 330 136	&	88 680 716	\\   \hline 
11	&	352 716	&59 348	  &	84 672 315 &16 882 153 & 3 159 461 968	&	804 480 107	\\   \hline \hline
\end{array}$
\end{small}
\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 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{tiny}
\begin{tabular}{||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  \\ \hline
1	&	0	&				&		&		&		&		&		&		&		&		\\ \hline
2	&	3	&	0	&				&		&		&		&		&		&		&		\\ \hline
3	&	22	&	3	&	0	&		&				&		&		&		&		&		\\ \hline
4	&	132	&	26	&	2	&	0	&				&		&		&		&		&		\\ \hline
5	&	824	&	164	&	31	&	4	&	0	&				&		&		&		&		\\ \hline
6	&	5 084	&	1 026	&	276	&	75	&	3	&	0			&		&		&		&		\\ \hline
7	&	31 902	&	6 288	&	2 018	&	829	&	111	&	5		0	&		&		&		&		\\ \hline
8	&	201 366	&	39 090	&	13 282	&	7 231	&	1 837	&	203	&	4	&	0	&				&		\\ \hline
9	&	1 281 918	&	244 833	&	84 340	&	53 594	&	20 681	&	4 259	&	298	&	6	&	0	&				\\ \hline
10	&	8 207 232	&	1 548 774	&	529 578	&	365 461	&	183 262	&	59 726	&	8 709	&	470	&	5	&	0			\\ \hline
11	&	52 819 163	&	9 866 545	&	3 331 910	&	2 385 963	&	1 404 590	&	632 058	&	155 070	&	17 213	&	660	&	7	\\ \hline\hline
\end{tabular} 
\end{tiny}
\caption{ChEGL $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nem $(0,2,n)$-grafikus sorozatok száma   
$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 $(0,2,n)$-grafikus sorozatok számát 
tartalmazza $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!ht]
\centering
\begin{scriptsize}
\begin{tabular}{||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 \\ \hline \hline
1	&	1	&		&		&		&		&		&		&		&		&				\\ \hline
2	&	2	&	0	&		&		&		&		&		&		&		&				\\ \hline
3	&	1	&	9	&	0	&		&		&		&		&		&		&				\\ \hline
4	&	1	&	7	&	42	&	0	&		&		&		&		&		&				\\ \hline
5	&	1	&	10	&	29	&	224	&	0	&		&		&		&		&				\\ \hline
6	&	1	&	14	&	49	&	183	&	1 297	&	0	&		&		&		&				\\ \hline
7	&	1	&	18	&	70	&	345	&	1 143	&	7 658	&	0	&		&			&		\\ \hline
8	&	1	&	23	&	97	&	559	&	2 326	&	7 262	&	46 489	&	0	&		&				\\ \hline
9	&	1	&	28	&	125	&	846	&	4 038	&	15 927	&	46 074	&	286 007	&	0	&				\\ \hline
10	&	1	&	34	&	159	&	1 191	&	6 520	&	29 629	&	107 724	&	295 609	&	1 779 026	&	0			\\ \hline
11	&	1	&	40	&	193	&	1 624	&	9 668	&	50 663	&	213 399	&	728 610	&	1 900 061	&	11 154 877		\\ \hline
\hline 
\end{tabular} 
\end{scriptsize}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt $(0,2,n)$-grafikus sorozatok száma   
$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.

\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,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	\\ \hline
3	&	1,120000000	&	1,900000000	&	1,342857143	&	0,560000000	&	0,950000000	&	0,671428571	\\ \hline
4	&	1,187500000	&	2,820000000	&	1,576190476	&	0,395833333	&	0,940000000	&	0,525396825	\\ \hline
5	&	1,232649071	&	3,803030303	&	1,759906760	&	0,308162268	&	0,950757576	&	0,439976690	\\ \hline
6	&	1,280785891	&	4,788212435	&	1,957042957	&	0,256157178	&	0,957642487	&	0,391408591	\\ \hline
7	&	1,322698224	&	5,770438549	&	2,137870128	&	0,220449704	&	0,961739758	&	0,356311688	\\ \hline
8	&	1,363989613	&	6,751572493	&	2,320248929	&	0,194855659	&	0,964510356	&	0,331464133	\\ \hline
9	&	1,402468979	&	7,733105601	&	2,496464714	&	0,175308622	&	0,966638200	&	0,312058089	\\ \hline
10	&	1,439464334	&	8,714770487	&	2,670148311	&	0,159940482	&	0,968307832	&	0,296683146	\\ \hline
11	&	1,474743645	&	9,697001722	&	2,839981439	&	0,147474365	&	0,969700172	&	0,283998144	\\ 
\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{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\label{thChung} $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}

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

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\label{th-Chungext} $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 $(1 \leq b \leq 2)$. 

\textit{Kimenet.} $L$: $s$ grafikusságát jelző 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{//} 17. sor:  első maradék számítása \\       
\hspace{-7mm}18 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$    \`  \textbf{//} 18--34. 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: $w_i$ frissítése \\ 
\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{//}32. 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 ChHHl futási idejét.
  
\begin{theorem} \emph{(Iványi, \cite{Ivanyi2012})} \rm{ChHHl} futási ideje a legjobb $\Theta(1)$ és a legrosszabb 
$\Theta(n)$ között változik.
\end{theorem}

\begin{proof} A 01--06. sorok végrehajtása $\Theta(1)$ időt igényel. Mivel ezek a sorok a nemgrafikus sorozatok jelentős részét 
kiszűrik, a legjobb futási idő $\Theta(1).$ A 07--11. sorok végrehajtása $\Theta(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 nem $(0,2,n)$-grafikus sorozatok számát 
tartalmazza $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!t]
\centering
\begin{tiny}
\begin{tabular}{||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  \\ \hline
1	&	0	&				&		&		&		&		&		&		&		&		\\ \hline
2	&	3	&	0	&				&		&		&		&		&		&		&		\\ \hline
3	&	22	&	3	&	0	&		&				&		&		&		&		&		\\ \hline
4	&	132	&	26	&	2	&	0	&				&		&		&		&		&		\\ \hline
5	&	824	&	164	&	31	&	4	&	0	&				&		&		&		&		\\ \hline
6	&	5 084	&	1 026	&	276	&	75	&	3	&	0			&		&		&		&		\\ \hline
7	&	31 902	&	6 288	&	2 018	&	829	&	111	&	5		0	&		&		&		&		\\ \hline
8	&	201 366	&	39 090	&	13 282	&	7 231	&	1 837	&	203	&	4	&	0	&				&		\\ \hline
9	&	1 281 918	&	244 833	&	84 340	&	53 594	&	20 681	&	4 259	&	298	&	6	&	0	&				\\ \hline
10	&	8 207 232	&	1 548 774	&	529 578	&	365 461	&	183 262	&	59 726	&	8 709	&	470	&	5	&	0			\\ \hline
11	&	52 819 163	&	9 866 545	&	3 331 910	&	2 385 963	&	1 404 590	&	632 058	&	155 070	&	17 213	&	660	&	7	\\ \hline\hline
\end{tabular} 
\end{tiny}
\caption{ChHHl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt nem $(0,2,n)$-grafikus sorozatok száma   
$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 $(0,2,n)$-grafikus sorozatok számát 
tartalmazza $n = 1, \ \ldots, \ 11$ csúcs esetén.

\begin{table}[!t]
\centering
\begin{scriptsize}
\begin{tabular}{||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 \\ \hline \hline
1	&	1	&		&		&		&		&		&		&		&		&				\\ \hline
2	&	2	&	0	&		&		&		&		&		&		&		&				\\ \hline
3	&	1	&	9	&	0	&		&		&		&		&		&		&				\\ \hline
4	&	1	&	7	&	42	&	0	&		&		&		&		&		&				\\ \hline
5	&	1	&	10	&	29	&	224	&	0	&		&		&		&		&				\\ \hline
6	&	1	&	14	&	49	&	183	&	1 297	&	0	&		&		&		&				\\ \hline
7	&	1	&	18	&	70	&	345	&	1 143	&	7 658	&	0	&		&			&		\\ \hline
8	&	1	&	23	&	97	&	559	&	2 326	&	7 262	&	46 489	&	0	&		&				\\ \hline
9	&	1	&	28	&	125	&	846	&	4 038	&	15 927	&	46 074	&	286 007	&	0	&				\\ \hline
10	&	1	&	34	&	159	&	1 191	&	6 520	&	29 629	&	107 724	&	295 609	&	1 779 026	&	0			\\ \hline
11	&	1	&	40	&	193	&	1 624	&	9 668	&	50 663	&	213 399	&	728 610	&	1 900 061	&	11 154 877		\\ \hline
\hline 
\end{tabular} 
\end{scriptsize}
\caption{ChHHl $i$-edik $(i = 1, \ldots, 11)$ menetében kiszűrt $(0,2,n)$-grafikus sorozatok száma   
$n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHl02g}}
\end{table} 


A \ref{tab-ChHHl02hat}. táblázat a ChHHl algoritmus hatékonyságát jellemzi $(0,2,n)$-szabályos sorozatok 
és $n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChHHl02hat}

\begin{table}[!t]
\centering
\begin{scriptsize}
$\begin{array}{||r|r|r|r|r|r|r||} \hline \hline
\frac{n}{\mbox{jellemző}}  &  X      &  Y    &    Z    &   X'          &  Y'  &    Z'  \\ \hline
2	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	\\ \hline
3	&	1,120000000	&	1,900000000	&	1,342857143	&	0,560000000	&	0,950000000	&	0,671428571	\\ \hline
4	&	1,187500000	&	2,820000000	&	1,576190476	&	0,395833333	&	0,940000000	&	0,525396825	\\ \hline
5	&	1,232649071	&	3,803030303	&	1,759906760	&	0,308162268	&	0,950757576	&	0,439976690	\\ \hline
6	&	1,280785891	&	4,788212435	&	1,957042957	&	0,256157178	&	0,957642487	&	0,391408591	\\ \hline
7	&	1,322698224	&	5,770438549	&	2,137870128	&	0,220449704	&	0,961739758	&	0,356311688	\\ \hline
8	&	1,363989613	&	6,751572493	&	2,320248929	&	0,194855659	&	0,964510356	&	0,331464133	\\ \hline
9	&	1,402468979	&	7,733105601	&	2,496464714	&	0,175308622	&	0,966638200	&	0,312058089	\\ \hline
10	&	1,439464334	&	8,714770487	&	2,670148311	&	0,159940482	&	0,968307832	&	0,296683146	\\ \hline
11	&	1,474743645	&	9,697001722	&	2,839981439	&	0,147474365	&	0,969700172	&	0,283998144	\\ 
\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{$(a,b,n)$-gráfok \label{sec-abn}}
Chungphaisan tételének közvetlen következménye az alábbi állítás. 

\begin{corollary} Legyen\label{cor-Chungab} $n \geq 2$.\label{cor-abn} Az $s = (s_1, \ldots, s_n)$ $(a,b,n)$-szabályos sorozat 
akkor és csak akkor $(a,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}

\begin{proof} 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.
\end{proof} 

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-ChEGl25n1}. és \ref{tab-ChEGl25n2}.  táblázatok a ChEGl $i$-edik -- ahol $(i = 1, \ldots, 4)$, 
illetve $(i = 5, \ldots, 10)$ --  menetében kiszűrt nem $(2,5,n)$-grafikus sorozatok számát 
tartalmazza $n = 1, \ \ldots, \ 11$ csúcs esetén. 


\begin{table}[!t]
\centering
\begin{small}
$\begin{array}{||r|r|r|r|r||} \hline \hline
n/i &  1          &   2         & 3          & 4   \\ \hline \hline
1	&	0	      & 	0	    & 	0	     & 	0	\\ \hline 
2	&	6	      & 	0	    & 	0	     & 	0	\\ \hline
3	&	57	      & 	7	    & 	0	     & 	0	\\ \hline
4	&	475	      & 	83	    & 	7	     & 	0	\\ \hline
5	&	4 099	  & 	732	    & 	163	     & 	13	 \\ \hline
6	&	35 500	  & 	6 287	& 	2 068	 & 	441	 \\ \hline
7	&	312 188	  & 	53 601	& 	20 775	 & 	7 766	 \\ \hline
8	&2 769 457	  & 	463 794	& 	188 643	 & 	97 976	 	\\ \hline
9	&24 768 128	  & 4 061 297	&1 658 351	 & 	1 021 804	 	\\ \hline
10	&222 858 957  & 35 952 854	&14 508 359	 & 	9 681 500	 	\\ \hline
11	&2 015 400 842& 320 927 140	&127 636 563 & 	87 804 078		\\ \hline	  \hline 
\end{array}$ 
\end{small}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 4)$ menetében kiszűrt, nem $(2,5,n)$-grafikus sorozatok száma 
$n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl25n1}}
\end{table}

\begin{table}[!t]
\centering
\begin{small}
$\begin{array}{||r|r|r|r|r|r|r|r||} \hline \hline
n/i & 5  &  6  &   7   &  8    &   9   &  10\\ \hline \hline
1	&	   0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline 
2	&	   0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
3	&	   0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
4	&	   0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
5	&      0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
6	&	      14 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
7	&	     921 & 	21	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
8	&	  24 374 & 	1 921	 & 	23	 & 	0	 & 	0	 & 	0	\\ \hline
9	&	 405 996 & 	71 152	 & 	3 572	 & 	31	 & 	0	 & 	0	\\ \hline
10	&  5 136 605 & 	1 554 803	 & 	186 666	 & 	6 402	 & 	34	 & 	0	\\ \hline
11	& 55 159 143 & 24 279 000 & 5 343 051 & 452 411	 & 	10 751	 & 	43	\\ \hline	  \hline 
\end{array}$ 
\end{small}
\caption{ChEGl $i$-edik $(i = 5, \ldots, 10)$ menetében kiszűrt, nem $(2,5,n)$-grafikus sorozatok száma 
$n = 1, \ \ldots, \ 11$ csúcs esetén.\label{tab-ChEGl25n2}}
\end{table}

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

\begin{table}[!ht]
\centering
\begin{tiny}
$\begin{array}{||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\\ \hline \hline
1	&	1	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline 
2	&	3	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
3	&	1	 & 	19	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
4	&	1	 & 	8	 & 	141	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
5	&	1	 & 	11	 & 	40	 & 	1 129	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
6	&	1	 & 	15	 & 	60	 & 	317	 & 	9 561	 & 	0	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
7	&	1	 & 	19	 & 	81	 & 	497	 & 	2 395	 & 	82 435	 & 	0	 & 	0	 & 	0	 & 	0	\\ \hline
8	&	1	 & 	24	 & 	108	 & 	720	 & 	3 838	 & 	19 074	 & 	722 192	 & 	0	 & 	0	 & 	0	\\ \hline
9	&	1	 & 	29	 & 	136	 & 	1 016	 & 	5 733	 & 	30 725	 & 	153 657	 & 	6 385 472	 & 	0	 & 	0	\\ \hline
10	&	1	 & 	35	 & 	170	 & 	1 366	 & 	8 387	 & 	47 136	 & 	247 112	 & 	1 259 718	 & 	56 880 031	 & 	0	\\ \hline
11	&	1	 & 	41	 & 	204	 & 	1 804	 & 	11 644	 & 	70 961	 & 	385 774	 & 	2 010 389	 & 	10 453 559	 & 	509 514 569	\\ \hline
\hline
\end{array}$
\end{tiny}
\caption{ChEGl $i$-edik $(i = 1, \ldots, 10)$ menetében kiszűrt $(2,5,n)$-grafikus sorozatok száma 
$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|r|r|r|r|r|r||} \hline \hline
\frac{n}{\mbox{jellemző}}&    X &   Y   &    Z   &    X'     &  Y' &    Z'  \\ \hline \hline
2	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	\\ \hline
3	&	1,109375000	&	1,950000000	&	1,309523810	&	0,554687500	&	0,975000000	&	0,654761905	\\ \hline
4	&	1,171681416	&	2,933333333	&	1,541258741	&	0,390560472	&	0,977777778	&	0,513752914	\\ \hline
5	&	1,219093269	&	3,944961897	&	1,739334195	&	0,304773317	&	0,986240474	&	0,434833549	\\ \hline
6	&	1,266350711	&	4,951175407	&	1,942282176	&	0,253270142	&	0,990235081	&	0,388456435	\\ \hline
7	&	1,309250339	&	5,956536499	&	2,135146661	&	0,218208390	&	0,992756083	&	0,355857777	\\ \hline
8	&	1,350304891	&	6,960496382	&	2,325332905	&	0,192900699	&	0,994356626	&	0,332190415	\\ \hline
9	&	1,389017669	&	7,963928944	&	2,510223895	&	0,173627209	&	0,995491118	&	0,313777987	\\ \hline
10	&	1,426027860	&	8,966857120	&	2,691252565	&	0,158447540	&	0,996317458	&	0,299028063	\\ \hline
11	&	1,461490194	&	9,969401198	&	2,868359205	&	0,146149019	&	0,996940120	&	0,286835921	\\ \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{$(0,1,n)$-grafikus sorozatok párhuzamos leszámlálása\label{sec-grafikusszam}}
A \ref{tab-sorozatszam}. táblázat $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. Az eredmény a \textsc{Erdős-Gallai-leszámláló} algoritmus, 
amely minden szóbajövő sorozatot tesztel. Az algoritmus részletes leírása megtalálható a \cite{IvanyiL2012CEJOR} cikkben.

Az algoritmus viszonylag gyors futása érdekében igyekeztünk minél kisebbre választani a vizsgálandó sorozatok halmazát. 
Ezért csak a nullamentes páros sorozatokat teszteltük, hiszen egyrészt a páratlanok nem lehetnek grafikusak, másrészt 
a $G(n)$ függvény értékeit a \ref{lemma-nullaatl}. lemma segítségével könnyen kiszámíthatjuk, ha ismerjük a $G_z(n)$ 
függvény megfelő értékeit. 

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. 


A \textsc{Erdős-Gallai-lineáris} 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 
tartalmazta a grafikus sorozatok számát. Ezt kiegészítettük $n = 29$ csúcsig \cite{Sloane2011A004251}. 

A alábbi \textsc{Erdős-Gallai-leszámláló} (EGl) 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)$ nullamentes 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 ugró pontokban vizsgáljuk.

Az EGl 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-leszámláló} 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. 

Az ugrópontok $C(s')$ listája rendszerint megegyezik 
a $C(s)$ listával, és legfeljebb a végén változik egy vagy két elem.  

Mivel a futási idő csökkentése érdekében az \textsc{Erdős-Gallai-leszámláló} algoritmus csak nullamentes sorozatokat állít elő és 
tesztel, a szeletekre bontás alapja az \eqref{eq-Rn} képlet. 

Feltételezzük, hogy a $(0,n-1,n)$-szabályos nullamentes sorozatok halmazának szeletekre való felbontásánál az egyes szeletek 
futási ideje arányos a hozzájuk tartozó $R(1,n-1,n)$-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. 

\textbf{?????????????}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}
Explicit képletek nem ismertek ismertek a különböző $(a,b,n)$-gráfok foksorozatainak számára. Ugyanakkor intenzív kutatások 
folynak olyan gyors módszerek kidolgozásával kapcsolatban, amelyek  

Kleitman \cite{KleitmanW1981} aszimptotikus korlátokat adott az irányított $(1,1,n)$-gráfok számára, míg Burns \cite{Burns2007}  
az irányítatlan $(0,1,n)$-gráfokéra. Narayana és Bent \cite{NarayanaB1964} rekurzív képleteket javasoltak az irányított 
$(0,1,n)$-gráfok pontos számának meghatározására. P\'ecsy és Sz\H ucs \cite{PecsySz2000} Narayana és Bent képleteit felhasználva  
gyors párhuzamos algoritmussal számították ki a $D(0,1,n)$ függvény értékeit. Iványi et al. \cite{IvanyiLMS2011Acta} 2011-ben 
ugyancsak párhuzamos algoritmussal határozták meg $G(n)$ értékeit $n = 29$-ig.  


\subsection{Konkrét problémák bonyolultsága} 
Ebben a cikkben megmutattuk, hogy nem csak az egyszerű gráfok, hanem még az$(a,b,n)$-gráfok potenciális foksorozatai is 
ellenőrizhetők polinomiális, méghozzá lineáris idő alatt. 

A hiányos gráfok esetén nehezebbek a feladatok. Például a labdarúgást modellező gráfok esetén nyitott kérdés, hogy egy 
$(2,3,n)$-szabályos sorozatról eldönthető-e polinomiális idő alatt, hogy megfelel a labdarúgás szabályainak \cite{Frank2011}. 


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


 
\bigskip
\noindent \textbf{Köszönetnyilvánítás.} A szerzők köszönik az ismeretlen lektor jobbító észrevételeit. 
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{BergerM2010} \textsc{Berger, A., Müller-Hannemann, M.:} \textit{Uniform sampling of digraphs with a fixed 
degree sequence.} In: (ed. D. M. Thilikos) WG2010, LNCS \textbf{6410} (2010), pp. 220--231.

\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{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{Degree sequences of multigraphs.}  
Annales Univ. Budapest., Computatorica (benyújtva).

\bibitem{IvanyiL2012CEJOR} \textsc{Iványi, A., Lucz, L.:} \textit{Parallel Erdős-Gallai theorem.} Central Eur. J. Oper. Res.  
(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{Keri2011} \textsc{Kéri G.:} \textit{On qualitatively consistent, transitive and contradictory judgment matrices 
emerging from multiattribute decision procedures}. Central Eur. J. Oper. Res. \textbf{19(2)} (2011) 215--224.

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

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

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

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

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

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

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

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

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

\bibitem{Lovasz2007} \textsc{Lovász, L.:}  \textit{Combinatorial Problems and Exercises} (corrected version of 
the second edition).  AMS Chelsea Publishing, Boston, 2007. 
Magyarul: \textit{Kombinatorikai problémák és feladatok.} Typotex, Budapest, 1999.

\bibitem{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{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, 2012, to appear.

\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.:} \textit{The number of degree-vectors for simple graphs.} 
In (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2011. http://oeis.org/A004251 .

\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, Komputeralgebra Tanszék \\
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, Komputeralgebra Tanszék \\
1117 Budapest, Pázmány Péter sétány 1/C \\ \\


\begin{center}
\vspace{6mm}

DEGREE SEQUENCES OF MULTIGRAPHS

\vspace{4mm}
\textsc{ANTAL IVÁNYI, LORÁND LUCZ}
\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 Havel-Hakimi 
algorithm and extend it for $(0,2,n)$-graphs.
\end{small}

\end{document}

