\documentclass[b5paper,10pt]{book}
\usepackage{KnuthMarcius30}
\usepackage{mycolortbl}
\usepackage{arabtex}
\usepackage[nocatcodes]{devanagari}


\makeindex

\renewcommand{\sfdefault}{ufu}

\setcounter{chapter}{6}
\setcounter{tocdepth}{4}
\setcounter{section}{5}
\setcounter{subsection}{1}
\setcounter{subsubsection}{3}
\setcounter{figure}{0}
\setcounter{equation}{0}
\setcounter{page}{1}
\font\dnten=dvng8 at 10pt
\font\grkten=kdgr8 at 10pt
\font\arabten=nash14 at 10pt
\font\arab=nash14
  
\begin{document}
\renewcommand\sz[1]{[\textit{#1}]}
\def\figdir{abrak} % ábrakönyvtár átnevezése
\def\CEE/{{\mc C\spacefactor1000}}% the C programming language
\def\MF{{\manfnt META}\-{\manfnt FONT}}%
\def\bool#1{\mathbin{\catcode`\.=12\vcenter{\hbox{$#1$}}}}
\def\nbool#1{\mathbin{\catcode`\.=12     \mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}}
\def\contra{\bool{\bot}} %%% rendben
\def\nimp{\nbool\supset}   %%% rendben
\def\quant{\lower.23ex\hbox{epsfbox{\figdir/v4a.9}}}   %%% ábra kell
\def\lproj{\bool{\epsfbox{\figdir/v4a.10}}}   %%% ábra kell
\def\cnimp{\nbool\subset}    %%% rendben
\def\rproj{\bool{\epsfbox{\figdir/v4a.11}}} %%% ábra kell
\def\xor{\oplus}       %%% rendben
\def\nor{\nbool\lor}   %%% rendben
\def\leqv{\bool\equiv}    %%% rendben
\def\rcomp{\nbool{\rproj}}   %%% ábra kell
\def\cimpl{\bool\subset}   %%% rendben
\def\lcomp{\nbool{\lproj}}   %%% ábra kell
\def\impl{\bool\supset} %%% rendben
\def\nand{\nbool{\land}}  %%% rendben
\def\affirm{\bool{\top}}  %%% rendben
\def\vtiny{\vskip.2pt}    %%% rendben
\def\orie{\rlap{$\,\vec{}$}} % oriented graph modifier
\def\rest{\mathbin{\mid}}

\hyphenation{
The-sau-ru-sát}

\tableofcontents


\chapter{KOMBINATORIKAI ELEMZÉS}

\markboth{\sf 7. KOMBINATORIKAI  ELEMZÉS (4. kötet 0. rész)}
{\sf 7. KOMBINATORIKAI ELEMZÉS (4. kötet 0. rész)}
\pagestyle{myheadings} 


\vspace{-3cm}
{
\quoteformat
Egész nap keresheted, és ha megtaláltad, kiderül, hogy nem érte meg a 
fáradságot. \author BASSANIO, \textsl{A velencei kalmár} (1597)  
\cite[1. felvonás 1. jelenet, 117. sor]{Shakespeare1623}
\angolnevindex{Shakespeare (= Shakspere), William (1564--1616)}
\bigskip
Ahol emberek tömege él sûrûn, egymással állandó kölcsönhatásban, 
az események minden lehetséges kombinációja megtörténhet, 
és sok meglepõ és különös kis probléma merülhet fel.  
\author SHERLOCK HOLMES, \textsl{A kék karbunkulus kalandja} (1892) \cite{Doyle1892}
\angolnevindex{Doyle, Ignatius Arthur Conan, Sir (1859--1930)}
\bigskip
A kombinatorikai algoritmusok területe túl nagy ahhoz, hogy 
egyetlen cikkben, vagy akár egyetlen könyvben tárgyalni lehessen.
\author ROBERT E. TARJAN (1976) \cite[483. oldal]{Tarjan1976}
\angolnevindex{Tarjan, Robert Endre}
\bigskip
Különféle emberekkel találkozva az a benyomás alakult ki bennem,
%B VAGY Mindenféle típusú emberrel összefutottam, és az a benyomás alakult ki bennem...
hogy azok a sikeresek, akiknek természetes 
képességük van a rejtvények\index{rejtvény = puzzle} megoldására. 
Az élet tele van rejtvényekkel, és mi arra vagyunk hivatva,  
hogy megoldjuk azokat, amelyeket a sors elénk vet. 
\author SAM LOYD, JR. (1927) \cite{Loyd1927}
} 

\vskip 20pt plus 12pt

\bigskip
\noindent
A {\tencsc kombinatorika} azokat a módszereket tanulmányozza, amelyek segítségével   
diszkrét objektumok különbözõ mintákba rendezhetõk. 
Például az objektumok lehetnek számok ($2n$ darab), $\{1,1,2,2,\ldots,n,n\}$,
és kívánhatjuk azt, 
hogy sorba legyenek rendezve oly módon, hogy 
minden egyes $k$ számjegy két megjelenése között pontosan $k$ szám forduljon elõ.
Ha $n=3,$ akkor lényegében csak egy módon lehet elrendezni az ilyen 
\idez{Langford-párokat}, nevezetesen $2\, 3\, 1\, 2\, 1\,3$ (és a bal-jobb tükörképe),
\index{Langford-pár = Langford pair}\index{kombinatorika = combinatorics}
hasonlóképpen $n=4$ esetén is egyetlen megoldás van.
Az alábbiakban számos más kombinatorikai példát tárgyalunk meg.

Rendszerint öt alapvetõ csoportba sorolhatók azok a kérdések, amelyek 
kombinatorikai példák tanulmányozása közben felmerülnek, 
néhány  bonyolultabb a többinél.  
\smallskip
\begin{enumerate}
\item[i)] 
Létezés: Van-e olyan $X$ elrendezés, amelyik megfelel egy adott mintának? 
\item[ii)] 
Konstrukció: Ha igen, akkor lehet-e ilyen $X$-et gyorsan találni?
\item[iii)] 
Összeszámlálás: Hány különbözõ $X$ elrendezés létezik?
\item[iv)] 
Elõállítás: Meg lehet-e találni módszeresen az összes $X_1$, $X_2$, \ \dots \ elrendezést?
\item[v)] 
Optimalizálás: Amennyiben adva van egy $f$ célfüggvény, 
mely elrendezések maximalizálják, vagy minimalizálják $f(X)$-et? 
\end{enumerate}
\smallskip\noindent

\goodbreak
\noindent
Ezek a kérdések mind érdekesnek bizonyulnak a Langford-párok esetében. 

\goodbreak
Tekintsük például a létezés kérdését. Puszta próbálkozás útján kideríthetõ, hogy $n=5$ esetén 
nem lehet megfelelõen elrendezni az $\{1,1,2,2,\ldots,5,5\}$ számokat tíz helyen.
Mindkét 1-es vagy páros sorszámú, vagy páratlan sorszámú helyre kell kerüljön; 
hasonlóképpen a 3-asok és az 5-ösök számára két páros, vagy két páratlan 
hely közül kell választanunk; a 2-esek és a 4-esek azonban mindkét paritású helybõl egyet-egyet 
foglalnak el. Azonban nem lehet azonos paritású számokkal pontosan 5 helyet megtölteni. 
Ilyen okfejtéssel látható be az is, hogy nincs megoldás $n=6$ esetén, vagy általánosan 
fogalmazva egyetlen olyan esetben sem, amikor az $\{1,2,\ldots,n\}$ számok között a páratlanok száma páratlan.   

Más szóval a Langford-párok csak akkor létezhetnek, ha $n=4m-1$ vagy $n=4m$, valamilyen egész~$m$ esetén. 
Fordítva, az ilyen alakú $n$-ek esetén Davies\angolnevindex{Davies, Roy Osborne} elegáns módot talált megfelelõ elhelyezés 
készítésére (lásd az \ref{gyak70-1}. gyakorlatot).

Hány lényegében különbözõ $L_n$ pár létezik? $n$ növekedtével egyre több.    
\begin{align*}
L_3 = 1\koz; &\quad \quad &L_4 = 1\koz;\\
L_7=26\koz;&\quad \quad &L_8=150\koz;\\
L_{11}=17{\,}792\koz;&\quad \quad &L_{12}=108{\,}144\koz;\tag{1}\label{keplet70-1}\\
L_{15}=39{\,}809{\,}640\koz;&\quad \quad &L_{16}=326{\,}721{\,}800{}\koz;\\
L_{19}=256{\,}814{\,}891{\,}280\koz;&\quad \quad &L_{20}=2{\,}636{\,}337{\,}861{\,}200\koz;\\
L_{23}=3{\,}799{\,}455{\,}942{\,}515{\,}488\koz;&\quad \quad &L_{24}=46{\,}845{\,}158{\,}056{\,}515{\,}936\koz.
\end{align*}
(Az $L_{23}$ és $L_{24}$ értéket Jaillet, Bui és Krajecki\angolnevindex{Krajecki, Micha$\ddot{\textnormal{e}}$l} \cite{Krajecki2005} 
határozták meg  2004-ben és 2005-ben). Elõzetes vizsgálatok arra mutatnak, hogy ha $L_n$ nem nulla, akkor hozzávetõleg   
$(4n/e^3)^{n+1/2}$ nagyságrendû lehet (lásd az \ref{gyak70-5}. gyakorlatot); és valóban, ez a becslés az összes ismert esetben 
alapvetõen jónak bizonyul. Egyszerû képlet azonban nem ismeretes.  

A Langford-elrendezések feladata a \textit{pontos lefedési probléma}\index{pontos lefedési probléma = exact cover problem} 
néven ismert általános kombinatorikai problémakör speciális esete. A  7.2.2.1. alpontban tárgyaljuk az ún. 
\idez{táncoló mutatók}\index{táncoló mutatók = dancing links} algoritmust \cite{Knuth2000b}, amelyik alkalmas az ilyen probléma 
összes megoldásának elõállítására. Ha például $n=16$, akkor a módszernek csupán körülbelül 3200 memóriahozzáférésre 
van szüksége mindegyik megtalált Langford-pár elrendezéséhez.\index{mems (memóriahozzáférések) = mems} Így $L_{16}$ értéke 
elfogadható idõ alatt kiszámítható egyszerûen az összes pár elõállítása és megszámolása segítségével.
    
Jegyezzük meg azonban, hogy $L_{24}$ \textit{igen nagy} szám -- nagyjából $5\times 10^{16}$, vagy kb. 1500 
MIP-év.\index{MIP-év = MIP-year} (Emlékeztetünk arra, hogy egy \idez{MIP-év} azoknak az utasításoknak a 
száma, amelyeket egy év alatt hajt végre az a gép, amelyik másodpercenként millió utasítást végez el, nevezetesen 
$31\,556\,952\,000\,000$.) Következésképp világos, hogy $L_{24}$ pontos értéke olyan módszerrel lett meghatározva, 
amelyik {\it nem\/} tartalmazta az összes elrendezés elõállítását. Valóban sokkal, sokkal gyorsabb mód $L_n$ kiszámítására az, ha 
polinomalgebrát alkalmazunk. A \ref{gyak70-6}. gyakorlatban leírt tanulságos módszer $O(4^nn)$ mûveletet igényel, 
ami úgy tûnhet, hogy nem hatékony; azonban az állítsd-elõ-és-számlálj módszert egy óriási, $\Theta((n/e^3)^{n-1/2})$ nagyságrendû 
tényezõvel múlja felül, és már $n=16$ esetén is, kb. 20-szor gyorsabban fut le. Másrészt azonban $L_{100}$ pontos értéke 
valószínûleg sohasem lesz ismert, még ha a számítógépek egyre gyorsabbá és gyorsabbá válnak is. 
 
Vizsgálhatjuk azokat a Langford-párokat is, amelyek különbözõ módokon \textit{optimálisak}.  Például elrendezhetünk 16 pár 
súlyt, -- legyenek $\{1,1,2,2,\ldots,16,16\}$ -- oly módon, hogy az elrendezés eleget tegyen Langford feltételének, valamint 
annak a járulékos tulajdonságnak, hogy legyen \idez{jól kiegyensúlyozott},\index{jól kiegyensúlyozott Langford-pár = well-balanced 
Langford pairing} abban az értelemben, hogy nem billen le a mérleg karja, ha a megfelelõ módon vannak a súlyok elhelyezve: 
\setcounter{equation}{1}
\begin{equation}\label{keplet70-2}
\epsfbox{\figdir/v4a.1} \koz .
\end{equation}

\noindent Más szóval, $15.5\cdot16+14.5\cdot6+\cdots+0.5\cdot8=0.5\cdot11+\cdots+14.5\cdot4+15.5\cdot7$; és 
ebben a konkrét példában másfajta egyensúly is fennáll, $16+6+\cdots+8=11+16+\cdots+7$, így 
$16\cdot16+15\cdot6+\cdots+1\cdot8=1\cdot11+\cdots+15\cdot4+16\cdot7$ is teljesül.

Ráadásul, a (\ref{keplet70-2})-beli elrendezés \textit{minimális szélességû}\index{szélesség = width} az összes 
16-od rendû Langford-pár között: A diagram alján lévõ összekötõ szakaszok mutatják, hogy ha balról jobbra haladunk, 
legfeljebb hét olyan pár van, amelyik egy bizonyos pontnál befejezetlen\footnote{Vagyis a pár egyik tagja le van helyezve, 
a másik még nincs. \textit{A fordító.}}, és belátható, hogy a hat szélesség lehetetlen. (Lásd a \ref{gyak70-7}. gyakorlatot).

Az $\{1,1,\ldots,16,16\}$-nak melyik $a_1a_2\ldots a_{32}$ elrendezése a \textit{legkevésbé} kiegyensúlyozott abban az 
értelemben, hogy $\sum_{k=1}^{32}ka_k$ maximális? A lehetséges legnagyobb értéknek 5268 bizonyul. 
Ilyen párosítás 12\,016 van, közülük egy:
\begin{equation}
2\ 3\ 4\ 2\ 1\ 3\ 1\ 4\ 16\ 13\ 15\ 5\ 14\ 7\ 9\ 6\ 11\ 5\ 12
           \ 10\ 8\ 7\ 6\ 13\ 9\ 16\ 15\ 14\ 11\ 8\ 10\ 12\koz.\label{keplet70-3}		   
\end{equation}
Egy érdekesebb kérdés az, hogy a Langford-párok között lexikografikus sorrendben\index{lexikografikus sorrend = lexicographic order}  
melyik a legkisebb és a legnagyobb. A válasz $n=24$ esetén az alábbi, ha az \texttt{a}, \texttt{b}, \dots, \texttt{w,} 
\texttt{x} betûket használjuk az 1, 2, \dots, 23, 24 számok helyett.\angolnevindex{Pohl, Ira Sheldon} 
\begin{equation}
\openup-.5\jot
\def\\#1 {\count255=#1\advance\count255 by`\`\char\count255\kern.9pt}
\eqalignbot{&\llap{$\{$}
\texttt{\\1 \\2 \\1 \\3 \\2 \\4 \\5 \\3 \\6 \\7 \\4 \\15 \\5 \\18 \\19 \\6 \\16 
   \\7 \\17 \\20 \\21 \\23 \\24 \\22 \\10 \\11 \\12 \\15 \\14 \\8 
   \\13 \\9 \\18 \\16 \\19 \\10 \\17 \\11 \\8 \\12 \\20 \\9 \\21 \\14 
   \\13 \\23 \\22 \\24 }\rlap{,}\cr
&\texttt{\\24 \\22 \\23 \\19 \\17 \\21 \\14 \\20 \\11 \\9 \\7 \\18 \\4 \\1 \\16 
  \\1 \\15 \\4 \\7 \\9 \\11 \\14 \\17 \\19 \\22 \\24 \\23 \\21 \\20 \\13 
  \\18 \\16 \\15 \\8 \\12 \\10 \\3 \\6 \\2 \\5 \\3 \\2 \\8 \\13 \\6 \\5 
\\10 \\12 }\rlap{$\}$}\cr}\label{keplet70-4}
\end{equation}
Ennek a fejezetnek késõbbi alfejezeteiben számos kombinatorikus optimalizálásra vonatkozó módszert fogunk 
tárgyalni. A célunk természetesen az, hogy anélkül oldjunk meg ilyen problémákat, 
hogy az összes lehetséges elrendezés halmazának egy kicsi szeleténél többet meg kelljen vizsgálnunk.

\medskip
\noindent \textbf{Ortogonális latin négyzetek.}\index{ortogonális latin négyzet = orthogonal Latin square}
\index{latin négyzet = Latin square} Menjünk vissza egy kis idõre a kombinatorika korai korszakába. 
Ozanam\angolnevindex{Ozanam, Jacques (1640--1717)} \cite[4. kötet 434. oldal]{Ozanam1725} 
könyvének posztumusz kiadásában egy szórakoztató rejtvény található:
\idez{Vegyük az összes ászt, királyt, dámát és bubit egy szokásos csomag
kártyajátékból, és rendezzük õket egy négyzetbe úgy, hogy mindegyik sor és mindegyik oszlop tartalmazza  
mind a négy jelet, és mind a négy színt.} Meg tudjuk csinálni?
Ozanam \angolnevindex{Ozanam, Jacques (1640--1717)} megoldása, amelyet a következõ oldalon a {\ref{abra70-1}. 
ábrán láthatunk, még ennél is többet tesz: Mindkét fõdiagonálisban is 
megjeleníti a jelek és a színek teljes vértezetét. 
(Kérem ne lapozzon addig, amíg meg nem próbálkozott a feladat megoldásával.)

\begin{figure}
\def\\#1.#2.{\epsfxsize=.5in\rlap{\epsfbox{\figdir/#1-of-#2-red.eps}}%
             \epsfxsize=.5in\epsfbox{\figdir/#1-of-#2-black.eps}}
%\hbox to\hsize{\qquad\vbox{\lineskip=3pt\halign{&#\kern3pt\cr
\hbox to\hsize{\qquad\vbox{\lineskip=3pt\halign{&#\kern3pt\cr
\\jack.diamonds.&\\ace.hearts.&\\king.spades.&\\queen.clubs.\cr
\\queen.spades.&\\king.clubs.&\\ace.diamonds.&\\jack.hearts.\cr
\\ace.clubs.&\\jack.spades.&\\queen.hearts.&\\king.diamonds.\cr
\\king.hearts.&\\queen.diamonds.&\\jack.clubs.&\\ace.spades.\cr}}\hfil
\raise10pt\vbox{\hsize=150pt \raggedright \noindent
\caption{Rendetlenség az udvari lapok között. 
Nincs egyezés egyik négy fõs sorban sem. 
(Ez az alakzat egyike a sok lehetségesnek, amelyek a népszerû 
tizennyolcadik századi probléma megoldását adják.)\label{abra70-1}}}\hfil}
\end{figure}

1779 körül egy hasonló rejtvény hozta izgalomba a szentpétervári~köröket, 
ami felkeltette a nagy matematikus  
Euler\angolnevindex{Euler, Leonhard ({\rus E1i0ler, Leonard} = {\rus Ei0lerp2, Leonardp2}, 1707--1783)} 
érdeklõdését.   
\idez{Harminchat tiszt, hat különbözõ rangú, és hat különbözõ ezredbõl való, 
$6\times 6$-os alakzatban akar vonulni, úgy, hogy mindegyik sorban és mindegyik oszlopban 
legyen mindegyik rangú tisztbõl egy, és legyen mindegyik ezredbõl egy. 
Hogyan tudják ezt megtenni?}
Senki nem volt képes megfelelõ menetelési elrendezést találni.
Így Euler eldöntötte, hogy megoldja a találós kérdést -- annak ellenére, 
hogy 1771-ben majdnem teljesen megvakult, és minden munkáját segédeknek diktálta. 
Írt egy jelentõs tanulmányt a témáról  \cite{Euler1782},  
amelyikben elkészítette a megfelelõ elrendezéseket a hasonló feladatokra  
$n$~rang és $n$~ezred esetén, ha $n=1$, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16,
\dots; csak az $n\bmod 4=2$ esetek álltak ellen a megoldásnak.
 
Nyilvánvalóan nincs megoldás, ha $n=2$. Eulert azonban megakasztotta az $n=6$ eset, 
miután \idez{tetemes számú} olyan négyzetes elrendezést vizsgált meg, 
amelyek nem mûködtek. Megmutatta, hogy bármely megtalált megoldás sok más, 
különbözõnek tûnõ megoldáshoz elvezet, és nem hitte, hogy minden ilyen megoldás elkerülte volna a figyelmét.
Ezért azt mondta: \idez{Nem tétovázom levonni azt a következtetést, hogy nem 
lehet elkészíteni a 36 elemû teljes négyzetet, és hogy ez a lehetetlenség továbbgyûrûzik az $n=10$, $n=14$ \dots\ esetekre,
általában minden páratlan sorszámú páros szám esetére.} 

Euler a 36 tisztet ezrede és rangja alapján nevezte el:
$a\alpha$, $a\beta$, $a\gamma$, $a\delta$, $a\epsilon$, $a\zeta$,
$b\alpha$, $b\beta$, $b\gamma$, $b\delta$, $b\epsilon$, $b\zeta$,
$c\alpha$, $c\beta$, $c\gamma$, $c\delta$, $c\epsilon$, $c\zeta$,
$d\alpha$, $d\beta$, $d\gamma$, $d\delta$, $d\epsilon$, $d\zeta$,
$e\alpha$, $e\beta$, $e\gamma$, $e\delta$, $e\epsilon$, $e\zeta$,
$f\alpha$, $f\beta$, $f\gamma$, $f\delta$, $f\epsilon$, $f\zeta$.
Megfigyelte, hogy mindegyik megoldást össze lehet építeni két \textit{különálló} négyzetbõl, 
ha az egyik négyzet latin betûket, a másik görög betûket tartalmaz.  
Mindegyik ilyen négyzetben minden sorban és minden oszlopban 
különböznek az elemek; így elkezdett foglalkozni $\{a,b,c,d,e,f\}$ 
lehetséges elrendezéseivel, amelyeket \textit{latin négyzeteknek} hívott.
Egy latin négyzet csak akkor párosítható egy görög négyzettel 
\idez{görög-latin négyzetté}\index{görög-latin négyzet = Gr{\ae}co-Latin square},
ha a négyzetek \textit{ortogonálisak} egymásra, ami azt jelenti, hogy egy (latin, görög) betû pár   
nem fordul elõ egynél több helyen, ha a négyzeteket összeépítjük.  
Ha például az $a =\texttt{A}$, $b = \texttt{B}$, $c = \texttt{Q}$, $d =\texttt{J}$, $\alpha=\clubsuit$,
$\beta=\spadesuit$, $\gamma=\diamondsuit$, és $\delta=\heartsuit$,
akkor a \ref{abra70-1}. ábrának az alábbi latin, görög és görög-latin 
négyzetek felelnek meg.
\begin{equation}
\begin{pmatrix}d&a&b&c\\ c&b&a&d\\ a&d&c&b\\ b&c&d&a\\
\end{pmatrix},\,
  \begin{pmatrix}\gamma&\delta&\beta&\alpha\\
           \beta&\alpha&\gamma&\delta\\
           \alpha&\beta&\delta&\gamma\\
           \delta&\gamma&\alpha&\beta\\
		   \end{pmatrix}\,\ \hbox{és}\,
\begin{pmatrix}d\gamma&a\delta&b\beta&c\alpha\\
           c\beta&b\alpha&a\gamma&d\delta\\
           a\alpha&d\beta&c\delta&b\gamma\\
           b\delta&c\gamma&d\alpha&a\beta\\
		   \end{pmatrix}.\label{keplet70-5}
\end{equation}
Természetesen {\it bármilyen\/} $n$ különbözõ szimbólumot alkalmazhatunk 
egy $n\times n$-es latin négyzetben; 
mindössze az a fontos, hogy egyetlen szimbólum se forduljon elõ kétszer 
valamelyik sorban, vagy kétszer valamelyik oszlopban.  
Így alkalmazhatunk az elemek számára 
numerikus értékeket is, $\{0,1,\ldots,n{-}1\}$-et. 
A továbbiakban hivatkozhatunk egyszerûen \idez{latin négyzetre},
ahelyett, hogy vagy latin, vagy görög kategóriába osztanánk a négyzeteket, 
hiszen a merõlegesség szimmetrikus reláció. 

Euler állítását, miszerint két $6\times 6$-os négyzet nem lehet ortogonális, 
Clausen\angolnevindex{Clausen, Thomas} megerõsítette, aki  
Schumacher\angolnevindex{Schumacher, Heinrich Christian (1780--1850)}   
{Gaussnak}\angolnevindex{Gauss, Carl Friedrich} írt levele szerint \cite{Schumacher1842}   
17 alapvetõen különbözõ eset vizsgálatára redukálta a feladatot.   
Clausen azonban nem publikálta az elemzését.  
Az elsõ nyomtatásban megjelent bizonyítás  
Tarrytõl\angolnevindex{Tarry, Gaston (1843--1913)} \cite{Tarry1901} származik, 
aki a maga egyéni módján fedezte fel, hogy a $6\times 6$-os latin 
négyzetek 17 különbözõ családba osztályozhatók. 
(A 7.2.3. pontban tanulmányozni fogjuk, hogyan lehet 
szétbontani a feladatot az elrendezések kombinatorikailag 
nem ekvivalens osztályaira.)

Euler sejtését a fennmaradó $n=10$, $n=14$, \dots\ esetekrõl háromszor \idez{bizonyították}, 
Petersen \angolnevindex{Petersen, Julius Peter Christian} \cite{Petersen1902}, 
Wernicke\angolnevindex{Wernicke, August Ludwig Paul} \cite{Wernicke1910}
és MacNeish\angolnevindex{MacNeish, Harris Franklin (1854--1929)} \cite{MacNeish1922}. 
Kiderült azonban, hogy mindhárom érvelés hibás; a kérdés mindaddig megválaszolatlan maradt, amíg 
sok évvel késõbb a számítógépek meg nem jelentek. A legelsõ kombinatorikai problémák egyike, amelyikhez 
géppel fogtak hozzá, a $10\times 10$-es görög-latin négyzetek rejtvénye: Léteznek, vagy nem léteznek? 

1957-ben Paige\angolnevindex{Paige, Lowell J.} és  
Tompkins\angolnevindex{Tompkins, Charles Brown} arra programozták a  {{\mc SWAC}}
számítógépet, hogy Euler sejtésére ellenpéldát keressen.  
Kiválasztottak egy bizonyos \idez{majdnem véletlen} $10\times 10$-es 
latin négyzetet, és a programjuk próbált egy erre ortogonális 
másik négyzetet találni. Az eredmény azonban elkedvetlenítõ volt, és öt óra futás után 
úgy döntöttek, hogy kikapcsolják a gépet. Ekkorra a program elegendõ adatot állított elõ számukra, hogy megjósolhassák, 
hogy legalább $4.8\times 10^{11}$ óra gépidõre lenne szükség a futás befejezéséhez!

Röviddel ezután három matematikus munkája áttörést hozott, s ez  
a latin négyzeteket a nemzetközi napilapok elsõ oldalára juttatta:  
Bose\angolnevindex{Bose, Raj Chandra (1901--1987)} \cite{Bose1959,Bose1960},  
Shrikande\angolnevindex{Shrikande, Sharadchandra Shankar}, 
és Parker\angolnevindex{Parker, Ernest Tilden} \cite{Parker1963}
figyelemreméltó konstrukció sorozatot találtak, amelyik 
ortogonális $n\times n$-es négyzeteket szolgáltat minden $n>6$ esetén.    
Így, miután 180 évig ellenállt a támadásoknak, 
Euler sejtése majdnem teljesen tévesnek bizonyult. 

Felfedezésüket számítógép segítsége nélkül tették. 
Parker azonban az {\mc UNIVAC} számára dolgozott, 
és hamarosan programozási jártasságot hozott a képbe, 
amivel Paige és Tompkins problémáját kevesebb, mint 
egy óra alatt oldotta meg az   
{\mc UNIVAC} 1206 Military Computer-en.
\index{univac@{\mc UNIVAC} 1206 katonai számítógép = {\mc UNIVAC} 1206 Military Computer}

Nézzük meg közelebbrõl azt, amit a korábbi programozók tettek, és hogy Parker milyen drámaian múlta felül a megközelítésüket.
Paige\angolnevindex{Paige, Lowell J.} és  Tompkins\angolnevindex{Tompkins, Charles Brown} \cite{Paige1960}
a következõ $10\times 10$-es $L$ négyzettel, valamint ismeretlen, rá ortogonális $M$~párjával (párjaival) kezdte: 
\newpage
\vspace{-4mm}
\begin{equation}
L=\begin{pmatrix}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!5\!&\!6\!&\!7\!&\!8\!&\!9\\
1\!&\!8\!&\!3\!&\!2\!&\!5\!&\!4\!&\!7\!&\!6\!&\!9\!&\!0\\
2\!&\!9\!&\!5\!&\!6\!&\!3\!&\!0\!&\!8\!&\!4\!&\!7\!&\!1\\
3\!&\!7\!&\!0\!&\!9\!&\!8\!&\!6\!&\!1\!&\!5\!&\!2\!&\!4\\
4\!&\!6\!&\!7\!&\!5\!&\!2\!&\!9\!&\!0\!&\!8\!&\!1\!&\!3\\
5\!&\!0\!&\!9\!&\!4\!&\!7\!&\!8\!&\!3\!&\!1\!&\!6\!&\!2\\
6\!&\!5\!&\!4\!&\!7\!&\!1\!&\!3\!&\!2\!&\!9\!&\!0\!&\!8\\
7\!&\!4\!&\!1\!&\!8\!&\!0\!&\!2\!&\!9\!&\!3\!&\!5\!&\!6\\
8\!&\!3\!&\!6\!&\!0\!&\!9\!&\!1\!&\!5\!&\!2\!&\!4\!&\!7\\
9\!&\!2\!&\!8\!&\!1\!&\!6\!&\!7\!&\!4\!&\!0\!&\!3\!&\!5\\
\end{pmatrix}
\ \hbox{és}\  
M=
\begin{pmatrix}
0\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
1\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
2\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
3\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
4\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
5\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
6\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
7\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
8\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
9\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\!&\!\sqcup\\
\end{pmatrix}
%.\eqno(6)$$
.\label{keplet70-6}
\end{equation}
Az általánosság korlátozása nélkül feltehetjük, hogy $M$ sorai a 
0, 1, \dots,~9 számokkal kezdõdnek, amint látható. 
A feladat a maradék 90 üres hely kitöltése, és ezt az eredeti
{\mc SWAC}\index{svac@{\mc SWAC} = {\mc SWAC}} program felülrõl lefelé, balról jobbra haladva végezte el. 
A bal felsõ \raise.25ex\hbox{\tt\char"20} nem tölthetõ ki 0-val,
mert a 0 már elõfordul $M\!\,$~ felsõ sorában. 
És nem lehet 1 sem, mert az $(1,1)$ pár ott van $(L,M)$ következõ sorában a bal oldalon. 
Ámde próbaként beilleszthetünk egy 2-est.
Az 1-es számjegy a következõ helyre tehetõ;
és nagyon hamar megkapjuk $M\!\,$~számára 
a lexikografikusan legkisebb lehetséges felsõ sort, 
nevezetesen $0\,2\,1\,4\,3\,6\,5\,8\,9\,7$-et.
Hasonlóképpen a $0\,2\,1\,4\,3\,6\,5\,8\,9\,7$ alá 
illeszkedõ legkisebb sorok $1\,0\,2\,3\,4\,5\,6\,7\,8\,9$ és
$2\,1\,0\,8\,5\,3\,7\,9\,4\,6$; 
és a legkisebb szabályos sor alattuk a 
$3\,5\,4\,0\,6\,1\,9\,2\,7\,8$. 
Most azonban sajnos megakadunk: 
Nincs lehetõség arra, hogy újabb sort megtöltsünk, anélkül, 
hogy egy korábbi választással ellentmondásba ne kerülnénk.  
Így $3\,5\,4\,0\,6\,1\,9\,2\,7\,8$-at lecseréljük  
$3\,5\,4\,0\,6\,2\,9\,1\,7\,8$-ra, (de ez sem mûködik),
majd $3\,5\,4\,0\,6\,9\,8\,1\,7\,2$-re, és így haladunk   
több további lépésen keresztül, míg végül  
$3\,5\,4\,6\,1\,0\,9\,2\,7\,8$-at és az õt követõ 
$4\,3\,9\,7\,0\,2\,8\,6\,5\,1$-et választjuk, 
mielõtt újra elakadunk. 

A 7.2.3. pontban tanulmányozni fogunk arra vonatkozó lehetõségeket, 
hogy hogyan lehet ilyen keresések viselkedését anélkül megbecsülni, 
hogy ténylegesen végrehajtanánk õket. 
Ilyen becslések alapján ebben az esetben azt mondhatjuk, 
hogy a  Paige--Tompkins módszer lényegében 
egy olyan {keresõ fát}\index{keresõ fa = search tree} jár be, amelyiknek körülbelül $2.5\times10^{18}$ 
csúcsa van.
Ezeknek a csúcsoknak a nagy része a fának csak kevés szintjéhez tartozik hozzá; 
több, mint a felük azokra a választásokra vonatkozik, amelyek 
$M\!\ $~hatodik sorának jobb felén állnak, miután 
a 90 helybõl körülbelül 50 már ki lett töltve próbálkozással. 
A keresõ fa egy tipikus csúcsának ellenõrzése 
várhatóan körülbelül 75 
{mems}-et (memóriahozzáférést)\index{mems (memóriahozzáférések) = mems} igényel. 
Így a teljes futási idõ egy modern számítógépen 
nagyjából megegyezik a végrehajtáshoz szükséges 
$2\times10^{20}$ mems végrehajtásának az idejével. 

Parker, ezzel szemben visszanyúlt ahhoz a módszerhez, amelyet   
Euler\angolnevindex{Euler, Leonhard ({\rus E1i0ler, Leonard} = {\rus Ei0lerp2, Leonardp2}, 1707--1783)} 
\cite{Euler1782} alkalmazott 
eredetileg ortogonális párok keresésére 1779-ben. 
Elõször megkereste $L$ összes úgynevezett {\it tranzverzálisát\/}\index{tranzverzális = transversal}, 
nevezetesen az összes lehetséges módon kiválasztott néhányat az $L$ elemei közül  
úgy, hogy pontosan egy elem legyen minden sorból, egy minden oszlopból, 
és egy minden értékbõl. Például az, hogy $0\,8\,5\,9\,7\,3\,4\,2\,1\,6$ egy tranzverzális, Euler jelölése  
szerint azt jelenti, hogy 0-t választjuk a 0~oszlopból, 8-at az 1~oszlopból, 
\dots, 6-ot a 9~oszlopból. Minden olyan tranzverzális, amelyik tartalmazza az $L$ legbaloldalibb oszlopában 
lévõ $k$-t, egy szabályos módja a tíz $k$  $M$~négyzetben való elhelyezésének.   
A tranzverzálisok megtalálásának munkája valójában meglehetõsen könnyû, 
és kiderül, hogy az adott $L$~mátrixnak  pontosan 808 tranzverzálisa van; 
rendre $(79,96,76,87,70,84,83,75,95,63)$ tranzverzális van $k=(0,1,\ldots,9)$ esetén. 

Amint a tranzverzálisok ismertté válnak, marad egy 10 lépcsõs teljes lefedési problémánk}\index{teljes lefedési probléma = 
exact cover problem}, ami jóval egyszerûbb, mint az eredeti 90 lépcsõs (\ref{keplet70-6})-ban.  
Az összes hátralévõ munkánk annyi, hogy lefedjük a négyzetet tíz egymással nem keresztezõdõ tranzverzálissal -- 
ugyanis a tízesek minden ilyen halmaza egy olyan $M$~latin négyzettel ekvivalens, amelyik $L$-re ortogonális.   

A (\ref{keplet70-6})-beli $L$ négyzetnek valójában pontosan egy ortogonális párja van:
\bigskip
\begin{equation}
\def\normalbaselines{\baselineskip=10pt}\let\quad=\enspace
\begin{pmatrix}
0&1&2&3&4&5&6&7&8&9\\
1&8&3&2&5&4&7&6&9&0\\
2&9&5&6&3&0&8&4&7&1\\
3&7&0&9&8&6&1&5&2&4\\
4&6&7&5&2&9&0&8&1&3\\
5&0&9&4&7&8&3&1&6&2\\
6&5&4&7&1&3&2&9&0&8\\
7&4&1&8&0&2&9&3&5&6\\
8&3&6&0&9&1&5&2&4&7\\
9&2&8&1&6&7&4&0&3&5\\
\end{pmatrix}
\quad\perp\quad
\begin{pmatrix}
0&2&8&5&9&4&7&3&6&1\\
1&7&4&9&3&6&5&0&2&8\\
2&5&6&4&8&7&0&1&9&3\\
3&6&9&0&4&5&8&2&1&7\\
4&8&1&7&5&3&6&9&0&2\\
5&1&7&8&0&2&9&4&3&6\\
6&9&0&2&7&1&3&8&4&5\\
7&3&5&1&2&0&4&6&8&9\\
8&0&2&3&6&9&1&7&5&4\\
9&4&3&6&1&8&2&5&7&0\\
\end{pmatrix}
.\label{keplet70-7}
\end{equation}
A táncoló mutatók\index{táncoló mutatók = dancing links} algoritmus megtalálja ezt a párt, és bebizonyítja, 
hogy ez az egyetlen, miután csupán $1.7\times 10^8$ mems számítást végez el   
808 tranzverzális esetén. Ezen kívül van a tranzverzálisok elõállítása során jelentkezõ költség, 
körülbelül 5~millió mems, ami elhanyagolható a többihez képest. Így az eredeti $2\times 10^{20}$~mems futási ideje -- 
amit korábban úgy tekintettünk, mint az üres helyek $10^{90}$ lehetséges kitöltésére vonatkozó feladat 
elkerülhetetlen költsége --, egy $10^{12}$-nél (!) nagyobb tényezõvel lett kisebb. 

Késõbb látni fogjuk, hogy még milyen fejlesztéseket végeztek a (\ref{keplet70-6})-hoz hasonló 90 szintes problémák 
megoldására alkalmas módszerekben. Valójában (\ref{keplet70-6}) egy teljes lefedési probléma 
(lásd a \ref{gyak70-17}. gyakorlatot) közvetlen képviselõjének bizonyult,    
amelyiket a 7.2.2.1. alpontban szereplõ táncoló mutatók algoritmus csupán $1.3\times 10^{11}$ mems 
költségével old meg. Az Euler\angolnevindex{Euler, Leonhard ({\rus E1i0ler, Leonard} = {\rus Ei0lerp2, Leonardp2}, 1707--1783)}
--Parker\angolnevindex{Parker, Ernest Tilden}-megközelítés mégis körülbelül ezerszer jobb maradt, mint a   
{Paige}\angolnevindex{Paige, Lowell J.}--{Tompkins}\angolnevindex{Tompkins, Charles Brown}-megközelítés.
Azzal, hogy a feladatot két különálló fázisra bontották, egyik a tranzverzális-keresés, másik a tranzverzális-összekapcsolás, 
a $T_1T_2$ szorzat költséget Euler és Parker a $T_1+T_2$ összeg költségre redukálták.   

A történet tanulsága nyilvánvaló: kombinatorikai problémák a lehetõségek roppant nagy tárházával szembesíthetnek minket, 
mégsem szabad túl könnyen feladnunk. Egyetlen jó ötlet a számítások mennyiségét sok nagyságrenddel képes csökkenteni. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  2. RÉSZ

\medskip
\noindent \textbf{Rejtvények és a való világ.}\index{rejtvény = puzzle}
Számos olyan kombinatorikai problémát tanulmányozunk ebben a fejezetben, 
mint {Langford}\angolnevindex{Langford, Charles Dudley} párokra vonatkozó problémáját,  
vagy {Ozanam}ét\angolnevindex{Ozanam, Jacques (1640--1717)} a tizenhat honor kártyalapra vonatkozóan,
amelyeket eredetileg élvezetes rejtvényeknek, vagy \idez{fejtörõknek} szántak.
Egyes Olvasókat talán megtéveszthet a szórakoztató\index{felüdülés = recreation} 
témák e hangsúlyozása, ezekre úgy tekintenek, mint léha idõpocsékolásra. 
Nem kellene valójában a számítógépeknek hasznos munkát végezniük?
És nem az ipar és/vagy a világ elõrehaladását 
elõsegítõ jelentõs alkalmazásokkal kellene 
a számítógép-tankönyveknek elsõsorban foglalkozniuk?

Nos az Olvasó kezében tartott könyv 
szerzõjének\angolnevindex{Knuth@\string\Knuth} 
egyáltalán nincs kifogása a hasznos munka és az emberi elõrehaladás ellen. 
Erõsen hiszi azonban, hogy egy olyan könyvnek, mint amilyen ez is, 
probléma megoldó {\it módszerekre\/} kell helyeznie a hangsúlyt, 
valamint ezzel együtt különbözõ problémák megoldásában segítõ 
matematikai elméletekre és {\it modellekre\/}, 
inkább, mint hogy arra összpontosítson, 
hogy ezek a módszerek és modellek miért használhatóak. 
A kombinatorikai problémák kezelésére számos gyönyörû és hathatós 
eljárást fogunk megismerni, 
és ezeket a módszereket elsõsorban eleganciájuk 
miatt fogjuk tanulmányozni. 
Kombinatorikai kihívások mindenhol felbukkannak, 
és minden nap új lehetõségek támadnak az ebben a fejezetben 
tárgyalt technikák alkalmazására.  
Ne korlátozzuk tehát látókörünket azzal, hogy elõre 
megpróbáljuk számba venni azt, hogy mire jók az elméletek.  

Kiderül például, hogy az ortogonális latin négyzetek roppant hasznosak, kiváltképpen kísérletek tervezésében.
Már 1788-ban használta Palluel\angolnevindex{Crett\'e de Palluel, Fran\c{c}ois} a $4{\times}4$-es latin négyzeteket 
annak a tanulmányozására, hogy mi történik, ha tizenhat birkát\index{birka = sheep} (négyet-négyet más és más fajtából) 
négy különbözõ étrend szerint táplálnak és négy különbözõ idõben nyírnak (lásd \cite{Palluel1788}). 
A latin négyzet lehetõvé tette számára, hogy mindezt 16 birkával tegye 64 helyett; 
\index{ortogonális latin négyzet = orthogonal Latin square}\index{latin négyzet = Latin square} 
görög-latin négyzettel \index{görög-latin négyzet = Gr{\ae}co-Latin square} más paramétereket is változtatni tudott a kísérlethez, 
mondjuk, a táplálék négy különbözõ mennyiségét, vagy négy különbözõ legeltetési mintát. 

De ha tárgyalásunkat az õ állattenyésztésre vonatkozó megközelítésére fókuszáltuk volna, beleveszhettünk volna a tenyésztés, 
a zöldség termesztése szemben a gabonáéval, és a termesztési költségük stb. részleteibe. Azok az Olvasók, akik nem farmerek, 
ezért dönthettek volna úgy, hogy az egész témát átugorják, annak ellenére, hogy a latin négyzet mintázatok számos problémára 
alkalmazhatóak. (Gondoljunk arra, hogy ötféle pirulát tesztelünk olyan betegeken, akik valamilyen betegség 
öt fázisának valamelyikében szenvednek, öt különbözõ életkorúak, öt súlycsoportba tartoznak.)
Továbbá, ha túlságosan  a kísérlettervezésre koncentrálunk, az oda vezethet, hogy az olvasó figyelmen kívül  hagyja 
azt a tényt, hogy a latin négyzeteket jelentõs mértékben alkalmazzák a kódolásban és a rejtjelezésben is (lásd a 
\ref{gyak70-18}--\ref{gyak70-24}. gyakorlatokat).

Még a {Langford-párosítások}\index{Langford-párosítások = Langford pairing} témájáról is kiderül,
 -- amely elsõre pusztán felfrissítõnek tûnik --, hogy gyakorlati jelentõségû. 
{Skolem}\angolnevindex{Skolem, Albert Thoralf (1867--1963)} használta a Langford-sorozatokat 
{Steiner-hármas rendszerének}\index{Steiner-hármas rendszere = Steiner triple system}
konstruálásához  \cite{Skolem1958}, amit adatbázis keresésekre alkalmaztunk a 6.5. alfejezetben;
az 1960-as években pedig {Groth}\angolnevindex{Groth, Edward John, Jr.} \cite{Groth1968} 
(Motorola Corporation) a Langford-párokat szorzó\index{szorzás = multiplication} áramkörök tervezésére alkalmazta.
Továbbá azok az algoritmusok, amelyek hatékonyan találják meg a Langford-párokat és a latin négyzet tranzverzálisokat, mint a 
táncoló mutatók algoritmus, alkalmazhatók általában a pontos lefedési problémára\index{pontos lefedési probléma = 
exact cover problem}; és a pontos lefedés problémája nagy fontossággal bír olyan életbe vágó problémák esetén, mint a 
szavazó körzetek igazságos felosztása\index{felosztás = apportionment} választói kerületekbe\index{választói kerületek = 
electoral districts} stb.

Nem az alkalmazások a legfontosabbak, és nem azok a rejtvények sem. Elsõdleges célunk inkább az, hogy alapvetõ fogalmakat 
ismerjünk meg,  mint a latin négyzetek és a teljes lefedés fogalma.  Az ilyen fogalmak építõ köveket adnak nekünk, 
szókincset és éleslátást, és betekintést abba, hogy a \textit{holnap} problémáinak mire lesz szüksége. 

Ámde ostobaság probléma megoldásról tárgyalni anélkül, hogy egyetlen problémát is megoldanánk ténylegesen. 
Szükségünk van jó problémákra, hogy serkentsük alkotó képességünket,   
hogy többé kevésbé rendszerezett módon aktivizáljuk a szürkeállományunkat 
és az alapvetõ elméleteket ismerõssé tegyük. A fejtörõ rejtvények gyakran ideálisak erre a célra, 
mert néhány szóban bemutathatók, és nem igényelnek bonyolult tudományos hátteret. 

Václav Havel egyszer megjegyezte \cite{Havel1992}, \angolnevindex{Havel, Václav (drámaíró és államférfi)}  
hogy az élet rendkívül bonyolult: \idez{Túl sok a tudnivaló\ldots 
Fel kell hagynunk azzal a nagyképû hiedelemmel, hogy a világ pusztán 
egy megoldandó rejtvény, hogy egy gép felfedezésre váró használati utasításokkal, 
hogy számítógép táplálására való információk tömege.}
Az igazságosság és felelõsség érzetének növelésére szólított fel; ízlésre, 
bátorságra és részvétre. Szavai telve vannak nagy bölcsességgel. 
Mégis, hála a Gondviselésnek, vannak olyan rejtvényeink, amelyek \textit{megoldhatóak}! 
A rejtvények méltóak arra, hogy az élet nagy élvezetei között tartsuk számon õket, 
hogy mértékkel élvezzük õket más mulatságokhoz hasonlóan. 

Természetesen {Langford}\angolnevindex{Langford, Charles Dudley} és Ozanam\angolnevindex{Ozanam, Jacques (1640--1717)} 
emberi célra szánták rejtvényüket, nem pedig számítógép számára. Nem tévesztünk-e célt, ha pusztán áthárítjuk az 
ilyen kérdéseket a gépekre, nyers erõvel oldva meg azokat, racionális meggondolás helyett?
Brewster\angolnevindex{Brewster, George} írta Gardnernek\angolnevindex{Gardner, Martin} 1963-ban  
sokak által elfogadott véleménynek adva hangot: \idez{Szórakoztató rejtvényekkel táplálni a számítógépet nem több, mint 
dinamittal halászni pisztrángra, tönkre téve a pillanatnyi szórakozást.}

Igen, de ez a nézet figyelmen kívül hagy még egy fontos szempontot: Az egyszerû rejtvényeknek gyakran vannak olyan általánosításaik, 
amelyek túlmutatnak az emberi képességen és felkeltik a kíváncsiságunkat. Ezeknek az általánosításoknak a vizsgálata gyakran 
sugall olyan tanulságos módszereket, amelyek számos más problémánál alkalmazhatóak, és meglepõ következményei vannak. 
Csakugyan, számos fontos technika, amelyet tanulmányozni fogunk, akkor született, amikor különféle rejtvényeket próbáltak megoldani. 
Bár ennek a fejezetnek az írása során a szerzõ\angolnevindex{Knuth@\string\Knuth} nem tehetett róla, de élvezte azt a tényt, 
hogy a rejtvények manapság sokkal érdekesebbek, mint valaha, miközben a gépek egyre gyorsabbá és gyorsabbá válnak, ugyanis egyre 
több hatásos dinamitunk van a velük való játékhoz. (További megjegyzések bukkannak fel a szerzõ tanulmányában \cite{Knuth1996}.)

A rejtvények magukban rejtik azt a veszélyt, hogy \textit{túl} elegánsak lehetnek. A jó rejtvények matematikailag tiszták és 
jól strukturáltak szoktak lenni, de meg kell tanulnunk azt is, hogyan kezeljük módszeresen a rendetlenséget, a káoszt, 
az organikus anyagot, amelyik minden nap körülvesz bennünket. Valóban, néhány számítási technika fõleg azért fontos, mert 
hatékony módszert nyújt arra, hogy megbirkózzunk az ilyen bonyolultságokkal. Ilyenek például a könyvtár cédulák ábécérendbe 
helyezésének misztikus szabályai, amelyeket az 5. fejezet elején mutattunk be, és az aktuális választói rendszer, amit a  
szimulációs technikák illusztrálására részletesen tárgyaltunk a 2.2.5. pontban. 

A Stanford GráfBázis\index{Stanford GráfBázis = Stanford GraphBase} 
(SGB\index{SGB@\textit{SGB}= Stanford GráfBázis, \textit{lásd} Stanford GráfBázis = \textit{SGB} Stanford GraphBase, \see  
Stanford GraphBase}) nevû program- és adatgyûjtemény úgy készült, hogy kombinatorikus algoritmusokkal végzett 
kísérletek könnyen végrehajthatóak legyenek számos, a valódi világban elõforduló példán. Az SGB tartalmaz például adatokat az 
amerikai autópályákról, és tartalmazza az USA gazdaságának input-output modelljét; feljegyzi 
Homérosz\angolnevindex{Homérosz (i.e. 850 körül)} {\sl Iliászának} \cite{Homer850}, 
Tolsztoj\angolnevindex{Tolsztoj, Lev Nyikolajevics (1828--1910, {\rus Tolstoi0, Lev Nikolaevich})} 
{\sl Anna Kareninájának} \cite{Tolstoy1877}, és sok más  {regénynek}\index{regény = novel} a karakterkészletét,  
magában foglalja Roget\angolnevindex{Roget, Peter Mark (1779--1869)} 1879-beli \textsl{Thesaurusát} \cite{Roget1879},   
dokumentálja a fõiskolai futball eredmények százait; megadja Leonardo da Vinci\angolnevindex{Leonardo, di ser Piero da 
Vinci (1452--1519)} \textsl{Gioconda} (Mona Lisa) képén \cite{Leonardo1506} a pixelek színeinek az értékét. 
És ami talán a legfontosabb, az SGB tartalmazza az ötbetûs szavak gyûjteményét, amit az alábbiakban fogunk megtárgyalni.

\medskip
\noindent \textbf{Az angol nyelv ötbetûs szavai.}\index{ötbetûs szavak = five-letter words}
Ebben a fejezetben sok példa az ötbetûs szavak következõ listáján alapszik: 
\begin{equation}
\texttt{aargh},\ 
\texttt{abaca},\
\texttt{abaci},\
\texttt{aback},\
\texttt{abaft},\
\texttt{abase},\
\texttt{abash},\
\ldots,\
\texttt{zooms},\
\texttt{zowie}\koz.\label{keplet70-8}
\end{equation}
(Összesen 5757 szó van, -- túl sok ahhoz, hogy mindet megmutassuk itt; de a hiányzóak könnyen elképzelhetõek.)
Ez egy személyes lista, a szerzõ\angolnevindex{Knuth@\string\Knuth} gyûjtötte össze 1972 és 1992 között, azért kezdte el, mert 
megértette, hogy az ilyen szavak \texttt{ideális} adatot képeznek sokféle kombinatorikai algoritmus teszteléséhez. 

A lista szándékosan le lett szûkítve azokra a szavakra, amelyek 
\texttt{valóban} elõfordulnak az angol nyelvben, 
abban az értelemben, hogy 
a szerzõ valóban találkozott velük használatban.
Teljes szótárak \index{szótár = dictionary} tartalmazzák olyan bejegyzések 
ezreit, melyek sokkal ezoterikusabbak, 
mint az \texttt{aalii}, \texttt{abamp}, \dots, \texttt{zymin},
és \texttt{zyxst}; olyan szavakat, amelyek elsõsorban a 
Scrabble$^{\setbox0=\hbox{$\scriptstyle\bigcirc$}
     \rlap{\hbox to\wd0{\hss$\scriptscriptstyle\rm R$\hss}}\box0}\!$
játékosok számára hasznosak. A szokatlan szavak azonban \texttt{elrontják} a szórakozását annak, aki nem ismeri õket.
Így a szerzõ húsz éven át szisztematikusan jegyzékbe vette az összes \texttt{szót}, 
amelyik \texttt{jónak} (right) látszott \textsl{A számítógép-programozás mûvészete} kitûzött \texttt{céljai} számára. 

Végül be kellett fagyasztani a gyûjteményt, azért, hogy legyen \texttt{fix} \texttt{pontunk} a
megismételhetõ kísérletek számára. Az angol nyelv állandóan fejlõdik, az 5757 SGB szó azonban így mindig ugyanaz marad -- 
még akkor is, ha a szerzõ néha elcsábul, hogy néhány új szót adjon hozzá, amit 1992-ben nem ismert, mint a 
\texttt{chads},
\texttt{stent},
\texttt{blogs},
\texttt{ditzy},
\texttt{phish},
\texttt{bling}, és esetleg 
\texttt{tetch}.
De nem, semmiképpen (\texttt{noway}). Az SGB bármelyik módosítására hosszú idõ kell az \texttt{ended}: \texttt{finis} óta.


\bigskip
{\quoteformat
A következõ szógyûjtemény tartalmazni fogja az összes jól ismert angol szót
\ldots amelyik használható a jó társaságban, és amelyik mutatóként szolgálhat. 
\ldots Szükség van ott egy gyorsíróra az új szavak felvételére.
\author LEWIS CARROLL\angolnevindex{CARROLL, LEWIS} \textsl{Doublets: A Word-Puzzle} (1879) \cite{Carroll1879}
\medskip
Ha létezik olyan ige, hogy ingerlékenykedni, akkor 
Mr. Lillywaite\angolnevindex{Lillywaite, Peregrine} ingerlékenykedett.
\author ROBERT BARNARD \angolnevindex{Barnard, Robert} Corpsein a Gilded Cage (1984) \cite{BARNARD1984}  
}
\bigskip
A személy nevek, mint a \texttt{Knuth}, nem számítanak szabályos szavaknak. 
Azonban \texttt{gauss} és \texttt{hardy} \texttt{érvényesek}, mert \idez{gauss} 
a mágneses indukció egysége, \idez{hardy} pedig angolul bátor. 
Tulajdonképpen az SGB szavak teljes egészében a szokásos kisbetûkbõl állnak;   
a lista nem tartalmaz kötõjellel ellátott szavakat, rövidítéseket, 
sem pedig olyan szavakat, amelyekhez szükség van ékezetre. 
Így mindegyik szót vektornak is tekinthetjük, amelyik öt komponenst 
tartalmaz a $[0\dts26)$ tartományból. Vektor értelemben a \texttt{yucca} és az \texttt{abuzz} 
szavak vannak a legtávolabb egymástól: A köztük lévõ {euklideszi távolság}\index{euklideszi távolság = Euclidean distance} 
$$\Vert(24,20,2,2,0)-(0,1,20,25,25)\Vert_2 = \sqrt{24^2+19^2+18^2+23^2+25^2}=\sqrt{2415}\koz.$$
A teljes {Stanford GráfBázis}\index{Stanford GráfBázis = Stanford GraphBase} az összes programjával és adathalmazával együtt 
könnyen letölthetõ a szerzõ honlapjáról (lásd \ref{kolofon}).\index{internet = Internet}
Az összes SGB szó listáját pedig még könnyebb megkapni, mert az ugyanezen a helyen az \idez{\texttt{sgb-words.txt}} fájlban van. 
Ez a fájl 5757 sort tartalmaz, soronként egy szót, kezdve a \idez{\texttt{which}} szóval, és befejezve a \idez{\texttt{pupal}} szóval.
A szavak alapértelmezés szerint a használati gyakoriságuknak\index{használati gyakoriság = frequency of usage} 
megfelelõ sorrendben jelennek meg; például az 1000, 2000, 3000, 4000, és 5000 rangú szavak rendre \texttt{ditch},
\texttt{galls},
\texttt{visas},
\texttt{faker}, és
\texttt{pismo}.
A \idez{\texttt{WORDS}$(n)$} jelölés ebben a fejezetben azt jelenti, 
hogy az összes szó az $n$ gyakoriságúig ebben a sorrendezésben.
\index{vördsz@\texttt{WORDS}$(n)$ = \texttt{WORDS}$(n)$}

Mellesleg az ötbetûs szavak sok {\it négybetûs szó} többes számát tartalmazzák, 
és meg kell jegyeznünk, hogy nem alkalmaztuk a viktoriánus stílus 
cenzúráját\index{cenzúra = censorship}. 
Az esetlegesen durva szavak el lettek távolítva 
a \textsl{The Official Scrabble}$^{\setbox0=\hbox{$\scriptstyle\bigcirc$}
     \rlap{\hbox to\wd0{\hss$\scriptscriptstyle\rm R$\hss}}\box0}\!$
\textsl{Players Dictionary}-ból, az SGB-bõl azonban nem. 
Egy lehetõség annak a biztosítására, hogy a 
szemantikailag nem megfelelõ 
szavak ne jelenjenek meg egy olyan tudományos cikkben, 
amelyik az SGB szólistáján alapszik, hogy 
leszûkítjük a választható szavak tartományát 
a \texttt{WORDS}$(n)$-re, ahol $n$ mondjuk 3000.

Az alábbiakban látható \ref{gyak70-26}--\ref{gyak70-37}. gyakorlatok bemelegítõként 
használhatók az SGB szavak kezdeti felderítésére, amelyeket  
ennek a fejezetnek a során számos különbözõ kombinatorikai összefüggésben fogunk látni.  
Ha például éppen a {lefedési}\index{lefedés = covering} problémán gondolkozunk,  
megfigyelhetjük azt is, hogy a \idez{\texttt{third} \texttt{flock}  \texttt{began} \texttt{jumps}} 
szavak az ábécé elsõ 21 betûjébõl 20-at lefednek. 
Öt szó azonban legfeljebb 24 különbözõ betût fed le, 
mint a \{\texttt{becks},
\texttt{fjord},
\texttt{glitz},
\texttt{nymph},
\texttt{squaw}\} szavak, 
ha nem folyamodunk egy ritka, nem SGB szóhoz, mint a \texttt{waqfs} (iszlám adományok), amelyik kombinálható a 
\{\texttt{gyved},
\texttt{bronx},
\texttt{chimp}, 
\texttt{klutz}\} 
szavakkal, így ezek 25-öt fednek le.

Egyszerû szavak a \texttt{WORDS}(400)-ból elegendõek ahhoz, hogy \textit{szó négyzetet}\index{szó négyzet = word square} 
készíthessünk: 
\begin{equation}
\vcenter{\baselineskip=10pt\tt\halign{#\cr
class\cr light\cr agree\cr sheep\cr steps\cr}}\enspace.
\label{(keplet-9)}
\end{equation}

El kell azonban mennünk majdnem \texttt{WORDS}(3000)-ig, hogy \textit{szó kockát}\index{szó kocka = wordcube} kapjunk, 
\begin{equation}
\def\\#1\\{\vcenter{\baselineskip=10pt\tt\halign{##\vphantom j\cr#1\cr}}}
\catcode`\:=\active \let:=\cr
\\types:yeast:pasta:ester:start\\ \quad
\\yeast:earth:armor:stove:three\\ \quad
\\pasta:armor:smoke:token:arena\\ \quad
\\ester:stove:token:event:rents\\ \quad
\\start:three:arena:rents:tease\\\enspace,\label{keplet70-10}
\end{equation}
amiben minden $5\times 5$-ös \idez{szelet} egy szó négyzet. A szimpla {táncoló mutatók}\index{táncoló mutatók = dancing links}  
algoritmus egyszerû kiterjesztésével (lásd a 7.2.2.2. alpontot) meg lehet mutatni körülbelül 390 milliárd mems számítás 
elvégzésével, hogy a \texttt{WORDS}(3000) csak három szimmetrikus szó kockát tartalmaz, 
mint amilyen (\ref{keplet70-10})-ben látható; a \ref{gyak70-36}. gyakorlat megmutatja a másik kettõt.
Meglepõ módon 83\,576 szimmetrikus kocka készíthetõ a teljes halmazból,  \texttt{WORDS}(5757)-bõl.


\medskip
\noindent \textbf{Szógráfok.}
Érdekes és fontos feladat az, hogy objektumokat sorokba, négyzetekbe, kockákba, 
és más minta szerint rendezzünk el; 
azonban a gyakorlati alkalmazásban másfajta kombinatorikai struktúrák
még {\it inkább\/} érdekesek és fontosak, mégpedig a {\it gráfok}\index{gráf = graph}. 
Emlékeztetünk a 2.3.4.1. alpontból arra, hogy egy gráf
pontok halmaza, amiket {\it csúcsoknak} hívunk, vonalak halmazával együtt, 
amiket {\it éleknek} nevezünk, és amik bizonyos csúcs párokat kötnek össze. 
A gráfok mindenütt ott vannak, és sok gyönyörû gráf algoritmust fedeztek fel, 
így természetesen a gráfok központi szerepet játszanak e fejezet számos alfejezetében.
Valójában a Stanford GráfBázisban elsõdlegesen gráfokról van szó, 
mint a neve is mutatja;
az SGB szavak pedig fõleg azért lettek összegyûjtve, mert 
érdekes és tanulságos gráfok meghatározására használhatóak. 
  
Carroll\angolnevindex{Carroll, Lewis} 1877 végén tûzte ki az utat, amikor kitalált egy játékot, amit szómutatóknak, vagy 
szópároknak\index{szópár = doublet} nevezett (lásd \cite{Gardner1996}).\angolnevindex{Gardner, Martin} 
Carroll ötlete, amely hamarosan meglehetõsen népszerû lett, az volt, hogy alakítsunk át egy szót egy másik szóvá 
egyszerre csupán egy betû megváltoztatásával:\index{mosoly = smile}\index{mosoly = $\smile$, \textit{lásd} smile}
\begin{equation}
\texttt{tears}\adj
\texttt{sears}\adj
\texttt{stars}\adj
\texttt{stare}\adj
\texttt{stale}\adj
\texttt{stile}\adj
\texttt{smile}\koz. 
\label{keplet70-11}
\end{equation}
% Carroll's solution was optimum, agreeing perfectly with the output of LADDERS
A legrövidebb ilyen átalakítás a legrövidebb \textit{út} egy gráfban, ahol a gráf csúcsai angol szavak, élei azokat a 
szó párokat\index{legrövidebb út = shortest path}\index{gráf = graph!legrövidebb út két szó között = 
shortest path between two words} kötik össze, amelyek \idez{Hamming-távolsága} 1\index{Hamming-távolság = Hamming distance} 
(ami azt jelenti, hogy éppen egy helyen különböznek egymástól).

Ha az SGB szavakra szorítkozunk, akkor Carroll szabályai a Stanford GráfBázis\index{Stanford GráfBázis = Stanford GraphBase}
egy gráfját eredményezik, amelyiknek a hivatalos neve $\textit{words}(5757,0,0,0)$.
Az SGB-vel meghatározott mindegyik gráfnak egyedi azonosítója van,  
amit az õ \textit{id}\index{id (azonosító) = id (identifyer)}-jének hívunk, 
és az SGB szavakból Carroll módján származó gráfok $\textit{words}(n,l,t,s)$ alakú \textit{id}-del vannak azonosítva. Itt $n$ 
a csúcsok számát jelenti, $l$ vagy 0, vagy súlyoknak egy listája, amit a szókincs különbözõ fajtáinak a megjelölésére használunk;   
$t$ egy küszöbszám arra, hogy az alacsony súlyú szavak elutasíthatóak legyenek; $s$ pedig a mag??\index{gráf = graph!mag?? = seed} 
néhány pszeudovéletlen\index{pszeudovéletlen szám = pseudorandom number} szám számára, amire szükség lehet az azonos súlyú szavak 
közötti összeköttetés megszakításához.?? Nincs szükségünk az összes részletre, de néhány példa megvilágítja a fõ gondolatot:  
\begin{enumerate}
\breathe
\item[$\bullet$] ${\it words}(n,0,0,0)$ pontosan az a gráf, amelyet akkor kapunk, 
ha {Carroll}\angolnevindex{Carroll, Lewis} eszméjét a \texttt{WORDS}$(n)$-re alkalmazzuk $1\le n\le5757$ esetén.
\breathe
\item[$\bullet$] ${\it words}(1000,\{0,0,0,0,0,0,0,0,0\},0,s)$ tartalmaz 1000 véletlenszerûen választott 
SGB szót, $s$ különbözõ értékeire rendszerint különbözõt.  
\breathe
\item[$\bullet$] ${\it words}(766,\{0,0,0,0,0,0,0,1,0\},1,0)$ tartalmazza az összes ötbetûs szót, amelyik 
megjelenik e sorok szerzõjének  
\angolnevindex{Knuth@\string\Knuth}{\TeX-rõl} 
%\index{teh@\TeX = \TeX}
és {\MF-ról}\index{mf@\MF = \MF}
írt könyveiben.
\end{enumerate}
\breathe\noindent
Az utóbbi gráfban csak 766 szó van, így nem tudunk nagyon sok (\ref{keplet70-11})-belihez hasonló hosszú utat kialakítani, ámbár 
\begin{equation}
%\displaylines{\hskip\parindent
\texttt{basic}\adj
\texttt{basis}\adj
\texttt{bases}\adj
\texttt{based}\adj
%\hfill\\
%\hfill{}\adj
\texttt{baked}\adj
\texttt{naked}\adj
\texttt{named}\adj
\texttt{names}\adj
\texttt{games}
%\qquad}
\label{keplet70-12}
\end{equation}
egy figyelemreméltó példa. 

Természetesen sok más mód is van egy gráf éleinek a definiálására, ha a csúcsok az ötbetûs szavakat reprezentálják. 
Kívánhatjuk például, hogy az euklideszi távolság\index{euklideszi távolság = Euclidean distance} 
legyen kicsi a {Hamming-távolság}\index{Hamming-távolság = Hamming distance} helyett. Vagy kijelenthetjük, hogy két szó akkor 
legyen szomszédos, ha van közös négy betûs részszavuk\index{részszó = subword}; ez a stratégia lényegesen kibõvítené a gráfot, 
lehetõvé téve a \texttt{káosz} számára, hogy \texttt{békét} teremjen, jóllehet a \TeX-hez\index{TeX = TeX}
%\index{teh@\TeX = \TeX} 
kapcsolódó 766 szóra korlátozva:

\begin{equation}\label{keplet70-13}
\begin{split}
\texttt{chaos}\adj
\texttt{chose}&\adj
\texttt{whose}\adj
\texttt{whole}\adj
\texttt{holes}\adj
\texttt{hopes}\adj
\texttt{copes}\adj
\texttt{scope}\\
&\adj\texttt{score}\adj
\texttt{store}\adj
\texttt{stare}\adj
\texttt{spare}\adj
\texttt{space}\adj
\texttt{paces}\adj
\texttt{peace}\koz.
\end{split}
\end{equation}
(Ebben az elõírásban elhagyunk egy betût, aztán beszúrunk egy másikat, lehetõleg eltérõ helyen.) Vagy választhatunk egy 
ezektõl teljesen különbözõ stratégiát, mint azt, hogy két szóvektor, $a_1a_2a_3a_4a_5$ és $b_1b_2b_3b_4b_5$ közé akkor és 
csak akkor teszünk élt, ha a skalár szorzatuk\index{vektorok skalár szorzata = dot product of vectors}, 
$a_1b_1+a_2b_2+a_3b_3+a_4b_4+a_5b_5$ valamilyen $m$ paraméternek a többszöröse. 
A gráf algoritmusok különbözõ fajtájú adatokkal boldogulnak.

Az SGB szavak elvezetnek  az \textit{irányított} gráfok\index{irányított gráf = directed graph}
\index{gráf = graph!irányított gráf = directed graph} érdekes családjához is, ha 
$\{a_2,a_3,a_4,a_5\}\subseteq\{b_1,b_2,b_3,b_4,b_5\}$ (mint multihalmazok) esetén 
$a_1a_2a_3a_4a_5\to b_1b_2b_3b_4b_5$-t írunk. (Távolítsuk el az elsõ betût, szúrjunk be egy másikat, és rendezzük át 
õket.) Ezzel a szabállyal például átalakíthatjuk a \texttt{words} szót a \texttt{graph} szóvá hat hosszú legrövidebb irányított úton:   
\begin{equation}
\texttt{words}\to
  \texttt{dross}\to
  \texttt{soars}\to
  \texttt{orcas}\to
  \texttt{crash}\to
  \texttt{sharp}\to
  \texttt{graph}\koz.\label{keplet70-14}
\end{equation}

{\quoteformat
\index{Taylor-sor = Taylor series} 
A gyakorlat Taylor-sorában az elsõ tag az elmélet. 
\author THOMAS M. COVER \textsl{1990 Shannon lecture} (1992)\angolnevindex{Cover, Thomas Merrill} \cite{Cover1992}
\bigskip
A gráfelméletben jelenleg használt terminológia rendszerek száma jó közelítéssel megegyezik a 
gráfelméleti szakemberek számával.
\author RICHARD P. STANLEY\angolnevindex{Stanley, Richard Peter} \textsl{Enumerative Combinatorics} (1986) \cite{Stanley1986}
}

\bigskip
\medskip
\noindent \textbf{Gráfelmélet: az alapok.}\index{bevezetés a gráfelméletbe  = graph theory, introduction to}
Egy $G$ gráf egy $V$ csúcshalmazból és egy $E$ élhalmazból áll, amit különbözõ csúcsokból képzett párok alkotnak.
Feltesszük, hogy $V$ és~$E$ {\it véges\/} halmazok, hacsak nem írjuk elõ másképp. 
Azt írjuk, hogy $u\adj v$ ha $u$ és~$v$ csúcsok, és $\{u,v\}\in E$, valamint $u\not\adj v$-t írunk, ha $u$ és $v$ csúcsok, 
de $\{u,v\}\notin E$. Ha csúcsokra fennáll $u\adj v$, akkor azt mondjuk, hogy 
\idez{szomszédok}\index{gráf = graph!szomszéd = neighbor}, és azt is mondjuk rájuk, hogy 
\idez{szomszédosak}\index{gráf = graph!szomszédos = adjacent} $G$-ben.
Ennek a definíciónak az egyik következménye az, hogy $u\adj v$  akkor 
és csak akkor, ha $v\adj u$. Másik következmény az, hogy $v\not\adj v$ 
minden $v\in V$ esetén, vagyis csúcs nem szomszédos önmagával. (Fogunk azonban 
multigráfokról\index{gráf = graph!multigráf = multigraph} tárgyalni, amelyekben megengedjük, 
hogy egy csúcsot egy hurok\index{gráf = graph!hurok gráfban = loop in a graph} önmagával kössön össze.)
 
A $G'=(V',E')$ {\it{részgráfja}\/}\index{gráf = graph!részgráf = subgraph} a $G=(V,E)$ gráfnak, ha
$V'\subseteq V$ és $E'\subseteq E$. \textit{Feszítõ}\index{gráf = graph!feszítõ részgráf = spanning subgraph} részgráfja 
$G$-nek, ha ráadásul még $V'=V$. És \textit{indukált}\index{gráf = graph!indukált részgráf = induced subgraph} 
részgráfja $G$-nek, ha $E'$ a lehetséges legtöbb élt tartalmazza, amennyiben $V'$ a csúcsok adott részhalmaza. 
Más szóval ha $V'\subseteq V$, a $V'$ által feszített $G'=(V',E')$ részgráfja $G=(V,E)$-nek,  ahol
\begin{equation}
E'\;=\;\bigl\{\,\{u,v\}\bigm\vert
 \hbox{$u\in V'$, $v\in V'$, és $\{u,v\}\in E$}\,\bigr\}\koz.\label{keplet70-15}
\end{equation}
Ezt a $G'$ részgráfot $G\rest V'$ jelöli, és gyakran hívjuk úgy, hogy \idez{$G$ leszûkítése $V'$-re}
\index{gráf = graph!gráf leszûkítése = restriction of a graph}.
\index{gráf = graph!gé@$G$ leszûkítése $V'$-re: $G\rest V'$ = $G\rest V'$}
\index{gráf = graph!gé@$G$ mínusz a $v$ csúcs: $G\setminus v$ = $G\setminus v$}
Abban a gyakori esetben, ha $V'=V\setminus\{v\}$, egyszerûen azt írjuk, hogy 
$G\setminus v$ (\idez{$G$ mínusz a $v$ csúcs}) mintegy a $G\rest(V\setminus\{v\})$ rövidítéseként.
Hasonlóképp, ha $e\in E$, akkor a $G'=(V,E\setminus\{e\})$ részgráf 
jelölésére, amit egy él eltávolításával kapunk csúcsé helyett, a {$G\setminus e$}
\index{gráf = graph!gé@$G$ mínusz az $e$ él: $G\setminus e$ = $G\setminus e$} jelölést alkalmazzuk.
Megjegyezzük, hogy az összes korábban leírt, ${\it words}(n,l,t,s)$-ként ismert SGB gráf   
feszítõ részgráfja a  ${\it words}(5757,0,0,0)$ fõ gráfnak;
ezekben a gráfokban csak a szókincs változik, nem pedig a szomszédsági szabályok. 

Egy $n$ csúcsú és $e$ élû gráfra azt mondjuk, hogy 
\textit{n-ed rendû}\index{nedrendû@$n$-ed rendû gráf = order $n$ graph}
és \textit{e méretû}\index{gráf = graph!e@$e$ méretû gráf = size~$e$ graph}. A legegyszerûbb és legfontosabb $n$-ed rendû gráfok 
a $K_n$\index{káen@$K_n$ = $K_n$} \textit{teljes gráf}\index{gráf = graph!teljes gráf = complete graph}, 
a $P_n$\index{gráf = graph!péen@$P_n$ = $P_n$} \textit{út}\index{gráf = graph!út gráfban = path in a graph}, és a  
$C_n$\index{gráf = graph!céen@$C_n$ = $C_n$} \textit{kör}\index{gráf = graph!kör gráfban = cycle in a graph}. 
Tegyük fel, hogy a csúcsok halmaza $V=\{1,2,\ldots,n\}$. Ekkor 
\begin{enumerate}
\item[$\bullet$] $K_n$-nek ${n\choose2}=\half n(n-1)$ éle van, $u\adj v$, ha 
$1\le u<v\le n$; minden $n$ csúcsú gráf feszítõ részgráfja $K_n$-nek.
\item[$\bullet$] $P_n$-nek $n-1$ éle van, $v\adj(v{+}1)$, amikor $1\le v<n$ és  
$n\ge 1$; ez egy $n{-}1$ hosszú út 1-tõl $n$-ig.
\item[$\bullet$] $C_n$-nek $n$ éle van,  $v\adj((v\mod n){+}1)$, ha $1\le v\le n$;
ez csak akkor gráf, ha $n=0$ vagy $n\ge 3$ (azonban $C_1$ és $C_2$ {multigráfok}\index{gráf = graph!multigráf = multigraph}).
\end{enumerate}
\smallskip\noindent
A $K_n$, $P_n$, és $C_n$ gráfokat valójában a $\{0,1,\ldots,n{-}1\}$ csúcsokon, vagy \textit{bármelyik} $n$-elemû $V$ 
halmazon definiálhattuk volna  az $\{1,2,\ldots,n\}$ halmaz helyett, mert két gráf, amelyik csak 
csúcsai nevében különbözik, éleinek struktúrájában azonban nem, kombinatorikailag ekvivalens. 

Formálisan azt mondjuk, hogy a $G=(V,E)$ és a $G'=(V',E')$ gráfok 
{\it izomorfak,\/}\index{gráf = graph!izomorf gráfok = isomorphic graphs}
ha van egy $\varphi$ egy-egy értelmû megfeleltetés 
$V$-rõl $V'$-re úgy hogy $u\adj v$ akkor és csak akkor áll fenn $G$-ben, ha $\varphi(u)\adj\varphi(v)$
fennáll $G'$-ben. A $G\cong G'$ jelölés
%\index{G ekvivalens G'-vel@$G\cong G'$ = $G\cong G'$}     
%\index{ekvivalensek@$G \cong G'$ = $G \cong G'$}    
gyakran használatos arra, hogy $G$ és $G'$ izomorfak; de sokszor leszünk kevésbé precízek, és az izomorf 
\index{gráf = graph!izomorf gráfok = isomorphic graphs}  gráfokat úgy kezeljük, mint azonosakat, és alkalmanként 
$G=G'$-t írunk még ha $G$ és $G'$ csúcshalmaza szigorúan véve nem is azonos. 

Kis gráfokat egyszerûen definiálhatunk az {ábrájuk}\index{ábra = diagram} megrajzolásával, 
amiben a csúcsok kicsi körök, az élek pedig vonalak közöttük. A \ref{abra70-2}. ábra több fontos példát mutat, amelyek 
tulajdonságait késõbb fogjuk tanulmányozni. A Petersen-gráf\index{gráf = graph!Petersen-gráf = Petersen graph} 
\ref{abra70-2}.(e)-ben Petersenrõl\angolnevindex{Petersen, Julius Peter Christian}, egy egykori  
gráfelméleti szakemberrõl kapta a nevét, aki egy kézenfekvõ feltevés  
megdöntésére használta \cite{Petersen1902}; valójában ez egy nevezetes alakzat, amelyik ellenpéldaként szolgál   
számos derûlátó sejtésre arról, hogy mi lehet igaz gráfokra általában. 
A \ref{abra70-2}.(f) ábrán látható Chvátal-gráfot\index{gráf = graph!Chvátal-gráf = Chvátal graph}   
Chvátal\angolnevindex{Chvátal, Václav} vezette be \cite{Chvatal1970}.  

\begin{figure}
$$\def\\#1#2#3#4{\vcenter to1.07in{\halign{\hfil##\hfil\cr
                              \strut(#1)\cr
                             \noalign{\vskip3pt\vfil\vskip#3pt}
                              \epsfbox{\figdir/ch7a.22#2}\cr
                             \noalign{\vfil\vskip-3pt}
                              \strut#4\cr}}}
\small{
\\a1{-2}{$P_5$}\qquad
\\b2{-2}{$C_5$}\qquad
\\c0{-2}{$K_5$}\qquad
\\d30{3-kocka}\qquad
\\e4{-3}{Petersen-gráf}\qquad
\\f51{Chvátal-gráf}}$$
\caption{Hat példa gráf, amelyek rendre $(5,5,5,8,10,12)$ csúcsot és $(4,5,10,12,15,24)$ élt tartalmaznak.\label{abra70-2}}
\end{figure}

Egy gráf ábrában lehetséges, hogy a vonalak olyan pontokban keresztezik egymást, 
amelyek nem csúcsok. Például \ref{abra70-2}.(f) középsõ pontja {\it nem\/} csúcsa Chvátal gráfjának. 
Egy gráfot {\it{síkba rajzolhatónak}\index{gráf = graph!síkba rajzolható gráf = planar graph}\/} nevezünk
ha van keresztezés nélküli lerajzolása. Világos, hogy $P_n$ és $C_n$ mindig síkba rajzolhatóak;  
\ref{abra70-2}.(d) mutatja, hogy a 3-kocka is síkba rajzolható. 
Azonban $K_5$-nek túl sok éle van ahhoz, hogy síkba rajzolható legyen (lásd a \ref{gyak70-46}. gyakorlatot) 

Egy csúcs {\it{foka}\index{gráf = graph!fok = degree}\/} a szomszédainak a száma.
\index{gráf = graph!fok = valency, \textit{lásd} degree}
Ha minden csúcsnak ugyanakkora a foka, akkor a gráfot 
{\it{regulárisnak}}\index{gráf = graph!reguláris gráf= regular graph} nevezzük.
A \ref{abra70-2}. ábrán például $P_5$ irreguláris, mert van két 
1-fokú csúcsa és három 2-fokú. A többi öt gráf azonban reguláris, 
rendre a $(2,4,3,3,4)$ fokszámokkal. Egy 3-fokú reguláris gráfot 
gyakran \idez{kubikus???-nak}\index{gráf = graph!kubik@kubikus = cubic}, 
vagy \idez{trivalens-nek???}\index{gráf = graph!trivalens = trivalent} hívnak.

Egy adott gráf megrajzolására számos mód van, néhány áttekinthetõbb a többinél. Például a (\ref{keplet70-16}) ábrán látható 
hat diagram mindegyike izomorf a 3-kockával\index{gráf = graph!háromkocka@3-kocka gráf = 3-cube graph}, a \ref{abra70-2}.(d) ábra    
Chvátal-gráfjának a \ref{abra70-2}.(d) ábrán látható  elrendezését Bondy\angolnevindex{Bondy, John Adrian} fedezte fel sok évvel 
azután, hogy Chvátal tanulmánya megjelent, miáltal váratlan szimmetriák tárultak fel. 
\begin{equation}
\def\\#1{\epsfbox{\figdir/v4a.14#1}}
\def\quad{\hskip1.3em}
\\0\quad
\\1\quad
\\2\quad
\\3\quad
\\4\quad
\\5\koz.\label{keplet70-16}
\end{equation}

Egy gráf szimmetriái, amiket az \textit{automorfizmusainak} is hívunk,
\index{szimmetria = symmetry}\index{automorfizmus = automorphism} 
a csúcsainak olyan permutációi, amelyek megõrzik a szomszédságot. 
Más szóval a $\varphi$ permutáció $G$ automorfizmusa, ha 
\vadjust{\goodbreak}$\varphi(u)\adj\varphi(v)$ teljesül, valahányszor 
$u\adj v$ fennáll $G$-ben. Egy a \ref{abra70-2}.(f) ábrán láthatóhoz   
hasonlóan jól megválasztott lerajzolás képes felfedni a rejtõzködõ 
szimmetriát, egy ábra azonban nem mindig tudja megmutatni 
az összes létezõ szimmetriát. Például a kockának 48 automorfizmusa van, a Petersen-gráfnak 
pedig 120. A 7.2.3. pontban tanulmányozni fogunk az 
izomorfizmussal és az automorfizmussal foglalkozó algoritmusokat.  
A szimmetriák hasznosíthatóak arra, hogy elkerülhessünk 
szükségtelen számításokat, egy algoritmust 
akár $k$-szor gyorsabbá téve, ha olyan gráffal dolgozik, amelyiknek $k$ automorfizmusa van. 

Azok a gráfok, amelyek a valódi világban adódnak, rendszerint különböznek a \ref{abra70-2}. ábrabeli   
tulajdonképpeni matematikai gráfoktól. Itt van például a (\ref{keplet70-17}) ábrán egy ismert gráf, amelyiknek egyáltalán  
nincs szimmetriája, jóllehet megvan az az elõnye, hogy síkba rajzolható\index{gráf = graph!síkba rajzolható gráf = planar graph}.
\begin{equation}\label{keplet70-17}
\epsfbox{\figdir/v4a.1500}\koz.
\end{equation}
Az {USA államainak a szomszédságát}\index{USA államainak a szomszédsága = contiguous United States of America}
reprezentálja és késõbb több példában fogjuk használni. Ennek az ábrának a 49 csúcsát az egyszerûség kedvéért a kétbetûs  
postai kódokkal\index{postai kód = postal codes} indexeltük,  ahelyett, hogy üres körökre redukáltuk volna. 

\medskip
\noindent \textbf{Utak és körök.}
Egy gráf {feszítõ}\index{gráf = graph!feszítõ út = spanning path} útját 
\textit{Hamilton-útnak}\index{gráf = graph!Hamilton-út gráfban = Hamiltonian path in a graph} nevezzük,
egy feszítõ kört pedig \textit{Hamilton-körnek}\index{gráf = graph!Hamilton-kör gráfban = Hamiltonian cycle of a graph}, 
mert Hamilton\angolnevindex{Hamilton, William Rowan} kitalált egy rejtvényt 1859-ben, amelyiknek az volt a célja, 
hogy ilyen utakat és köröket találjanak a dodekaéder\index{dodekaéder = dodecahedron} élein.
Kirkman\angolnevindex{Kirkman, Thomas Penyngton (1806-1895)} ettõl függetlenül tanulmányozta a problémát poliéderekre 
általában (lásd \cite{Kirkman1858} és  \cite[2. fejezet]{Biggs1998}). A feszítõ út vagy feszítõ kör keresésének feladata 
azonban sokkal régebbi -- valóban, jogosan tekinthetjük a legrégibbnek az összes kombinatorikai probléma közül, 
mert a huszár\index{huszár (sakktáblán) = knight} sakktáblán\index{sakktábla = chessboard} megtett útjainak és mozgásának   
a története visszanyúlik a kilencedik századi Indiáig (lásd a 7.3.3. pontban). Egy gráfot 
\textit{Hamilton-gráfnak}\index{gráf = graph!Hamilton-gráf = Hamiltonian graph} nevezünk, ha van Hamilton-köre. 
(A Petersen-gráf\index{gráf = graph!Petersen-gráf = Petersen graph} egyébként a legkisebb 3-reguláris gráf, 
amelyik sem nem síkba rajzolható, sem nem Hamilton-gráf \cite{Polignac1899}. 
\angolnevindex{Polignac, Camille Armand Jules Marie de}

A gráf \textit{kerülete}\index{gráf = graph!gráf kerülete = girth of a graph} a legrövidebb körének a hossza;   
a kerület végtelen, ha a gráf {aciklikus}\index{gráf = graph!aciklikus gráf = acyclic graph} 
(nem tartalmaz kört). Például a \ref{abra70-2}. ábra hat gráfjának kerülete rendre $(\infty,5,3,4,5,4)$.  
Nem nehéz bebizonyítani, hogy egy olyan gráfnak, amelyiknek a minimális fokszáma $k$ és 5 a kerülete, legalább $k^2+1$ 
csúcsa kell legyen. További vizsgálat megmutatja, hogy ez a minimális érték csak $k=2$ ($C_5$),
$k=3$ (Petersen), $k=7$, vagy esetleg $k=57$ esetén valósítható meg. (Lásd a \ref{gyak70-63}--\ref{gyak70-65}. gyakorlatokat.)

Két csúcs, $u$ és $v$ között a $d(u,v)$ {\it{távolság}\/}\index{távolság = distance}\index{gráf = graph!legrövidebb út gráfban = 
shortest path in a graph} a gráfban az $u$-ból $v$-be menõ utak minimális hossza; ez végtelen, ha nincs ilyen út. Nyilvánvalóan 
$d(v,v)=0$ és $d(u,v)=d(v,u)$. Fennáll a {háromszög egyenlõtlenség}\index{háromszög egyenlõtlenség = triangle inequality} is: 
\begin{equation}
d(u,v)+d(v,w)\;\ge\; d(u,w)\koz.\label{keplet70-18}
\end{equation}
Ha $d(u,v)=p,\ $ $d(v,w)=q,\ $ $p<\infty $ és $q<\infty$, akkor
\begin{equation}
u=u_0\adj u_1\adj\cdots\adj u_p=v\quad\hbox{és}\quad
  v=v_0\adj v_1\adj\cdots\adj v_q=w\koz,\label{keplet70-19}
\end{equation} 
utak, és meg tudjuk a legkisebb $r$ indexet találni, amire $u_r=v_s$ valamilyen $s$ esetén. 
Ekkor 
\begin{equation}
u_0\adj u_1\adj\cdots\adj u_{r-1}\adj v_s\adj v_{s+1}\adj\cdots\adj v_q
\label{keplet70-20}
\end{equation}
egy $u$-tól $w$-ig tartó $\le p+q$ hosszú út.

Egy gráf {\it{átmérõje}\/}\index{gráf = graph!gráf átmérõje = diameter of a graph} $d(u,v)$ maximuma  az összes $u$ és $v$ 
csúcsra nézve. A gráf {\it{összefüggõ}\/}\index{gráf = graph!összefüggõ gráf = connected graph}, ha átmérõje véges. 
Egy gráf csúcsai mindig szétoszthatóak összefüggõ \textit{komponensekbe}\index{gráf = graph!gráf komponense = component of a ghraph}, 
ahol két $u$ és $v$ csúcs akkor és csak akkor tartozik ugyanabba a komponensbe, ha $d(u,v)<\infty$. 

A ${\it words}(5757,0,0,0)$ gráfban például $d(\texttt{tears},\texttt{smile})=6$,  
\index{ötbetûs szavak = five-letter words} mert (\ref{keplet70-11}) legrövidebb út \texttt{tears}-tõl \texttt{smile}-ig.
\index{mosoly = smile} Hasonlóan $d(\texttt{tears},\texttt{happy})=6$, 
$d(\texttt{smile},\texttt{happy})=10$ és $d(\texttt{world},$ \linebreak
\noindent $\texttt{court})=6$. Azonban $d(\texttt{world},\texttt{happy})=\infty$; a gráf nem összefüggõ.
Valóban, tartalmaz az \texttt{aloof}-hoz hasonlóan 671 olyan szót, amelyiknek nincs szomszédja, és mindegyik saját magával 
1-rendû összefüggõ komponenst képez. Szó párok, mint az $\texttt{alpha}\adj\texttt{aloha}$, $\texttt{droid}\adj\texttt{druid}$, 
és az $\texttt{opium}\adj\texttt{odium}$ a többi 103 2-rendû komponenshez tartoznak. Néhány 3-rendû komponens út, mint a 
$\texttt{chain}\adj\texttt{chair}\adj\texttt{choir}$; mások, mint a $\{\texttt{getup},\texttt{letup},\texttt{setup}\}$ pedig körök. 
Néhány kisebb komponens van még, amilyen a  
\begin{equation}
\texttt{login}\adj\texttt{logic}\adj\texttt{yogic}\adj\texttt{yogis}\adj\texttt{yogas}\adj\texttt{togas}
\label{keplet70-21}
\end{equation}
furcsa út, amelyik szavainak nincs több szomszédja. Az összes ötbetûs szó hatalmas többsége azonban egy 4493-rendû 
{óriás komponenshez}\index{gráf = graph!gráf óriás komponense = giant component of a graph} tartozik. 
Ha ön el tud menni két lépésre egy adott szótól, annak az esélye, hogy 
az ön szava mindennel össze van kötve az óriás komponensben, nagyobb, mint 15 az 1-hez. 

Hasonlóan a ${\it words}(n,0,0,0)$ gráf óriás komponenseinek a rendje  
$(3825,2986,2056,\allowbreak 1198,224)$, ha sorra $n=(5000,4000,3000,2000,1000)$. 
Ha azonban $n$ kicsi, nincs elég él sok kapcsolat létesítéséhez. 
Például ${\it words}(500,0,0,0)$-nek 327 különbözõ komponense van, semelyik sem 15, vagy nagyobb rendû.

A távolság-fogalmat ki lehet terjeszteni $d(v_1,v_2,\ldots,v_k)$-ra  bármely $k$ érték esetén, ami az élek minimális számát jelenti 
abban az összefüggõ részgráfban, amelyik tartalmazza a $\{v_1,v_2,\ldots,v_k\}$ csúcsokat.
Például, $d(\texttt{blood},\texttt{sweat},\texttt{tears})$ 15-nek bizonyul, mert a 
\begin{equation}
\postdisplaypenalty=10000
\def\\{\noalign{\vskip-2pt}}
\advance\abovedisplayskip3pt
\advance\belowdisplayskip5pt\vcenter{\halign{#&&\hfil${}#$\hfil\cr
\texttt{blood}&\adj\texttt{brood}&\adj\texttt{broad}&\adj\texttt{bread}&\adj\texttt{tread}
   &\adj\texttt{treed}&\adj\texttt{tweed}\cr
\\&&&&&\phantom{\adj}\ \enspace\vert&\phantom{\adj}\ \enspace\vert\cr
\\\texttt{tears}&\adj\texttt{teams}&\adj\texttt{trams}&\adj\texttt{trims}&\adj\texttt{tries}
   &\adj\texttt{trees}&\hfill\texttt{tweet}\cr
\\&&&&&&\phantom{\adj}\ \enspace\vert\cr
\\&&&&&\hfill\texttt{sweat}&\adj\texttt{sweet}\cr}}
\label{keplet70-22}
\end{equation}
részgráf \index{távolság = distance!általánosított távolság = generalized distance} 
15 élû, és nincs megfelelõ 14\footnote{Vagy kevesebb. \textit{A fordító.}} élû részgráf.

Említettük a 2.3.4.1. alpontban, hogy a legkevesebb élû összefüggõ gráfot 
\textit{szabad fának}\index{gráf = graph!szabad fa = free tree} 
hívjuk. Az a részgráf, amelyik a $d(v_1,\ldots,v_k)$ általánosított távolságnak 
megfelel, mindig szabad fa. Félrevezetõ módon hívják \textit{Steiner-fának},\index{gráf = graph!Steiner-fa = Steiner tree} 
mert Steiner\angolnevindex{Steiner, Jacob (1796--1863)} egyszer említette a $k=3$ esetet a $\{v_1,v_2,v_3\}$ 
pontokra az euklideszi síkban\index{euklideszi sík = Euclidean plane} \cite{Steiner1835}. Heinen\angolnevindex{Heinen, Franz} 
oldotta meg ezt a problémát \cite{Heinen1834}; Gauss\angolnevindex{Gauss, Carl Friedrich} kiterjesztette a vizsgálatot 
$k=4$-re Schumacherhez\angolnevindex{Schumacher, Heinrich Christian (1780--1850)} írt levelében (1836. márc. 21.). 

\medskip
\noindent \textbf{Színezés}.\index{színezés = coloring} Egy gráfot 
{\it{$k$-részesnek}\/}\index{gráf = graph!kárészes@$k$-részes gráf= $k$-partite graph} vagy 
{\it{$k$-színezhetõnek}\/}\index{gráf = graph!kászínezhetõ@$k$-színezhetõ gráf = $k$-colorable graph} 
nevezünk, ha csúcsai $k$ vagy kevesebb részre oszthatók szét úgy, hogy 
minden él végpontjai különbözõ részhez tartozzanak, -- vagy ami ezzel ekvivalens, ha ki lehet a csúcsokat legfeljebb 
$k$ különbözõ színnel színezni úgy, hogy soha ne tartozzon ugyanaz a szín 
két szomszédos csúcshoz. A híres négyszín tétel\index{négyszín tétel = Four Color Theorem}, 
amit Guthrie\angolnevindex{Guthrie, Francis} sejtett meg 1852-ben, és 
végül masszív számítógépes segítséggel Appel\angolnevindex{Appel, Kenneth Ira}, 
Haken\angolnevindex{Haken, Wolfgang}, és Koch\angolnevindex{Koch, John Allen} \cite{Appel1977}   
bizonyította be, azt állítja, hogy  {\sl minden síkba rajzolható\index{gráf = graph!síkba rajzolható gráf = planar graph} 
gráf 4-színezhetõ}.\index{gráf = graph!négy@4-színezhetõ gráf = 4-colorable graph} 
Egyszerû bizonyítás nem ismert, de speciális esetek, mint a  
(\ref{keplet70-17}), kiszínezhetõk ránézésre (lásd a \ref{gyak70-45}. gyakorlatot); 
és egy síkba rajzolható gráf 4-színezéséhez általában elegendõ $O(n^2)$ lépés \cite{Robertson1996}.  
\angolnevindex{Robertson, George Neil}\angolnevindex{Sanders, Daniel Preston}
\angolnevindex{Seymour, Paul Douglas}\angolnevindex{Thomas, Robin}

A 2-színezhetõ gráfok különösen fontosak a gyakorlatban. 
A 2 részes gráfokat általában \textit{kétrészesnek}\index{gráf = graph!kétrészes gráf = bipartite graph}, 
vagy egyszerûen \idez{bigráfnak}\index{gráf = graph!bigráf = bigraph} hívjuk; 
egy ilyen gráf minden élének egy végpontja van mindkét részben. 

\smallskip
\noindent
\textbf{B tétel.} {\sl Egy gráf akkor és csak akkor kétrészes, ha nem tartalmaz páratlan hosszúságú kört.}
\proof. (Lásd \cite{Konig1916}.) \angolnevindex{Kõnig Dénes (1884--1944)} Egy $k$ részes gráf mindegyik 
részgráfja\index{gráf = graph!részgráf = subgraph} $k$ részes. Így a $C_n$ kör csak akkor lehet egy kétrészes gráf 
részgráfja, ha $C_n$ maga is bigráf, ekkor pedig $n$-nek párosnak kell lennie.  

Fordítva, ha egy gráf nem tartalmaz páratlan kört, kiszínezhetjük a csúcsait két színnel, a $\{0,1\}$ színekkel a 
következõ eljárás végrehajtásával: Kezdetben mindegyik csúcs színezetlen. Ha a színezett csúcsok minden szomszédja színezett már, 
válasszunk egy színezetlen $w$ csúcsot, és színezzük 0-val. Egyébként válasszunk egy színezett $u$ csúcsot, amelyiknek van 
egy színezetlen $v$ szomszédja, és rendeljük $v$-hez a másik színt. A \ref{gyak70-48}. gyakorlat bebizonyítja, hogy végül érvényes 
2-színezést\index{két@2-színezés = 2-coloring} kapunk. \quad\slug

\smallbreak
A {\it{teljes kétrészes gráf}\/}\index{gráf = graph!teljes kétrészes gráf = complete bipartite graph},  
$K_{m,n}$ a legnagyobb kétrészes gráf, amelyiknek a csúcsai $m$ és $n$ méretû részekbõl állnak. 
Az $\{1,2,\ldots,m{+}n\}$ csúcsokon úgy definiálhatjuk, hogy $u\adj v$ mindahányszor $1\le u\le m<v\le m+n$.
Más szóval $K_{m,n}$-nek $mn$ éle van,  amelyekhez minden lehetséges módon 
az egyik csúcsot az elsõ részben, a másikat a második részben választjuk. 
Hasonlóan a \textit{teljes $k$-részes gráf}\index{gráf = graph!teljes $k$-részes gráf = complete $k$-partite graph} 
$K_{n_1,\ldots,n_k}$  $N=n_1+\cdots+n_k$ csúcsból áll, amelyek $\{n_1,\ldots,n_k\}$ méretû részekbe oszlanak szét, 
és bármelyik két olyan csúcs között van él, amelyek nem tartoznak ugyanahhoz a részhez. 
Itt van néhány példa, ha $N=6$:
\begin{equation}\label{keplet70-23}
\begin{tabular}{ccc}
\epsfbox{\figdir/v4a.1601} \ ; \quad  & \quad  \epsfbox{\figdir/v4a.1602} \quad $\cong$ \quad \epsfbox{\figdir/v4a.1603} \ ; & 
\ ; \quad \quad
\epsfbox{\figdir/v4a.1604} \quad $\cong$ \quad \epsfbox{\figdir/v4a.1605} \koz .\\
$K_{1,5}$ & $K_{3,3}$ & $K_{2,2,2}$
\end{tabular}
\end{equation}
\noindent Vegyük észre, hogy $K_{1,n}$ szabad fa\index{gráf = graph!szabad fa = free tree}; 
népszerû nevén $n+1$-ed rendû \textit{csillaggráf}\index{gráf = graph!csillaggráf = star graph}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%         GYAKORLATOK  ÉS  MEGOLDÁSOK
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\small
\vspace{8mm}
\setcounter{gyakcounter}{0}
\textbf{GYAKORLATOK}\small
\vspace{2mm}
\begin{gyak}
%%% 1
\ujgyak\label{gyak70-1} \sz{25}
Tegyük fel, hogy $n=4m-1$. Készítsük el az $\{1,1,\ldots,n,n\}$ számokra a Langford-párok\gyakindex{Langford-pár = Langford pair}
elrendezését úgy, hogy $n=4m$-re is megkapjuk a megoldást az elsõ \idez{$2m{-}1$}-et  \idez{$4m$}-re cserélve és 
\idez{$2m{-}1\,\,4m$}-et jobbról hozzáírva. \textit{Útmutatás.} Helyezzük balra az $m-1$ páros számot, $4m{-}4$, $4m{-}6$, 
\dots,~$2m$-et.
\ujgyak\label{gyak70-2} \sz{18}
Milyen $n$ esetén lehet $\{1,1,2,2,\ldots,n,n\}$-et Langford-párokba rendezni?
\ujgyak\label{gyak70-3} \sz{22}
Tegyük fel, hogy a  $\{0,0,1,1,\ldots,n{-}1,n{-}1\}$ számokat \textit{körben} rendezzük el, nem pedig egy vonalban úgy, 
hogy $k$ távolság legyen két $k$ között. Kaphatunk-e olyan megoldásokat, amelyek  lényegesen különböznek a 
\ref{gyak70-2}. gyakorlat megoldásaitól?  
\ujgyak\label{gyak70-4} \sz{M20}
(T. Skolem, 1957.\angolnevindex{Skolem, Albert Thoralf (1867--1963)}) 
Mutassuk meg, hogy az 1.2.8.-36. gyakorlat $S_\infty=babbababbabba\ldots{}$ Fibonacci-füzére\gyakindex{Fibonacci-füzér = 
Fibonacci string}  egyenesen elvezet a Langford-párok \textit{összes} nemnegatív egész halmazán vett $00121$ $32453674\ldots{}$
végtelen sorozatához, ha az $a$-kat és a $b$-ket egymástól függetlenül sorban a 0, 1, 2, stb. számjegyekkel 
helyettesítjük balról jobbra haladva.
\ujgyak\label{gyak70-5} \sz{F22}
Ha véletlenszerûen választjuk $\{1,1,2,2,\ldots,n,n\}$ egyik permutációját, mi a valószínûsége annak, hogy két 
$k$ pontosan $k$ pozícióra van egymástól adott $k$ esetén? Használjuk ezt a képletet arra, hogy megbecsüljük  
a Langford-számok $L_n$ számát (\ref{keplet70-1})-ben. 
\ujgyak\label{gyak70-6} \sz{M28} (M. Godfrey\angolnevindex{Godfrey, Michael John}, 2002.) 
Legyen $f(x_1,\ldots,x_{2n})= \prod_{k=1}^{n}\bigl(x_kx_{n+k}\sum_{j=1}^{2n-k-1}\!x_jx_{j+k+1}\bigr).$
\begin{enumerate}
\breathe
\item[a)] Bizonyítsuk be, hogy $\sum_{x_1,\ldots,x_{2n}\in\{-1,+1\}}f(x_1,\ldots,x_{2n}) =2^{2n+1}L_n$.
\item[b)] Indokoljuk meg, hogyan lehet ezt az összeget $O(4^n n)$ lépésben megbecsülni. 
Hány bit pontosságú aritmetikára van szükség ehhez?  
\item[c)] Adjuk meg nyolc??? egyik tényezõjét, felhasználva az alábbi azonosságot:
\begin{equation*}
\kern-2emf(x_1,\ldots,x_{2n})=f(-x_1,\ldots,-x_{2n})=f(x_{2n},\ldots,x_1)=
f(x_1,-x_2,\ldots,x_{2n-1},-x_{2n})\koz.
\end{equation*}
\end{enumerate}
\ujgyak\label{gyak70-7} \sz{M22}
Bizonyítsuk be, hogy $\{1,1,\ldots,16,16\}$ mindegyik Langford-párosításának valahol hét  
befejezetlen párt\footnote{Vagyis a pár egyik tagja le van helyezve, a másik még nincs. \textit{A fordító.}} 
kell tartalmaznia, ha balról jobbra haladunk.
\ujgyak\label{gyak70-8} \sz{23}
A legegyszerûbb Langford-sorozat nem csupán jól 
kiegyensúlyozott\gyakindex{jól kiegyensúlyozott Langford-sorozat = well-balanced Langford pairing}, 
hanem {\it{síkba rajzolható}}\gyakindex{gráf = graph!síkba rajzolható gráf = planar graph} is, 
abban az értelemben, hogy a párokat össze lehet kötni a vonalak keresztezõdése nélkül, mint (\ref{keplet70-2})-ben:
$$\epsfbox{\figdir/v4a.8}\koz.$$
Keressük meg az összes síkba rajzolható Langford-párosítást, ha $n\le 8$. 
\ujgyak\label{gyak70-9} \sz{24}
({\it{Langford-hármasok}}\gyakindex{Langford-hármas = Langford triple}.)
Hányféleképpen lehet sorba rendezni $\{1,1,1,2,2,2,\ldots,9,9,9\}$-et 
úgy, hogy két egymás utáni $k$ egymástól $k$ távolságra legyen $1\le k\le 9$ esetén?
\ujgyak\label{gyak70-10} \sz{M20}
Mutassuk meg, hogy hogyan lehet \textit{bûvös négyzetet}\gyakindex{bûvös négyzet = magic square} 
készíteni közvetlenül a \ref{abra70-1}. ábrából. (Feleltessünk meg mindegyik kártyának egy 1 és 16 közé esõ számot 
olyan módon, hogy a sorokban, oszlopokban, valamint a fõdiagonálisokban 34 legyen az összeg.) 
\ujgyak\label{gyak70-11} \sz{20}
Terjesszük ki (\ref{keplet70-5})-öt egy 
\idez{héber-görög-latin}\gyakindex{görög-latin négyzet = Gr{\ae}co-Latin square}  
négyzetté úgy, hogy a \textbf{HÉBER}
%% \font\heb=heb8 at 9pt \def\\#1{\hbox{\heb\char"4#1}} $\{\\0,\\1,\\2,\\3\}$ 
betûk valamelyikét hozzáírjuk mindegyik cellában lévõ kétbetûs füzérhez. 
Egyetlen (latin, görög), (latin, {héber}\gyakindex{héber négyzet = Hebrew square}), illetve (görög, héber) 
betû pár sem fordulhat elõ egynél több helyen. 
\ujgyak\label{gyak70-12} \sz{M21}
(L. Euler\angolnevindex{Euler, Leonhard ({\rus E1i0ler, Leonard} = {\rus Ei0lerp2, Leonardp2}, 1707--1783)}.) 
Legyen $L_{ij}=(i+j)\mod n$, ha $0\le i,j<n$ 
egészek modulo~$n$ vett {összeadási táblája}.\gyakindex{összeadási tábla = addition table}
Mutassuk meg, hogy $L$-re ortogonális latin négyzet akkor és csak akkor 
létezik, ha $n$ páratlan. 
\ujgyak\label{gyak70-13} \sz{M25}
Egy $10\times 10$-es négyzet négy $5\times 5$-ös negyedre osztható. Egy $10\times 10$-es latin négyzetnek, amelyik a 
$\{0,1,\ldots,9\}$ számjegyeket tartalmazza, $k$ \idez{betolakodója}\gyakindex{betolakodó = intruder} van, ha 
a felsõ baloldali negyede pontosan $k$ $\ge 5$ elemet tartalmaz. (Lásd $k=3$-ra példaként a \ref{gyak70-14}.(e) gyakorlatot.)
Bizonyítsuk be, hogy a négyzetnek nincs ortogonális párja, kivéve, ha  van legalább három betolakodója. 
\ujgyak\label{gyak70-14} \sz{29}
Keressük meg az alábbi latin négyzetek összes ortogonális párját:
$$\advance\abovedisplayskip9pt
  \advance\belowdisplayskip3pt
\def\\#1 #2.{\vcenter{\kern-12pt\baselineskip=9pt\halign{##\cr
        \hfil(#1)\hfil\cr\noalign{\vskip3pt}#2}}\,}
\\a
3145926870\cr
2819763504\cr
9452307168\cr
6208451793\cr
8364095217\cr
5981274036\cr
4627530981\cr
0576148329\cr
1730689452\cr
7093812645\cr.;\quad
\\b
2718459036\cr
0287135649\cr
7524093168\cr
1435962780\cr
6390718425\cr
4069271853\cr
3102684597\cr
9871546302\cr
8956307214\cr
5643820971\cr.;\quad
\\c
0572164938\cr
6051298473\cr
4867039215\cr
1439807652\cr
8324756091\cr
7203941586\cr
5610473829\cr
9148625307\cr
2795380164\cr
3986512740\cr.;\quad
\\d
1680397425\cr
8346512097\cr
9805761342\cr
2754689130\cr
0538976214\cr
4963820571\cr
7192034658\cr
6219405783\cr
3471258906\cr
5027143869\cr.;\quad
\\e
7823456019\cr
8234067195\cr
2340178956\cr
3401289567\cr
4012395678\cr
5678912340\cr
6789523401\cr
0195634782\cr
1956740823\cr
9567801234\cr..$$
\ujgyak\label{gyak70-15} \sz{50}
Keressünk $10\times10$-es latin négyzeteket, amelyek  
kölcsönösen ortogonálisak\gyakindex{kölcsönösen ortogonálisak = mutually orthogonal} egymásra.
\ujgyak\label{gyak70-16} \sz{48}
(H. J. Ryser,\angolnevindex{Ryser, Herbert John (1923--1985)} 1967.)
Egy latin négyzetet \idez{$n$-ed rendûnek}\gyakindex{nedrendû@$n$-ed rendû = order $n$} mondunk, ha  
$n$ sora, $n$ oszlopa van és $n$ szimbólumot tartalmaz.\gyakindex{latin négyzet rendje = order of a latin square}
Van-e minden páratlan rendû latin négyzetnek tranzverzálisa?
\ujgyak\label{gyak70-17} \sz{25}
Legyen $L$ egy latin négyzet,\gyakindex{latin négyzet = Latin square} melynek elemei $L_{ij}$, ha $0\le i,j<n$. 
Nézzük a következõ két feladatot: 
(a) $L$ összes tranzverzálisának\gyakindex{tranzverzális = transversal} a megkeresése 
és (b) $L$ összes ortogonális párjának\gyakindex{ortogonális pár = orthogonal mate} a megkeresése. 
Igazoljuk, hogy ez a két probléma speciális esete 
az általános teljes lefedési problémának.\gyakindex{pontos lefedési probléma = exact cover problem}
\ujgyak\label{gyak70-18} \sz{M23}
Az $x_1x_2\ldots x_N$ füzért \idez{$n$-árisnak}\gyakindex{náris@$n$-áris füzér = $n$-ary string} 
nevezzük, ha mindegyik $x_j$ elem az $n$-áris $\{0,1,\ldots,$ $n - 1\}$ halmazból való. 
Két $x_1x_2\ldots x_N$ és $y_1y_2\ldots y_N$ füzért 
\textit{ortogonálisnak}\gyakindex{ortogonális füzérek = orthogonal strings} mondunk, 
ha az $N$ darab $(x_j,y_j)$ pár diszjunkt, ahol $1\le j\le N$. (Következésképpen két $n$-áris füzér nem lehet ortogonális, 
ha $N$ hosszuk meghaladja az $n^2$-et.) Egy $m$ sorral és $n^2$ oszloppal rendelkezõ olyan $n$-áris mátrixot, amelyiknek sorai 
ortogonálisak egymásra $n$-ed rendû $m$-mélységû \textit{ortogonális mátrixnak}\gyakindex{ortogonális mátrix = orthogonal array}
nevezünk. 

Keressünk összefüggést $m$ mélységû ortogonális mátrixok, 
és kölcsönösen ortogonális latin négyzetek $m-2$ listája között. 
Melyik ortogonális mátrix felel meg a \ref{gyak70-11}. gyakorlatnak? 
\ujgyak\label{gyak70-19} \sz{M25}
A \ref{gyak70-18}. gyakorlatot folytatva bizonyítsuk be, hogy  
$n>1$~rendû és $m$~mélységû ortogonális mátrix 
csak akkor lehetséges, ha $m\le n+1$.
Mutassuk meg, hogy ez a felsõ határ megvalósítható, ha 
$n$ egy $p$~prímszám. 
Írjunk fel egy példát, ha $p=5$. 
\ujgyak\label{gyak70-20} \sz{F20}
Mutassuk meg, hogy ha egy ortogonális mátrix minden $k$ elemét   
$e^{2\pi ki/n}$-nel helyettesítjük, akkor a sorok 
ortogonális vektorok\gyakindex{ortogonális vektorok = orthogonal vectors} lesznek 
a szokásos értelemben (vektoriális szorzatuk\gyakindex{vektoriális szorzat = dot product} nulla). 
\ujgyak\label{gyak70-21} \sz{M21}
Egy {\it{geometriai háló}\/}\gyakindex{geometriai háló = geometric net} 
pontok és egyenesek rendszere, amelyek eleget tesznek három axiómának:   
%\breathe
\begin{enumerate}
\item[i)] Mindegyik egyenes pontok halmaza.
\item[ii)] Különbözõ egyeneseknek legfeljebb egy közös pontjuk van.
\item[iii)] Ha $p$ egy pont és $L$ egy egyenes, amelyikre $p\notin L$, 
akkor pontosan egy olyan $M$ egyenes van, amelyikre $p\in M$ és $L\cap M=\emptyset$.
\end{enumerate}
\breathe\noindent Ha $L\cap M=\emptyset$, akkor azt mondjuk, hogy $L$ 
{\it{párhuzamos}\/}\gyakindex{párhuzamos egyenesek = parallel lines}
$M$-mel, és ezt $L\parallel M$-mel jelöljük.
%\breathe
\begin{enumerate}
\item[a)] Bizonyítsuk be, hogy egy geometriai háló egyenesei 
ekvivalencia osztályokba oszthatóak szét   
úgy, hogy két egyenes akkor és csak akkor van ugyanabban az osztályban, 
ha megegyezik, vagy párhuzamos.  
\item[b)] Mutassuk meg, hogy ha van a párhuzamos egyeneseknek 
legalább két osztálya, mindegyik egyenes ugyanannyi 
számú pontot tartalmaz, mint az ugyanebben az osztályban lévõ többi egyenes. 
\item[c)] Továbbá, ha van legalább három osztály, vannak olyan $m$ és $n$ 
számok, hogy minden pont pontosan $m$ egyeneshez tartozik, 
és minden egyenes pontosan $n$  pontot tartalmaz.  
\end{enumerate}
\ujgyak\label{gyak70-22} \sz{M22}
Mutassuk meg, hogy mindegyik ortogonális mátrix\gyakindex{ortogonális mátrix = orthogonal array} 
tekinthetõ geometriai hálónak\gyakindex{geometriai háló = geometric net}. 
Igaz-e ennek a fordítottja is? 
\ujgyak\label{gyak70-23} \sz{M21}
({\it Hibajavító kódok}.) Két $x=x_1\ldots x_N$ és $y=y_1\ldots y_N$ füzér közötti 
$d(x,y)$ \idez{Hamming-távolság} azoknak a $j$ pozícióknak a száma, amelyekre $x_j\ne y_j$. 
\gyakindex{hibajavító kód = error-correcting code}
\gyakindex{Hamming-távolság = Hamming distance}
Egy {\it $b$-áris kód $n$ információs jeggyel és $r$ ellenõrzõ jeggyel\/}  
\gyakindex{kódszó, $b$-áris = codeword, $b$-ary} 
$b^n$ $x=x_1\ldots x_{n+r}$ füzér $C(b,n,r)$ halmaza, 
ahol $0\le x_j<b$, ha $1\le j\le n+r$. 
Ha egy küldött kódszó az $x$, $y$ pedig a fogadott üzenet, akkor $d(x,y)$ az átviteli hibák száma. A kódot 
\textit{t-hibajavítónak} nevezzük, ha minden olyan alkalommal meg tudjuk állapítani $x$ értékét, amikor az $y$ fogadott üzenetre 
$d(x,y)\le t$. A kód {\it távolsága\/}\gyakindex{kód távolsága = distance of a code}
az összes $x\ne x'$ kódszó pár esetén $d(x,x')$ minimális értéke.
%\breathe
\begin{enumerate}
\item[a)] Bizonyítsuk be, hogy egy kód akkor és csak akkor 
$t$-hiba javító, ha távolsága meghaladja a $2t$-t.
\item[b)] Bizonyítsuk be, hogy egy olyan 1-hiba javító $b$-áris kód, 
amelyiknek 2 információs jegye és 2 ellenõrzõ jegye van, ekvivalens 
egy pár $b$ rendû ortogonális latin négyzettel. 
\item[c)] Továbbá egy $r+1$ távolságú $C(b,2,r)$ kód 
ekvivalens $r$ kölcsönösen ortogonális $b$ rendû
latin négyzetek egy halmazával.  
\end{enumerate}
\ujgyak\label{gyak70-24} \sz{M30}
Egy $N$ pontból és $R$ egyenesbõl álló geometriai háló\gyakindex{geometriai háló = geometric net} 
természetes úton elvezet a $C(2,N,R)$ bináris kódhoz,   
ha az $x_1\ldots x_{N}x_{N+1}\ldots x_{N+R}$ kódszavak 
az alábbi paritás bittel vannak definiálva:  
$$x_{N+k}=f_k(x_1,\ldots,x_N)=\textstyle
 \bigl(\sum\{x_j\mid\hbox{a $j$ pont a $k$ egyenesen fekszik}\}\bigr)\mod 2\koz.$$
\begin{enumerate}
\item[a)] Ha a hálónak $m$ osztálya van, amelyeket párhuzamos egyenesek alkotnak, bizonyítsuk be, hogy a kód távolsága $m+1$. 
\item[b)] Keressünk hatékony módot arra, hogy ha $m=2t$, akkor ezzel a kóddal $t$-hibával bezárólag javítani tudjunk.  
Szemléltessük a dekódolás folyamatát az $N=25$, $R=30$, $t=3$ esetben. 
\end{enumerate}
\ujgyak\label{gyak70-25} \sz{27}
Keressünk olyan latin négyzetet,\gyakindex{latin négyzet = Latin square} amelynek sorai és oszlopai ötbetûs szavakból álló 
szónégyzetek.\gyakindex{szónégyzet = word square} (Ehhez a gyakorlathoz elõ kell ásnunk a nagyszótárakat.)
\gyakindex{szótár = dictionary}
\ujgyak\label{gyak70-26} \sz{25}
Alkossunk értelmes angol mondatot, amelyik csupán ötbetûs szavakat tartalmaz. 
\ujgyak\label{gyak70-27} \sz{20}
Hány SGB szó tartalmaz $k$ különbözõ betût, ha $1\le k\le 5$?
\ujgyak\label{gyak70-28} \sz{20}
Van-e olyan SGB szó vektor pár, amelyik 
komponenseiben az egymásnak megfelelõ betûk $\pm1$-gyel térnek el 
egymástól\footnote{Az angol ábécében elfoglalt helyük szerint. \textit{A fordító.}}?
\ujgyak\label{gyak70-29} \sz{20}
Keressük meg az összes SGB szót, amelyek {\it{palindromák}\/}\gyakindex{palindroma = palindrome} 
(megegyezik a fordítottjával), vagy tükör párok\gyakindex{tükör párok = mirror pairs} 
(mint a \texttt{regal} \texttt{lager}).
\ujgyak\label{gyak70-30} \sz{20}
A \texttt{first} szó betûi alfabetikus sorrendben\gyakindex{alfabetikus sorrend = alphabetic order} 
vannak balról jobbra. 
Melyik lexikografikusan \gyakindex{lexikografikusan = lexicographically} az elsõ  
ilyen ötbetûs szó? Melyik az utolsó?
\ujgyak\label{gyak70-31} \sz{21}
(C. Manus.)\angolnevindex{McManus, Christopher DeCormis} 
Keressük meg az összes olyan halmazt, amelyik három olyan SGB szót tartalmaz, 
amelyek számtani sorozatot\gyakindex{számtani sorozat = arithmetic progression} alkotnak,  
de nincs közös betûjük semmilyen rögzített helyen. 
(Egy ilyen példa $\{\texttt{power}, \texttt{slugs}, \texttt{visit}\}$.)
\ujgyak\label{gyak70-32} \sz{23}
Vannak-e az angol nyelvben olyan 10-betûs 
$a_0a_1\ldots a_9$ szavak, amelyekre $a_0a_2a_4a_6a_8$ és
$a_1a_3a_5a_7a_9$ is SGB szavak? \gyakindex{tökéletes keverés = perfect shuffle}
\ujgyak\label{gyak70-33} \sz{20}
(S. Morris\angolnevindex{Morris, Scot Anderson}.)
Egészítsük ki a 26 érdekes SGB szó következõ listáját: 
$$\texttt{about}\koz,\ \texttt{bacon}\koz,\ \texttt{faced}\koz,\ \texttt{under}\koz,\ \texttt{chief}\koz,\
\ldots,\ \texttt{pizza}\koz.$$
\ujgyak\label{gyak70-34} \sz{21}
Minden olyan SGB szóból, amelyik nem tartalmazza az \texttt{y} betût,
nyerjünk ki egy 5-bites bináris számot úgy, hogy 
az $\{\texttt{a}\koz,\texttt{e}\koz,\texttt{i}\koz,\texttt{o}\koz,\texttt{u}\}$ 
magánhangzókat\gyakindex{magánhangzó = vowel} 1-re cseréljük, a többi betût pedig 0-ra. 
Melyek a legismertebb szavak a 32 bináris eredmény mindegyikénél?\gyakindex{mássalhangzó = consonant}
\ujgyak\label{gyak70-35} \sz{26}
A \texttt{WORDS}(1000) alábbi tizenhat jól megválasztott eleme elágaztatási stratégiához  
vezet\gyakindex{teljes bináris vizsgálat = complete binary trie|(}:
$$\epsfbox{\figdir/v4a.15}\koz,$$
ami az \texttt{s} betûvel kezdõdõ szavak teljes bináris vizsgálata. 
Azonban nincs ilyen sablon az \texttt{a} betûvel kezdõdõ szavakra, 
még akkor sem, ha a \texttt{WORDS}(5757) teljes gyûjteményét vizsgáljuk. 
Az ábécé mely betûi használhatóak olyan tizenhat szó kezdõbetûjeként, amelyek adott $n$ esetén a \texttt{WORDS}$(n)$-ben  
teljes bináris vizsgálatot\gyakindex{vizsgálat = trie} képeznek? 
\ujgyak\label{gyak70-36} \sz{M17}
Derítsük fel \gyakindex{szimmetria = symmetry} a (\ref{keplet70-10})-beli  
szó kockában \gyakindex{szó kocka = word cube} megjelenõ szimmetriákat. 
Mutassuk meg azt is, hogy további két ilyen kockát kapunk 
csupán a $\{\texttt{stove},\texttt{event}\}$ szavak cseréjével.
\ujgyak\label{gyak70-37} \sz{20}
Melyek a ${\it words\/}\koz(5757,0,0,0)$ gráf maximális 
fokszámú\gyakindex{gráf = graph!fok = degree} csúcsai?\gyakindex{teljes bináris vizsgálat = complete binary trie|)}
\ujgyak\label{gyak70-38} \sz{22}
A (\ref{keplet70-14})-beli irányított gráf szabályt használva 
változtassuk \texttt{tears}-t \texttt{smile}-ra pontosan 
három lépésben, {\it számítógép segítsége nélkül}. \gyakindex{mosoly = smile}
\ujgyak\label{gyak70-39} \sz{M00}
$G\setminus e$ feszített részgráfja-e $G$-nek?
Feszítõ részgráf-e?
\ujgyak\label{gyak70-40} \sz{M15}
Hány (a) feszítõ (b) feszített részgráfja van  
egy $G=(V,E)$ gráfnak\gyakindex{gráf = graph}, ha 
$\vert V\vert=n$ és $\vert E\vert=e$?
\ujgyak\label{gyak70-41} \sz{M10}
Milyen $n$ egész szám esetén lesz (a) $K_n=P_n$? (b) $K_n=C_n$?
\ujgyak\label{gyak70-42} \sz{15}
(D. H. Lehmer\angolnevindex{Lehmer, Derrick Henry (1905--1991)}.) Legyen $G$ egy gráf 13 csúccsal, 
amelyben minden csúcs foka 5. Adjunk nem triviális állítást $G$-rõl.
\ujgyak\label{gyak70-43} \sz{23}
A következõ gráfok ugyanazok-e, mint a Petersen-gráf\gyakindex{gráf = graph!Petersen-gráf = Petersen graph}?
$$\epsfbox{\figdir/v4a.1501} \qquad\qquad \epsfbox{\figdir/v4a.1502}\qquad\qquad
\epsfbox{\figdir/v4a.1503} \qquad\qquad \epsfbox{\figdir/v4a.1504}$$
\ujgyak\label{gyak70-44} \sz{M23}
Hány szimmetriája\gyakindex{szimmetria = symmetry} van a 
Chv\'atal-gráfnak\gyakindex{gráf = graph!Chv\'atal-gráf = Chv\'atal graph}?
(Lásd a \ref{abra70-2}.(f) ábrát.)
\ujgyak\label{gyak70-45} \sz{20}
Keressünk könnyû módot a (\ref{keplet70-17})-beli síkba rajzolható gráf 4-színezésére\gyakindex{négyszín@4-színezés = 4-coloring}. 
\gyakindex{USA államainak a szomszédsága = contiguous USA \textit{lásd}
contiguous United States of America}
Elegendõ lenne-e 3 szín?
\ujgyak\label{gyak70-46} \sz{M25}
Tegyük fel, hogy egy $n\ge3$ csúcsú $G$ gráfot olyan síkbeli ábrával 
definiálunk, amelyik \idez{maximális}
\gyakindex{gráf = graph!maximális síkbeli gráf = maximal planar graph} abban az értelemben, 
hogy újabb vonalat nem lehet húzni nem szomszédos csúcsok között 
a meglévõ élekkel való keresztezõdés nélkül.      
\begin{enumerate}
\item[a)] Bizonyítsuk be, hogy az ábra a síkot olyan tartományokra osztja fel, 
amelyek mindegyikének határán pontosan három csúcs van. 
(Ezeknek a tartományoknak az egyike azoknak a pontoknak a halmaza, amelyek 
az ábrán kívül fekszenek.)
\item[b)] Következésképpen $G$-nek pontosan $3n-6$ éle van.
\end{enumerate}
\vspace{-2mm}
\ujgyak\label{gyak70-47} \sz{M22}
Bizonyítsuk be, hogy a $K_{3,3}$ teljes bigráf nem síkba rajzolható.
\ujgyak\label{gyak70-48} \sz{M25}
Egészítsük ki a B tétel bizonyítását annak a megmutatásával, hogy 
a szóban forgó eljárás sohasem adja ugyanazt a színt két 
szomszédos csúcsnak. 
\ujgyak\label{gyak70-49} \sz{18}
Rajzoljuk meg az összes legfeljebb 6 csúcsú kubikus?? 
gráf\gyakindex{gráf = graph!kubikus?? gráf = cubic graphs} 
ábráját.
\ujgyak\label{gyak70-50} \sz{M24}
Keressük meg az összes olyan kétrészes gráfot, amelyik 
pontosan 24-féleképpen 3-színezhetõ\gyakindex{gráf = graph!háromszínezhetõ@3-színezhetõ gráf = 3-colored graph}.
\ujgyak\label{gyak70-51} \sz{M22}
Adott egy, a \ref{gyak70-21}. gyakorlatban leírt geometriai háló,\gyakindex{geometriai háló = geometric net} 
készítsünk olyan kétrészes gráfot\gyakindex{gráf = graph!kétrészes gráf = bipartite graph}, 
amelyiknek a csúcsai a háló $p$ pontjai és $L$ egyenesei, és $p\adj L$ akkor és csak akkor, ha $p\in L$. Mekkora a 
\textit{kerülete}\gyakindex{gráf = graph!kerület = girth} ennek a gráfnak? 
\ujgyak\label{gyak70-52} \sz{M16}
Keressünk egyszerû egyenlõtlenséget, amelyik megadja hogyan viszonyul 
a gráf átmérõje\gyakindex{gráf = graph!gráf átmérõje = diameter of a graph}  
a kerületéhez\gyakindex{gráf = graph!gráf kerülete = girth of a graph}. 
(Mennyire kicsi lehet az átmérõ, ha a kerület nagy terjedelmû?)
\ujgyak\label{gyak70-53} \sz{15}
A \texttt{world} és a \texttt{happy} szavak\gyakindex{szó = word} közül melyik tartozik 
a ${\it words}\koz(5757,0,0,0)$ 
gráf óriás komponenséhez\gyakindex{gráf = graph!gráf óriás komponense = giant component of a graph}?  
\ujgyak\label{gyak70-54} \sz{21}
A (\ref{keplet70-17})-beli gráfban a 49 postai kód\gyakindex{postai kód = postal codes}
alfabetikus sorrendben a következõ: 
\texttt{AL},
\texttt{AR},
\texttt{AZ},
\texttt{CA},
\texttt{CO},
\texttt{CT},
\texttt{DC},
\texttt{DE},
\texttt{FL},
\texttt{GA},
\texttt{IA},
\texttt{ID},
\texttt{IL},
\texttt{IN},
\texttt{KS},
\texttt{KY},
\texttt{LA},
\texttt{MA},
\texttt{MD},
\texttt{ME},
\texttt{MI},
\texttt{MN},
\texttt{MO},
\texttt{MS},
\texttt{MT},
\texttt{NC},
\texttt{ND},
\texttt{NE},
\texttt{NH},
\texttt{NJ},
\texttt{NM},
\texttt{NV},
\texttt{NY},
\texttt{OH},
\texttt{OK},
\texttt{OR},
\texttt{PA},
\texttt{RI},
\texttt{SC},
\texttt{SD},
\texttt{TN},
\texttt{TX},
\texttt{UT},
\texttt{VA},
\texttt{VT},
\texttt{WA},
\texttt{WI},
\texttt{WV},
\texttt{WY},
\breathe
\begin{enumerate}
\item[a)] Tegyük fel, hogy akkor tekintünk két államot szomszédosnak, ha 
a postai kódjuk egy helyen megegyezik  
(nevezetesen $\texttt{AL}\adj\texttt{AR}\adj\texttt{OR}\adj\texttt{OH}$ stb.). 
Melyek ennek a gráfnak a komponensei\gyakindex{gráf = graph!gráf komponense = component of a graph}?
\breathe
\item[b)] Készítsünk irányított gráfot az $\texttt{XY}\longrightarrow\texttt{YZ}$-vel 
(például $\texttt{AL}\rightarrow\texttt{LA}\rightarrow\texttt{AR}$ stb.). 
Melyek ennek a gráfnak az \textit{erõsen összefüggõ komponensei}?
\gyakindex{gráf = graph!gráf erõsen összefüggõ komponense = strongly connected component of a graph} 
(Lásd a 2.3.4.2. pontot.)
\breathe
\item[c)] Az USA-nak vannak postai kódjai a (\ref{keplet70-17}) ábrabelieken kívül: 
\texttt{AA},
\texttt{AE},
\texttt{AK},
\texttt{AP},
\texttt{AS},
\texttt{FM},
\texttt{GU},
\texttt{HI},
\texttt{MH},
\texttt{MP},
\texttt{PW},
\texttt{PR},
\texttt{VI}. 
Gondoljuk meg a (b) kérdést mind a 62 kód felhasználásával.
\end{enumerate}
\vspace{-2mm}
\ujgyak\label{gyak70-55} \sz{M20}
Hány él van a $K_{n_1,\ldots,n_k}$ 
teljes $k$-részes gráfban?\gyakindex{gráf = graph!teljes $k$-részes gráf = complete $k$-partite graph}
\ujgyak\label{gyak70-56} \sz{M10}
Igaz, vagy hamis: Egy multigráf\gyakindex{gráf = graph!multigráf = multigraph} akkor és csak akkor gráf, 
ha a megfelelõ digráf\gyakindex{gráf = graph!digráf = digraph} 
\gyakindex{gráf = graph!egyszerû gráf= simple graph} egyszerû.
\vspace{-2mm}
\ujgyak\label{gyak70-57} \sz{M10}
Igaz, vagy hamis: Az $u$ és $v$ akkor és csak akkor vannak egy irányított 
gráf ugyanazon összefüggõ komponensében, ha vagy 
$d(u,v)<\infty$, vagy $d(v,u)<\infty$.
\ujgyak\label{gyak70-58} \sz{M17}
Írjuk le az összes (a) gráfot (b) multigráfot, amelyek 2-fokú regulárisak.
\ujgyak\label{gyak70-59} \sz{M23}
Egy $n$-ed rendû \textit{verseny}\gyakindex{gráf = graph!verseny gráf = tournament graph}
egy irányított gráf $n$ csúccsal és pontosan $n\choose2$ irányított éllel, 
melyekre $u\rightarrow v$ vagy $v\rightarrow u$ teljesül bármely két különbözõ $\{u,v\}$ csúcs esetén.
\begin{enumerate}
\item[a)] Bizonyítsuk be, hogy mindegyik verseny tartalmaz egy 
$v_1\rightarrow\cdots\rightarrow v_n$ 
irányított feszítõ 
utat\gyakindex{gráf = graph!irányított feszítõ út gráfban = oriented spanning path in a graph}. 
\item[b)] Tekintsünk egy versenyt a $\{0,1,2,3,4\}$ csúcsokon, 
amelyikre $u\rightarrow v$ akkor és csak akkor, ha $(u-v)\mod 5 \ge 3$. 
Hány irányított feszítõ útja van?
\item[c)] Vajon $K^\rightarrow _{n}$ \gyakindex{Knir@$K_n\hspace{-1.6mm}\vec{} \ = K_n\hspace{-1.6mm}\vec{} \hspace{1.5mm}$}
az egyetlen $n$-ed rendû verseny, amelyiknek egyetlen 
irányított\gyakindex{gráf = graph!tranzitív verseny = transitive tournament} feszítõ útja van?  
\end{enumerate}
\vspace{-2mm}
\ujgyak\label{gyak70-60} \sz{M22}
Legyen $u$ a versenyben a legnagyobb ki-fokú csúcs\gyakindex{gráf = graph!gráf csúcsának ki-foka = out-degree of a vertex of a graph},
és legyen $v$ egy másik csúcs. Bizonyítsuk be, hogy $d(u,v)\le 2$.
\ujgyak\label{gyak70-61} \sz{M16}
Készítsünk olyan digráfot, amelyiknek $k$ darab $k$ hosszú sétája van az 1 csúcstól a 2 csúcsig.
\ujgyak\label{gyak70-62} \sz{M21}
Egy \textit{permutációs digráf}\gyakindex{gráf = graph!permutációs digráf = permutation digraph} 
olyan irányított gráf, amelyikben minden csúcs ki-foka 1 és be-foka is 1; így a 
komponensei\gyakindex{gráf = graph!gráf komponense = component of a graph} irányított 
körök\gyakindex{gráf = graph!gráf irányított köre = oriented cycle of a graph}. Ha $n$ csúcsa és $k$ komponense van, 
\textit{párosnak}\gyakindex{gráf = graph!páros gráf = even graph} nevezzük, ha $n-k$ páros, 
és \textit{páratlannak}\gyakindex{gráf = graph!páratlan gráf = odd gráf}, ha $n-k$ páratlan. 
\begin{enumerate}
\item[a)] Legyen $G$ irányított gráf az $A$ szomszédsági mátrixszal. Bizonyítsuk be, hogy $G$ feszítõ permutációs 
digráfjainak a száma ${\rm per}\,A$, az $A$ 
permanense\gyakindex{permanens = permanent}\gyakindex{mátrix permanense = permanent of a matrix}. 
\item[b)] Értelmezzük a $\det A$ determinánst a feszítõ permutációs digráf szempontjából. 
\end{enumerate}
\vspace{-2mm}
\ujgyak\label{gyak70-63} \sz{M23}
Legyen $G$ egy $g$ kerületû\gyakindex{gráf = graph!kerület = girth} gráf, amelyben 
minden csúcsnak legalább $d$ szomszédja van. Bizonyítsuk be, hogy $G$-nek legalább $N$ csúcsa van, ahol 
$$N=
\begin{cases}
1+\sum_{0\le k<t}d(d-1)^k,&\text{ha } $g=2t+1$\koz;\\
\noalign{\smallskip}
1+(d-1)^t+\sum_{0\le k<t}d(d-1)^k,&\text{ha } $g=2t+2$\koz.
\end{cases}$$
\ujgyak\label{gyak70-64} \sz{M21}
Folytatva a \ref{gyak70-63}. gyakorlatot, mutassuk meg, hogy 
van {\it egyetlen\/} 4 kerületû gráf $d$ minimális fokszámmal és 
$2d$ renddel minden $d\ge2$ esetén.
\ujgyak\label{gyak70-65} \sz{F31}
Tegyük fel, hogy a $G$ gráf kerülete 5, minimális fokszáma $d$, és 
$N=d^2\!+1$ csúcsa van.
\begin{enumerate}
\item[a)] Bizonyítsuk be, hogy $G$ $A$ szomszédsági mátrixa\gyakindex{gráf = graph!szomszédsági mátrix = adjacency matrix}
kielégíti az $A^2+A=(d-1)I+J$ egyenlõséget. 
\item[b)] Mivel $A$ szimmetrikus mátrix, $N$ darab $x_j$ ortogonális sajátvektora van\gyakindex{sajátvektor = eigenvector}, 
a megfelelõ $\lambda_j$ sajátértékekkel\gyakindex{sajátérték = eigenvalue} úgy, hogy $Ax_j=\lambda_jx_j$, ha $1\le j\le N$. 
Bizonyítsuk be, hogy mindegyik $\lambda_j$ vagy $d$, vagy $(-1\pm\sqrt{4d-3}\koz\koz)/2$.
\item[c)] Mutassuk meg, hogy ha $\sqrt{4d-3}$ irracionális, akkor $d=2$.
{\em Útmutatás:} $\lambda_1+\cdots+\lambda_N={\rm trace}(A)=0$.
\item[d)] És ha $\sqrt{4d-3}$ racionális, akkor $d\in\{3,7,57\}$.
\end{enumerate}
\vspace{-2mm}
\ujgyak\label{gyak70-66} \sz{M30}
A \ref{gyak70-65}. gyakorlatot folytatva, alkossunk meg egy gráfot, melyre $d=7$.
\ujgyak\label{gyak70-67} \sz{M48}
Van-e olyan reguláris gráf, amelyiknek 57 a foka, 3250 a rendje, és 5 a kerülete?
\ujgyak\label{gyak70-68} \sz{M20}
Hány különbözõ szomszédsági mátrixa van egy $n$ csúcsú $G$ 
mátrixnak?
\end{gyak}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%          MEGOLDÁSOK
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section*{A 7.0. alfejezet gyakorlatainak megoldása}
\addcontentsline{toc}{section}{A 7.0. alfejezet gyakorlatainak a megoldása}

\begin{gyak}

\ujgyak\label{megold70-1} 
Az útmutatás szerint a második \idez{$4m{-}4$}-et közvetlenül követnie kell 
az elsõ \idez{$2m{-}1$}-nek. A kívánt elrendezéseket ki lehet következtetni  
az elsõ négy példából, amelyek hexadecimális jelöléssel: 
\texttt{231213}, \texttt{46171435623725}, \texttt{86a31b1368597a425b2479},  \texttt{ca8e531f1358ac7db9e6427f2469bd}.  
\cite{Davies1959}\angolnevindex{Davies, Roy Osborne}
\ujgyak\label{megold70-2} 
Ilyen elrendezés akkor és csak akkor létezik, ha $n$ mod $4 = 0$ vagy 3.
Ez a feltétel szükséges, mert páros kell legyen a páratlan elemek száma. 
És elégséges is a feltétel, mert az elõzõ gyakorlatban a megoldás  
elejére lehet \idez{$00$}-t helyezni.  

{\em Megjegyzés:} Ezt a kérdést elõször {Hall}\angolnevindex{Hall, Marshall, jr. (1910--1990)} 
vetette fel 1951-ben, és {Leahy}\angolnevindex{Leahy, Francis Theodor, Jr}, oldotta meg 
a következõ évben \cite{Leahy1952}. 
Ettõl függetlenül vetette fel és oldotta meg a feladatot 
{Skolem}\angolnevindex{Skolem, Albert Thoralf (1867--1963)}   
és {Bang}\angolnevindex{Bang, Thoger Sophus Vilhelm} \cite{Skolem1957}. 
Más számintervallumokra lásd {Simpson}\angolnevindex{Simpson, James Edward} 
teljes megoldását \cite{Simpson1983}.
\ujgyak\label{megold70-3} 
Igen. A $(0072362435714165)$ kört például nem lehet 
megszakítani. 
\ujgyak\label{megold70-4} 
$b$ $k$-adszor balról a $\lfloor k\phi\rfloor$-edik  helyen fordul elõ,  
$a$ pedig  $k$-adszor a $\lfloor k\phi^2\rfloor$-edik helyen jelenik meg. 
Nyilván $\lfloor k\phi^2\rfloor-\lfloor k\phi\rfloor=k$, 
mert $\phi^2=\phi+1$. 
%\gyakindex{fí@phi = phi}
(A  $\lfloor k\phi\rfloor$ egészek $\phi$ \idez{spektrumát}\gyakindex{spektrum = spectrum} 
alkotják ; lásd a {\sl CMath} 3.13. gyakorlatát.)
\ujgyak\label{megold70-5} 
A $2n\choose2$ egyformán lehetséges pozíciópárból $2n-k-1$ elégíti ki az 
adott feltételt.
Ha ezek a valószínûségek függetlenek volnának 
egymástól (de nem azok), akkor $2L_n$ 
értéke a következõ volna: 
$$\eqaligntop{\Bigl({2n\atop2,2,\ldots,2}\Bigr)\prod_{k=1}^n
   \bigl({\textstyle(2n-1-k)/{2n\choose2}}\bigr)
&={(2n)!^2n(n-1)\over n!(2n)^{n+1}(2n-1)^{n+1}}\cr
&=\exp\Bigl(n\ln{4n\over e^3}+\ln\sqrt{\pi en\over2}
  +O(n\_)\Bigr)\koz.\cr}$$
\ujgyak\label{megold70-6} 
(a) Ha a szorzatokat kifejtjük, $(2n-2)!/(n-2)!$ tagú polinomot kapunk, 
mindegyik tag foka $4n$. Mindegyik Langford-párosítás számára van egy 
$x_1^2\ldots x_{2n}^2$ tag; az összes többi tagnak van legalább egy 
1-fokú változója.  
$x_1,\ldots,x_{2n}\in\{-1,+1\}$-re összegezve kiesik az összes rossz tag, 
és $2^{2n}$ adódik a jó tagok esetén. 
Ezen kívül egy 2-es tényezõ azért jelenik meg, 
mert $2L_n$ Langford-pár van (beleértve a bal-jobb megfordítottját).  

(b) Legyen $f_k=\sum_{j=1}^{2n-k-1}\!x_jx_{j+k+1}$ a $k$-adik tényezõ fõ része. 
Legyen $x_1,\ldots,x_{2n}\in\{-1,+1\}$, ekkor mind a $4^n$ esetén végig tudunk futni 
a {Gray-kód}\gyakindex{Gray-kód = Gray-code}  
sorrendjében, (lásd a 7.2.1.1. alpont hurokmentes-gray?? algoritmusát), 
miközben egyszerre csak egy $x_j$-t zárunk ki.   
Egy $x_j$-ben történõ csere esetén legfeljebb kétszer 
kell hozzányúlni mindegyik $f_k$-hoz; így mindegyik Gray-kód lépés költsége $O(n)$.

Nincs szükségünk arra, hogy az összeget pontosan kiszámítsuk; 
elegendõ mod~$2^N$ dolgoznunk, ahol $2^N$ megfelelõen meghaladja $2^{2n+1}L_n$-et.  
Ha $n=24$, akkor még jobb mod~$2^{60}-1$ végezni a számításokat, vagy  mod~$2^{30}-1$ 
és mod~$2^{30}+1$ is. 
Meg lehet takarítani $\lceil n/2\rceil$ bit pontosságot 
kihasználva azt a tényt, hogy $f_k\equiv k+1$ (modulo~2).
\gyakindex{moduláris aritmetika = modular arithmetic}

(c) A harmadik egyenlõség tulajdonképpen csak akkor érvényes, ha $n$ mod~$4=0$ vagy~3; 
de ezek az érdekes $n$-ek. 
Az összegzés $n$ lépésben végrehajtható,
ahol a $p$ lépés $p<n$-re 
azokat az eseteket foglalja magába, ahol 
$x_{n-1}=x_{n+2}$, $x_{n-2}=x_{n+3}$, \dots, $x_{n-p+1}=x_{n+p}$,
$x_{n-p}=x_n=x_{n+1}=+1$, és $x_{n+p+1}=-1$; 
van egy külsõ ciklusa, amelyik 
$(x_{n-p+1},\ldots,x_{n-1})$-et választja mind a $2^{p-1}$ módon, 
és egy belsõ ciklusa, amelyik
$(x_1,\ldots,x_{n-p-1},x_{n+p+2},\ldots,x_{2n})$-et választja 
mind a $2^{2n-2p-2}$ módon.
(A belsõ ciklus Gray bináris kódot használ,    
\idez{orgonasíp sorrendben}\gyakindex{orgonasíp sorrend = organ-pipe order} 
részesíti elõnyben az indexeket úgy, hogy $x_1$ és $x_{2n}$ váltakozzon a leggyorsabban. 
A külsõ ciklus nem kell, hogy különösen hatékony legyen.) 
Az $n$ lépés lefedi a $2^{n-1}$ tükörkép\gyakindex{tükörkép = palindromic}
\gyakindex{palindroma = palindromic, \textit{lásd} tükörkép} 
esetet ha $x_j=x_{2n+1-j}$, $1\le j<n$-re és $x_n=x_{n+1}=+1$. 
Ha $s_p$ jelöli a $p$ lépésben az összeget, akkor 
$s_1+\cdots+s_{n-1}+\half s_n=2^{2n-2}L_n$.

A tagok jelentõs részérõl kiderül, hogy nulla. 
Például ha $n=16$, az esetek körülbelül 76\%-ában nulla jelenik meg  
(408\,838\,754 esetben a $2^{29}+2^{14}$-bõl). 
Ezt a tényt használhatjuk arra, hogy a belsõ ciklusban sok 
szorzást elkerüljünk. (Csak $f_1$, $f_3$, \dots lehet nulla.)
\ujgyak\label{megold70-7} 
Legyen $d_k$ a befejezetlen párok száma, miután 
$k$ karaktert elolvastunk; így $d_0=d_{2n}=0$, és $d_k=d_{k-1}\pm1$,  
ha $1\le k\le2n$. A leghosszabb olyan sorozat, amelyikben $d_k$ 
sohasem haladja meg a 6-ot $(0,1,2,3,4,5,6,5,6,\ldots,5,6,5,4,3,2,1,0)$. 
Erre a sorozatra $\sum_{k=1}^{2n}d_k=11n-30$. 
De $\sum_{k=1}^{2n}d_k=\sum_{k=1}^{n}(k+1)
={n+1\choose2}+n$ bármelyik  Langford-párosításnál. 
Ebbõl ${n+1\choose2}+n\le11n-30$, és $n\le15$.
(Valójában a 6 szélesség $n=15$ esetén sem lehetséges. 
A legnagyobb és legkisebb lehetséges szélességet  
nem ismerjük általában.)
\ujgyak\label{megold70-8} 
Nincs megoldás, ha $n=4$ vagy $n=7$. Ha $n=8$, akkor négy van:
$$\epsfbox{\figdir/v4a.801};\epsfbox{\figdir/v4a.802};\epsfbox{\figdir/v4a.803};\epsfbox{\figdir/v4a.804}$$
(Ez a probléma egy jó kis összerakós rejtvényhez\gyakindex{összerakós rejtvény = mechanikal puzzle} vezet, ha  
$k+1$ szélességû és $\lceil k/2\rceil$ magasságú részecskéket használunk a $k$ darab számára. 
\gyakindex{szivárvány összerakós rejtvény = RainBones puzzle} 
Langford\angolnevindex{Langford, Charles Dudley} hasonló darabokat mutatott be 
eredeti feljegyzésében \cite{Langford1958}  
és $n=12$-re síkba rajzolható megoldást adott.
A kérdés megfogalmazható teljes lefedési 
problémaként\gyakindex{teljes lefedési probléma = exact cover problem}, 
ha a nem elsõdleges oszlopok reprezentálják azokat a helyeket, ahol 
két részecske nem keresztezheti egymást;??  
lásd a 7.2.2.1.-00 gyakorlatot.   
%--|langford-planar|. 
Brette\angolnevindex{Brette, Jean} egy hasonló 
rejtvényt eszelt ki; a probléma Skolem-féle\angolnevindex{Skolem, Albert Thoralf (1867--1963)} változatára 
alapozott, és a szélességet\gyakindex{szélesség = width} használta a 
síkba rajzolhatóság helyett; 1992-ben adott egy másolatot 
David Singmasternek\angolnevindex{Singmaster, David Breyer}.)
\ujgyak\label{megold70-9} 
Pontosan háromféleképpen: 
181915267285296475384639743,  
191218246279458634753968357, 
191618257269258476354938743 
(és a tükörképük).
Ezt elõször Baron találta meg. Lásd \cite{Baron1970}\angolnevindex{Baron, Gerd}. 
A 7.2.2.1. alpontbeli \idez{táncoló mutatók}\gyakindex{táncoló mutatók = dancing links} 
módszer egy csupán 360 csúcsú keresõ fa bejárásával oldja meg ezt a feladatot  
egy 132 soros teljes lefedési problémát adva.  
\gyakindex{teljes lefedési probléma = exact cover problem}
\ujgyak\label{megold70-10} 
Legyen például $\texttt{A}=12$, $\texttt{K}=8$, $\texttt{Q}=4$,
$\texttt{J}=0$, $\spadesuit=4$, $\heartsuit=3$, $\diamondsuit=2$,
$\clubsuit=1$; összegezzünk.\par
Ebben az összefüggésben a \ref{abra70-1}. ábrán láthatóval ekvivalens ortogonális latin négyzetek már a középkori iszlám 
talizmánokban is megjelentek (lásd {Ibn al-Hajj}\angolnevindex{Ibn al-Hajj, Muhammad ibn Muhammad (1258--1336)} \cite{Ibn1322}, 
õ adott egy $5{\times}5$-ös példát is);\gyakindex{iszlám matematika = Islamic maths}\gyakindex{arab matematika = Arabic maths}  
lásd Doutté\angolnevindex{Doutté, Edmond (1867--1926)} \cite{Doutte1909}; Ahrens\angolnevindex{Ahrens, Wilhelm Ernst Martin Georg} 
\cite{Ahrens1917}. Lásd Andersen\angolnevindex{Andersen, Lars D{\o}vling} készülõben lévõ cikkét is a latin négyzetek történetérõl 
\angolnevindex{Andersen, Lars D.} \cite{Andersen2007}. 
\ujgyak\label{megold70-11} 
%%%\font\heb=heb8 at 9pt 
%\def\\#1{\hbox{\heb\char"4#1}}%
$$
\begin{pmatrix}
%d\gamma\\0&a\delta\\1&b\beta\\2&c\alpha\\3\cr
%c\beta\\1&b\alpha\\0&a\gamma\\3&d\delta\\2\cr
%a\alpha\\2&d\beta\\3&c\delta\\0&b\gamma\\1\cr
%b\delta\\3&c\gamma\\2&d\alpha\\1&a\beta\\0\cr
d\gamma\ 0&a\delta\ 1&b\beta\ 2&c\alpha\ 3\cr
c\beta\ 1&b\alpha\ 0&a\gamma\ 3&d\delta\ 2\cr
a\alpha\ 2&d\beta\ 3&c\delta\ 0&b\gamma\ 1\cr
b\delta\ 3&c\gamma\ 2&d\alpha\ 1&a\beta\ 0\cr
\end{pmatrix} 
$$

(ITT \ A \  HEBER \ BETUKET \ IDEIGLENESEN \  SZAMOK \ HELYETTESITIK)

Ilyen négyzetekre a legkorábbi ismert példát Sauveur mutatta meg \cite{Sauveur1710}.\angolnevindex{Sauveur, Joseph (1653-1716)} 

\ujgyak\label{megold70-12} 
Ha $n$ páratlan, akkor választhatjuk $M_{ij}=(i-j)\mod n$-et. 
Ha azonban $n$ páros, akkor nem létezik {tranzverzális}\gyakindex{tranzverzális = transversal}: 
Ha ugyanis $\{(t_0{+}0)\mod n,\ldots, (t_{n-1}{+}n{-}1)\mod n\}$ 
tranzverzális lenne, akkor $\sum_{k=0}^{n-1}t_k\equiv\sum_{k=0}^{n-1}(t_k+k)$ (modulo~$n$)
teljesülne, amibõl $\sum_{k=0}^{n-1}k=\half n(n-1)$ többszöröse lenne $n$-nek.
\ujgyak\label{megold70-13} 
Helyettesítsünk minden $l$ elemet $\lfloor l/5\rfloor$-vel, 
így olyan mátrixot kapunk, amelyik $0$-kat és 1-eket tartalmaz. 
Nevezzük el a negyedeket: $\bigl({A\atop C}{B\atop D}\bigr)$; 
ekkor $A$ és $D$ pontosan $k$ 1-est tartalmaz, miközben 
$B$-ben és $C$-ben pontosan $k$ $0$ van. 
Tegyük fel, hogy az eredeti mátrixnak tíz diszjunkt tranzverzálisa van. 
Ha $k\le2$, közülük legfeljebb négy megy át egy 1-esen $A$-ban vagy $D$-ben, 
és legfeljebb négy megy át egy 0-n $B$-ben, vagy $C$-ben. 
Így közülük legalább kettõ tartalmaz csak $0$-t $A$-ban és $D$-ben, csak 1-est $B$-ben és $C$-ben. 
Egy ilyen tranzverzális azonban páros sok $0$-t tartalmaz (nem pedig ötöt), mert $A$-n és $D$-n ugyanannyiszor megy át. 

Hasonlóan egy $4m+2$ rendû latin négyzet, amelyiknek van ortogonális párja, $m$-nél több betolakodója kell legyen mind a 
$(2m+1)\times(2m+1)$ részmátrixában elemeinek átnevezése után.  
Lásd \cite{Mann1944}\angolnevindex{Mann, Henry Berthold (1905--2000)}.
\ujgyak\label{megold70-14} 
A (b) és (d) esetben nincs ilyen pár. Az (a), (c) és (e) esetekben 
rendre 2, 6, és 12\,265\,168(!) ortogonális pár van, amelyek közül lexikografikus 
sorrendben az elsõ és az utolsó alant látható: 
$$\advance\abovedisplayskip9pt
  \advance\belowdisplayskip3pt
\def\\#1 #2.{\vcenter{\kern-12pt\baselineskip=9pt\halign{##\cr
        \hfil(#1)\hfil\cr\noalign{\vskip3pt}#2}}\,}
\\a
0456987213\cr
1305629847\cr
2043798165\cr
3289176504\cr
4518263790\cr
5167432089\cr
6894015372\cr
7920341658\cr
8731504926\cr
9672850431\cr.,\
\\a
0691534782\cr
1308257964\cr
2169340578\cr
3250879416\cr
4587902631\cr
5412763890\cr
6945081327\cr
7836425109\cr
8723196045\cr
9074618253\cr.;\ \
\\c
0362498571\cr
1408327695\cr
2673519408\cr
3521970846\cr
4890253167\cr
5736841920\cr
6259784013\cr
7915602384\cr
8147036259\cr
9084165732\cr.,\
\\c
0986271435\cr
1354068792\cr
2741853960\cr
3572690814\cr
4630789251\cr
5218947306\cr
6095324178\cr
7869512043\cr
8407136529\cr
9123405687\cr.;\ \
\\e
0214365897\cr
1025973468\cr
2690587143\cr
3857694201\cr
4168730925\cr
5473829016\cr
6942158730\cr
7309216584\cr
8531402679\cr
9786041352\cr.,\
\\e
0987645321\cr
1795402638\cr
2506913874\cr
3154067289\cr
4231850967\cr
5348276190\cr
6820394715\cr
7069128543\cr
8412739056\cr
9673581402\cr..$$
\textit{Megjegyzés:} Az (a), (b), (c), és (d) négyzeteket a $\pi$, $e$\gyakindex{emint@$e$, mint \idez{véletlen} adat 
forrása = $e$ as source of ``random'' data}, $\gamma$\gyakindex{gammamint@$\gamma$, mint \idez{véletlen} adatok forrása = 
$\gamma$ as source of ``random'' data}, és $\Phi$\gyakindex{fímint@$\Phi$, mint \idez{véletlen} adatok forrása = 
$\phi$ as source of ``random'' data} 
decimális számjegyeibõl kaptuk, \gyakindex{pimint@Pi $(\Pi)$, mint \idez{véletlen} adatok forrása = Pi $(\Pi)$ as source of ``random'' data} 
elhagyva azokat a jegyeket, amelyek egy kitöltött latin négyzettel nem egyeztethetõk össze. Jóllehet valójában nem 
véletlenek\gyakindex{véletlen számjegy = random digit}, valószínûleg jellemzõek a $10\times 10$-es latin négyzetekre általában, 
amelyeknek nagyjából a fele rendelkezik ortogonális párral. Parker\angolnevindex{Parker, Ernest Tilden} készítette az 
(e) négyzetet, hogy szokatlanul nagy számú tranzverzálishoz jusson; 5504 tranzverzálisa van.
(Euler\angolnevindex{Euler, Leonhard ({\rus E1i0ler, Leonard} = {\rus Ei0lerp2, Leonardp2}, 1707--1783)} 
tanulmányozott hasonló 6-odrendû példát, így \idez{éppen lemaradt} egy $10\times 10$-es pár felfedezésérõl.)
\ujgyak\label{megold70-15} 
Parkert megdöbbentette a felfedezés, hogy a 14(e) egyik párja 
sem ortogonális egymásra. Brown\angolnevindex{Brown, John Wesley} 
és Hedayat\angolnevindex{Hedayat, Samad (= Abdossamad)} talált késõbb két $10{\times}10$-eset, 
amelyeknek volt négy közös diszjunkt tranzverzálisuk (de nem tíz) \cite{Brown1993}.
Lásd még \cite{Ganter1978}. \angolnevindex{Ganter, Bernhard}
\angolnevindex{Mathon, Rudolf Anton}\angolnevindex{Rosa, Alexander}
Weisner\angolnevindex{Weisner, Louis} (\cite{Weisner1963}) ötletét 
követve a szerzõ\angolnevindex{Knuth@\string\Knuth} 
véletlenül észlelt olyan négyzeteket, amelyek egészen közel vannak egy kölcsönösen 
ortogonális hármashoz: Az alábbi négyzet ortogonális a transzponáltjaihoz; 
és van öt diagonálisan szimmetrikus tranzverzálisa a   
$(0,p_0)$, \dots, $(9,p_9)$ cellákban $p_0\ldots p_9=0132674598$,
2301457689, 3210896745, 4897065312, és 6528410937, amelyek {\it majdnem \/}
diszjunktak: 49 cellát fednek le.
$$L\quad=\quad\left(\,\vcenter{\baselineskip=9.1pt\halign{&\kern.5pt#\cr
0&2&3&4&5&6&7&8&9&1\cr
3&1&9&2&7&0&8&5&4&6\cr
6&5&2&8&1&3&9&4&0&7\cr
8&7&5&3&2&4&1&9&6&0\cr
1&6&8&9&4&7&3&0&2&5\cr
4&9&7&0&8&5&2&6&1&3\cr
5&0&4&7&9&8&6&1&3&2\cr
9&4&1&6&3&2&0&7&5&8\cr
7&3&6&1&0&9&5&2&8&4\cr
2&8&0&5&6&1&4&3&7&9\cr}}\,\right)\quad\perp\quad
\left(\,\vcenter{\baselineskip=9.1pt\halign{&\kern.5pt#\cr
0&3&6&8&1&4&5&9&7&2\cr
2&1&5&7&6&9&0&4&3&8\cr
3&9&2&5&8&7&4&1&6&0\cr
4&2&8&3&9&0&7&6&1&5\cr
5&7&1&2&4&8&9&3&0&6\cr
6&0&3&4&7&5&8&2&9&1\cr
7&8&9&1&3&2&6&0&5&4\cr
8&5&4&9&0&6&1&7&2&3\cr
9&4&0&6&2&1&3&5&8&7\cr
1&6&7&0&5&3&2&8&4&9\cr
}}\,\right)\quad=\quad L^T.$$

McKay\angolnevindex{McKay, Brendan Damien}, Meynert\angolnevindex{Meynert, Alison}  
és Myrvold\angolnevindex{Myrvold, Wendy Joanne} részletes számításai bizonyították \cite{McKay2007}, 
hogy nincs $10\times10$-es latin négyzet nem triviális szimmetriával, amelyiknek  
két párja ortogonális lenne egymásra.?? 
Három kölcsönösen ortogonális latin négyzet létezése ismert 
minden $n>10$ esetben.
Lásd \cite{Wang1978}\angolnevindex{Wang, Shinmin Patrick}
\angolnevindex{Wilson, Richard Michael};
\cite{Todorov1985}\angolnevindex{Todorov, Dobromir Todorov ({\rus Todorov, Dobromir Todorov})}.
\ujgyak\label{megold70-16} 
Lásd \cite{Brualdi1991}\angolnevindex{Brualdi, Richard Anthony}\angolnevindex{Ryser, Herbert John (1923--1985)}. 
\ujgyak\label{megold70-17} 
(a) Legyen $3n$ oszlop, $r_j$, $c_j$, $v_j$ ahol $0\le j<n$,
és $n^2$ sor; az $(i,j)$ sorban legyen 1 az $r_i$, $c_j$, és 
$v_{\koz l}$, oszlopokban, 
ahol $l=L_{ij}$ ha $0\le i,j<n$.

(b) Legyen $4n^2$ oszlop $r_{ij}$, $c_{ij}$, $x_{ij}$, $y_{ij}$, 
ahol $0\le i,j<n$ és legyen $n^3-n^2+n$ sor; az $(i,j,k)$ sorban legyen 1 
az $r_{ik}$, $c_{jk}$, $x_{ij}$ és $y_{\koz lk}$ oszlopokban, ahol $l=L_{ij}$,  
ha $0\le i,j,k<n$ és ($i=k$ vagy $j>0$).
\ujgyak\label{megold70-18} 
Legyen adva  egy $A$ ortogonális mátrix $A_i$ sorokkal, ahol $1\le i\le m$,
definiáljuk az $L_i=(L_{ijk})$ latin négyzetet, ahol $1\le i\le m-2$ 
a következõ módon: $L_{ijk}=A_{iq}$, ha $A_{(m-1)q}=j$ és $A_{mq}=k$, ahol $0\le j,k<n$. 
($q$ értékét $j$ és $k$ értékei egyértelmûen meghatározzák.)
A mátrix oszlopait permutálva nem változnak a megfelelõ latin négyzetek.  

Ez a konstrukció megfordítható, s így alkalmazható arra, hogy kölcsönösen ortogonális $n$-ed rendû latin négyzetekbõl $n$-ed rendû 
ortogonális mátrixokat állítsunk elõ. A \ref{gyak70-11}. gyakorlatban például legyen \def\\#1{\hbox{\heb\char"4#1}}%
$a=\alpha=\\0=0$, $b=\beta=\\1=1$, $c=\gamma=\\2=2$, és $d=\delta=\\3=3$, így a következõt kapjuk:

\textbf{HÉBER BETÛK}
$$
A=\begin{pmatrix}
3\koz 0\koz 1\koz 2\koz 2\koz 1\koz 0\koz 3\koz 0\koz 3\koz 2\koz 1\koz 1\koz 2\koz 3\koz 0\cr
2\koz 3\koz 1\koz 0\koz 1\koz 0\koz 2\koz 3\koz 0\koz 1\koz 3\koz 2\koz 3\koz 2\koz 0\koz 1\cr
0\koz 1\koz 2\koz 3\koz 1\koz 0\koz 3\koz 2\koz 2\koz 3\koz 0\koz 1\koz 3\koz 2\koz 1\koz 0\cr
0\koz 0\koz 0\koz 0\koz 1\koz 1\koz 1\koz 1\koz 2\koz 2\koz 2\koz 2\koz 3\koz 3\koz 3\koz 3\cr
0\koz 1\koz 2\koz 3\koz 0\koz 1\koz 2\koz 3\koz 0\koz 1\koz 2\koz 3\koz 0\koz 1\koz 2\koz 3\cr
\end{pmatrix}.
$$

(Az ortogonális mátrix fogalma \idez{tisztább} matematikailag, mint az ortogonális latin négyzeteké, mert jobban magyarázza  
a rejtõzködõ szimmetriákat.  Figyeljük meg például, hogy egy $n\times n$-es $L$ mátrix akkor és csak akkor latin 
négyzet,\gyakindex{latin négyzet = latin square} ha ortogonális két bizonyos nem latin négyzetre, nevezetesen 
\begin{equation*}
L\;\perp\;\begin{pmatrix}
1&1&\dots&1\cr
                 2&2&\dots&2\cr
               \noalign{\vskip-1pt}
                \vdots&\vdots&\ddots&\vdots\cr
               \noalign{\vskip-1pt}
                 n&n&\dots&n\cr
			\end{pmatrix}
				 \qquad\hbox{és}\qquad L\;\perp\;
		%\pmatrix{
  \begin{pmatrix}
  1&2&\dots&n\cr
                 1&2&\dots&n\cr
               \noalign{\vskip-1pt}
                \vdots&\vdots&\ddots&\vdots\cr
               \noalign{\vskip-1pt}
                 1&2&\dots&n\cr
	 \end{pmatrix}.
\end{equation*}	 
Így latin négyzetek, görög-latin négyzetek\gyakindex{görög-latin négyzet = Gr{\ae}co-Latin square},
héber-görög-latin négyzetek\gyakindex{héber-görög-latin négyzet = Hebraic-Gr{\ae}co-Latin square}, 
stb. ekvivalensek a 3, 4, 5, \dots\koz mélységû ortogonális mátrixokkal. 
Azonfelül az itt figyelembe vett ortogonális mátrixok 
csupán speciális esetei $t=2$ és $\lambda=1$ értékekkel 
a \idez{$t$ erejû??} és \idez{$\lambda$ mutatójú??} 
$m\times\lambda n^t$-es $n$-áris mátrixok 
egy sokkal általánosabb fogalmának,  
amit Rao\angolnevindex{Rao, Calyampudi Radhakrishna} vezetett be \cite{Rao1949}; 
lásd \cite{Hedayat1999}
\angolnevindex{Hedayat, Samad (= Abdossamad)}\angolnevindex{Sloane, Neil James Alexander}\angolnevindex{Stufken J.}.)
\ujgyak\label{megold70-19} 
Átrendezhetjük az oszlopokat úgy, hogy az elsõ sor $0^n1^n\ldots(n{-}1)^n$ legyen. 
Ezután a többi sorban átszámozhatjuk az elemeket, úgy hogy $01\ldots(n{-}1)$-gyel kezdõdjenek.
A megmaradó oszlopokban minden sorban, kivéve az elsõt, az elemek különbözõek kell legyenek.

A felsõ határ eléréséhez ha $n=p$, indexeljük mindegyik oszlopot 
az $x$ és $y$ számokkal, ahol $0\le x,y<p$, és helyezzük ebbe az oszlopba a 
$y$, $x$, $(x+y)\mod p$, $(x+2y)\mod p$, \dots, $(x+(p{-}1)y)\mod p$ számokat.  
Ha például $p=5$ a következõ ortogonális mátrixot kapjuk, 
amelyik ekvivalens négy kölcsönösen ortogonális latin négyzettel: 
\begin{equation*}
\left(
\begin{array}{ccccccccccccccccccccccccc}
0\!&\!0\!&\!0\!&\!0\!&\!0\!&\!1\!&\!1\!&\!1\!&\!1\!&\!1\!&\!2\!
&\!2\!&\!2\!&\!2\!&\!2\!&\!3\!&\!3\!&\!3\!&\!3\!&\!3\!&\!4\!&\!4\!&\!4\!&\!4\!&\!4\\
\noalign{\vskip-1pt}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\!&\!4
\!&\!0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\!&\!4\\
\noalign{\vskip-1pt}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1
\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\\
\noalign{\vskip-1pt}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3
\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\\
\noalign{\vskip-1pt}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0
\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\\
\noalign{\vskip-1pt}
0\!&\!1\!&\!2\!&\!3\!&\!4\!&\!4\!&\!0\!&\!1\!&\!2\!&\!3\!&\!3\!&\!4\!&\!0\!&\!1\!&\!2

\!&\!2\!&\!3\!&\!4\!&\!0\!&\!1\!&\!1\!&\!2\!&\!3\!&\!4\!&\!0\\
\end{array}
\right).
\end{equation*}
Lényegében ugyanez az elv akkor is mûködik, ha $n$ prímhatvány,   
ekkor a GF$(p^e)$ véges testet használjuk\gyakindex{véges test = finite field};
lásd \cite[\&15.1. ]{Moore1896a,Moore1896b}\angolnevindex{Moore, Eliakim Hastings (1862--1932)}. 
Ezek a mátrixok ekvivalensek a véges \textit{projektív síkokkal}\gyakindex{projektív sík = projective plane}; 
lásd \cite{Hall1967}. 
\ujgyak\label{megold70-20} 
Legyen $\omega=e^{2\pi i/n}$, és tegyük fel, hogy 
$a_1\ldots a_{n^2}$ és $b_1\ldots b_{n^2}$ különbözõ sorokban 
lévõ vektorok. Ekkor $a_1b_1+\cdots+a_{n^2}b_{n^2}=
\sum_{0\le j,k<n}\omega^{j+k}=0$, mert $\sum_{k=0}^{n-1}\omega^k=0$.
\ujgyak\label{megold70-21} 
(a) Ha meg akarjuk mutatni, hogy az egyenlõség vagy párhuzamosság 
ekvivalencia reláció\gyakindex{ekvivalencia reláció = equivalence relation}, 
akkor igazolnunk kell a tranzitivitási 
szabályt\gyakindex{tranzitivitási szabály = transitive law}: 
Ha $L\parallel M$ és $M\parallel N$
és $L\ne N$, akkor $L\parallel N$ kell teljesüljön. 
Ellenkezõ esetben (ii) szerint lenne olyan $p$ pont, amelyre $L\cap N=\{p\}$; 
$p$ pedig két különbözõ $M$-mel párhuzamos egyenesre illeszkedne, ami ellentmond 
(iii)-nek.\par

(b) Legyen $\{L_1,\ldots,L_n\}$ párhuzamos egyenesek 
egy osztálya, és tegyük fel, hogy $M$ egy másik osztály egyik egyenese. 
Ekkor mindegyik $L_j$ egyetlen $p_j$ pontban metszi $M$-et; 
és $M$ mindegyik pontja egy ilyen találkozási pont, mert (iii) szerint 
a geometria mindegyik pontja mindegyik osztálynak pontosan egy 
egyenesén van rajta.  
Így $M$-nek pontosan $n$ pontja van.\par

(c) Már megfigyeltük, hogy ha $m$ osztály van, akkor mindegyik pont 
$m$ egyeneshez tartozik hozzá. 
Ha az $L$, $M$, és $N$ egyenesek három különbözõ osztályból valóak, 
akkor $M$-nek és $N$-nek ugyanannyi pontja van, mint ahány 
egyenese az $L$ osztályának.
Így van egy közös $n$ méretû egyenes, és 
a pontok teljes száma valóban $n^2$. 
($n$ természetesen lehet végtelen.)
\ujgyak\label{megold70-22} 
Adott $n$ rendû és $m$ mélységû ortogonális $A$ mátrix esetén 
definiáljunk $n^2$ ponttal és párhuzamos egyenesekbõl álló $m$  
osztállyal egy geometriai hálót 
úgy, hogy $A$ oszlopait pontoknak tekintjük; a $k$ osztály $j$ egyenese 
azoknak az oszlopoknak a halmaza, amelyekre az $A$ mátrix $k$ sorában 
megjelenik a $j$ szimbólum.

Minden véges geometriai háló, amelyiknek $m\ge3$ osztálya van, 
elõáll ilyen módon. 
A csupán egyetlen osztályt tartalmazó geometriai háló nyilvánvalóan 
pontok diszjunkt halmazokba való szétosztása. 
Az $m=2$ osztályú geometriai hálónak $nn'$  $(x,x')$ pontja van, 
ahol $n$ számú `$x=\rm konstans$' egyenes van az egyik osztályban, 
és $n'$ számú `$x'=\rm konstans$' a másikban.
További információért lásd \cite{Bruck1951,Bruck1963}\angolnevindex{Bruck, Richard Hubert}.
\ujgyak\label{megold70-23} 
(a) Ha $d(x,y)\le t$ és $d(x',y)\le t$ és $x\ne x'$, akkor
$d(x,x')\le2t$. Így egy olyan kód, amelynél két kódszó között  
a távolság $>2t$, lehetõvé teszi a javítást egészen $t$-hibáig -- legalábbis 
elvileg, jóllehet a számítás lehet bonyolult. 
Fordítva, ha $d(x,x')\le2t$ és $x\ne x'$, van olyan $y$ elem, amelyre 
$d(x,y)\le t$ és $d(x',y)\le t$; így nem tudjuk egyértelmûen rekonstruálni $x$-et, 
ha $y$ érkezik be.

(b,\thinspace c) Legyen $m=r+2$, és figyeljük meg, hogy 
$b^2$ $b$-áris $m$-esek egy halmazának elempárjai között a Hamming-távolság  
akkor és csak akkor $\ge m-1$, ha $m$ mélységû 
$b$-áris ortogonális mátrix\gyakindex{ortogonális mátrix = orthogonal array}
oszlopai alkotják a halmazt.
Lásd \cite{Golomb1964}\angolnevindex{Golomb, Solomon Wolf}\angolnevindex{Posner, Edward Charles (1933--1993)}.  
A kódelmélet \gyakindex{kódelmélet = coding theory} irodalmában 
gyakran jelölik a $d$ távolságú $C(b,n,r)$ kódot az $(n+r,b^n,d)_b$ 
szimbólummal. 
Így a $b$-áris $m$ mélységû ortogonális mátrix 
lényegében egy $(m,b^2,m-1)_b$ kód. 
\ujgyak\label{megold70-24} 
(a) Tegyük fel, hogy $x_ j\neq x'_j$, ha $1\le j\le l$ és $x_ j=x'_j$ $l<j\le N$. Ha $l=0$, akkor $x=x'$. 
Egyébként tekintsük azokat a paritás biteket, amelyek az 1 ponton átmenõ $m$ egyenesnek felelnek meg. Ezek közül a bitek 
közül legfeljebb $l-1$ felel meg azoknak az egyeneseknek, amelyek érintik a $\{2,\ldots,l\}$ pontokat. Így $x'$ legalább 
$m-(l{-}1)$-szer vált paritást, és $d(x,x')\ge l+(m-(l{-}1))=m+1$.

(b) Legyenek $l_{p1}$, \dots, $l_{pm}$ a $p$ ponton átmenõ egyenesek indexei. Az $y_1\ldots y_{N+R}$ üzenet fogadása után   
számoljuk ki $x_p$-t, ahol $1\le p\le N$, felhasználva az  $m+1$ $\{y_{p0},\ldots,y_{pm}\}$ tanú bit\gyakindex{tanú bit = witness bit}
többségi \gyakindex{többségi szabály = majority law} értékét, ahol $y_{p0} = y_p$ és 
$$y_{pk}=\textstyle\bigl(y\_{N+l_{pk}}+\sum\{y_j\mid\hbox{$j\neq p$ és a $j$ pont az $l_{pk}$ egyenesen 
fekszik}\}\bigr)\mod 2,\quad\hbox{ha $1\le k\le m$}\koz.$$ Ez a módszer mûködik, mert mindegyik $y_j$ fogadott bit 
legfeljebb egy tanú bitre hat.

Nézzük például a \ref{gyak70-19}. gyakorlatban a 25 pontos geometriát. 
Tegyük fel, hogy mindegyik kódszó $x_{26+5i+j}$ paritásbitje 
az $i$ sor $j$ egyenesének felel meg, ahol 
$0\le i\le5$ és $0\le j<5$; így 
$x_{26}=x_1\xor x_2\xor x_3\xor x_4\xor x_5$,
$x_{27}=x_6\xor x_7\xor x_8\xor x_9\xor x_{10}$, \dots,
$x_{55}=x_5\xor x_6\xor x_{12}\xor x_{18}\xor x_{24}$.
Adott $y_1\ldots y_{55}$ üzenet esetén, dekódoljuk az $x_1$ bitet (például) 
az alábbi hét érték többségének kiszámításával: $y_1$,
$y_{26}\xor y_2\xor y_3\xor y_4\xor y_5$,
$y_{31}\xor y_6\xor y_{11}\xor y_{16}\xor y_{21}$,
$y_{36}\xor y_{10}\xor y_{14}\xor y_{18}\xor y_{22}$,
$y_{41}\xor y_9\xor y_{12}\xor y_{20}\xor y_{23}$,
$y_{46}\xor y_8\xor y_{15}\xor y_{17}\xor y_{24}$,
$y_{51}\xor y_7\xor y_{13}\xor y_{19}\xor y_{25}$.
A 7.1.2. pont kifejti, hogyan lehet hatékonyan kiszámítani a többségi függvényeket. Figyeljük meg, hogy eltekinthetünk az utolsó 
10 bittõl, ha csupán két hibával bezárólag akarunk korrigálni, és az utolsó 20-tól, ha  elegendõ az 1-hiba javítás. Lásd 
\cite{Hsiao1970}.\angolnevindex{Hsiao@\string\Hsiao}\angolnevindex{Bossen, Douglas Craig}\angolnevindex{Chien@\string\Chien}
\ujgyak\label{megold70-25} 
Az $\{\texttt{l},\texttt{e},\texttt{a},\texttt{s},\texttt{t}\}$-bõl 
alkotott anagrammákat\gyakindex{anagramma = anagram} vizsgálva  
(lásd az 5-21. gyakorlatot), az alábbi négyzetet, valamint sorainak ciklikus permutációit kapjuk.
$$\vcenter{\baselineskip=8pt\tt\halign{&\kern.1em#\cr
s&t&e&l&a\cr
t&e&l&a&s\cr
e&l&a&s&t\cr
l&a&s&t&e\cr
a&s&t&e&l\cr}}\koz.$$
Itt a \texttt{telas} spanyolul szöveteket?? jelent;
az \texttt{elast} az elasztikus szó elõtagja; 
és a \texttt{laste} egy Chaucer-féle\angolnevindex{Chaucer, Geoffrey} ige felszólító módja. 
(Természetesen öt betû majdnem minden kiejthetõ kombinációja elõfordult valamikor a történelem során, 
mint valaminek valahol a jól vagy rosszul leírt neve.)
\vspace{-2mm}
\ujgyak\label{megold70-26} 
\idez{\texttt{every}
\texttt{night},
\texttt{young}
\texttt{video}
\texttt{buffs}
\texttt{catch}
\texttt{rerun}
\texttt{fever}
\texttt{forty}
\texttt{years}
\texttt{after}
\texttt{those}
\texttt{great}
\texttt{shows}
\texttt{first}
\texttt{aired}.}
Lásd \cite{Leighton1992}.
\angolnevindex{Leighton, Robert Erik}
\ujgyak\label{megold70-27} 
$(0,4,163,1756,3834)$, ha $k=(1,2,3,4,5)$;
\texttt{mamma} és \texttt{esses} \idez{full house}-t alkotnak\footnote{Pókerben. \textit{A fordító.}}.
\ujgyak\label{megold70-28} 
Igen, összesen 38 pár van. A \idez{legismertebb} megoldás a 
\texttt{needs} (180 a rangja) és \texttt{offer} (384 a rangja). 
Csak három esetben különböznek következetesen $+1$-gyel, 
(\texttt{adder} \texttt{beefs}, \texttt{sheer} \texttt{tiffs}, \texttt{sneer} \texttt{toffs}).
Más nevezetes példák a 
\texttt{ghost} \texttt{hints} és a 
\texttt{strut} \texttt{rusts}.
A párok közül az egyik szó az \texttt{s} betûvel végzõdik  
négy eset kivételével, mint például a \texttt{robed} \texttt{spade}. 
Lásd \cite{Gordon1990}.
\angolnevindex{Gordon, Leonard Joseph}
\ujgyak\label{megold70-29} 
18 palindroma van a \texttt{level}-tõl (184 a rangja) a 
\texttt{dewed}-ig (5688 a rangja). 
Néhány a 34 tükör pár közül:  
`\texttt{devil} \texttt{lived}',
`\texttt{knits} \texttt{stink}',
`\texttt{smart} \texttt{trams}',
`\texttt{faced} \texttt{decaf}'.
\ujgyak\label{megold70-30} 
A 105 ilyen SGB szó közül a leggyakoribbak  
\texttt{first},
\texttt{below},
\texttt{floor},
\texttt{begin},
\texttt{cells},
\texttt{empty}, és 
\texttt{hills}; 
\texttt{abbey} és 
\texttt{pssst} az elsõ illetve az utolsó lexikografikusan.
(Ha Ön nem szereti a
\texttt{pssst}-t, a következõ visszafelé 
a \texttt{mossy}.)
Csak 37 olyan szó van \texttt{mecca}-tól \texttt{zoned}-ig, 
amelyek betûi {\it fordított\/} sorrendben vannak; de ezek természetesen \texttt{rossz} (wrong) válaszok.
\ujgyak\label{megold70-31} 
A középsõ szó átlaga a másik kettõnek, így a szélsõ szavak kongruensek kell legyenek mod~2; 
ez a megfigyelés a szótár keresések számát egy nagyjából 32-es tényezõvel csökkenti. 
119 ilyen hármas van \texttt{WORDS}(5757)-ben, de \texttt{WORDS}(2000)-ben csak kettõ:
\texttt{marry}, \texttt{photo}, \texttt{solve}; \texttt{risky}, \texttt{tempo}, \texttt{vague}. Lásd \cite{McManus1992}.
\ujgyak\label{megold70-32} 
Úgy tûnik, hogy az egyetlen értelmes ismert példa a \texttt{peopleless}.
\ujgyak\label{megold70-33} 
\texttt{chief}, 
\texttt{fight},
\texttt{right},
\texttt{which},
\texttt{ouija},
\texttt{jokes},
\texttt{ankle},
\texttt{films},
\texttt{hymns},
\texttt{known},
\texttt{crops},
\texttt{pique},
\texttt{quart},
\texttt{first},
\texttt{first},
\texttt{study},
\texttt{mauve},
\texttt{vowel},
\texttt{waxes},
\texttt{proxy},
\texttt{crazy},
\texttt{pizza}.
(Az alapgondolat az, hogy keressük meg a legismertebb olyan szót, amelyikben 
$x$-et $(x+1)\mod26$ követi, ha $x=\texttt{a}$~(0), $x=\texttt{b}$~(1), \dots, $x=\texttt{z}$~(25).
Minimalizáljuk is a közbülsõ távolságot, így elõnyben részesítjük \texttt{bacon}-t 
a sokkal ismertebb \texttt{black}-kel szemben. Abban az egy esetben, ahol nincs ilyen szó, a \texttt{crazy} látszik a 
legértelmesebbnek. Lásd \cite{Morris1994})
\ujgyak\label{megold70-34} 
A felsõ kettõ (és az összes száma) mindegyik kategóriában: \texttt{pssst} és \texttt{pffft} (2),
\texttt{schwa} és \texttt{schmo} (2), \texttt{threw} és \texttt{throw} (36),
\texttt{three} és \texttt{spree} (5), \texttt{which} és \texttt{think} (709),
\texttt{there} és \texttt{these} (234), \texttt{their} és \texttt{great} (291),
\texttt{whooo} és \texttt{wheee} (3), \texttt{words} és \texttt{first} (628),
\texttt{large} és \texttt{since} (376), \texttt{water} és \texttt{never} (1313),
\texttt{value} és \texttt{radio} (84), \texttt{would} és \texttt{could} (460),
\texttt{house} és \texttt{voice} (101), \texttt{quiet} és \texttt{queen} (25),
\texttt{queue} csak (1), \texttt{ahhhh} és \texttt{ankhs} (4),
\texttt{angle} és \texttt{extra} (20), \texttt{other} és \texttt{after} (227),
\texttt{agree} és \texttt{issue} (20), \texttt{along} és \texttt{using} (124),
\texttt{above} és \texttt{alone} (92), \texttt{about} és \texttt{again} (58),
\texttt{adieu} és \texttt{aquae} (2), \texttt{earth} és \texttt{eight} (16),
\texttt{eagle} és \texttt{ounce} (8), \texttt{outer} és \texttt{eaten} (42),
\texttt{eerie} és \texttt{audio} (4), (0), \texttt{ouija} és \texttt{aioli} (2), (0), (0);
\texttt{years} és \texttt{every} a legismertebbek a 868 kihagyott szó közül.
A három lyuk kitöltésére internet\gyakindex{internet = Internet} 
használók javasolják az \texttt{ooops}, \texttt{ooooh}, és \texttt{ooooo} szavakat. 
Lásd \cite{Cohen1977}\angolnevindex{Cohen, Philip Michael}.
\ujgyak\label{megold70-35} 
Tekintsük a \texttt{WORDS}$(n)$ gyûjteményt $n=1$, 2, \dots, 5757 esetén.
Az \texttt{s}-bõl gyökerezõ szemléltetett vizsgálatot?? elõször akkor 
lehet megkapni, ha $n$ eléri a 978-at (a \texttt{stalk} rangját).  
A következõ olyan gyökér betû, amelyik ilyen próbálkozást lehetõvé tesz   
a \texttt{c}, amelyiknek elég sok elágazása van a leszármazottaiban, ha 
$n=2503$ (a \texttt{craze} rangja). 
A rákövetkezõ felbukkanás akkor következik be, ha $n=2730$ (\texttt{bulks}),
3999 (\texttt{ducky}),
4230 (\texttt{panty}),
4459 (\texttt{minis}),
4709 (\texttt{whooo}),
4782 (\texttt{lardy}),
4824 (\texttt{herem}),
4840 (\texttt{firma}),
4924 (\texttt{ridgy}),
5343 (\texttt{taxol}).

(Egy felbukkanás akkor következik be, ha a felsõ szintû vizsgálatok Horton\angolnevindex{Horton, Robert Elmer}--Strahler
\angolnevindex{Strahler, Arthur Newell} száma 4; lásd a 7.2.1.6. alpont 124. gyakorlatát.A szavaknak egy igen szórakoztató 
halmaza kerül elõ, amelyik a költészet\gyakindex{költészet = poetry} új formáját sugallja, ha az elágaztatás jobbról balra 
halad ahelyett, hogy balról jobbra menne:
\texttt{black},
\texttt{slack},
\texttt{crack},
\texttt{track},
\texttt{click},
\texttt{slick},
\texttt{brick},
\texttt{trick},
\texttt{blank},
\texttt{plank},
\texttt{crank},
\texttt{drank},
\texttt{blink},
\texttt{clink},
\texttt{brink},
\texttt{drink}.
Valójában a jobbról balra történõ elágaztatás teljes \textit{ternáris} vizsgálatot  
\gyakindex{teljes ternáris vizsgálat = complete ternary trie} eredményez 81 levéllel:
\texttt{males},
\texttt{sales},
\texttt{tales},
\texttt{files},
\texttt{miles},
\texttt{piles},
\texttt{holes},
\dots,
\texttt{tests},
\texttt{costs},
\texttt{hosts},
\texttt{posts}.)
\ujgyak\label{megold70-36} 
Jelöljük a kocka elemeit $a_{ijk}$-val, ha $1\le i,j,k\le5$, 
a szimmetria feltétele az, hogy $a_{ijk}=a_{ikj}=a_{jik}=a_{jki}=a_{kij}=a_{kji}$ legyen. 
Általában $n{\times}n{\times}n$ kockában $3n^2$ szó van,  
megkaphatjuk õket, ha két koordinátát rögzítünk, 
a harmadikat pedig az 1-tõl $n$-ig terjedõ tartományban engedjük változni.   
A szimmetria feltétel szerint azonban csak $n+1\choose2$ szóra van szükségünk. 
Így, ha $n=5$ a szükséges szavak 75-rõl 15-re redukálódnak. 
Grant\angolnevindex{Grant, Jeffrey Lloydd Jagton} képes volt 75 megfelelõ szót találni 
az {\sl Oxford English Dictionary-ban\gyakindex{szótár = dictionary}\/}; 
lásd \cite{Grant1978}.

Ha $(\texttt{stove},\texttt{event})$-t 
$(\texttt{store},\texttt{erect})$-ra, vagy 
$(\texttt{stole},\texttt{elect})$-ra változtatjuk, akkor két további adódik.    
\ujgyak\label{megold70-37} 
A gráf legsûrûbb része, amelyet a \idez{csupasz magjának} hívhatunk, 
tartalmaz két 25 fokú elemet, név szerint \texttt{bares}-t 
és \texttt{cores}-t.
\ujgyak\label{megold70-38} 
$\texttt{tears}\to\texttt{raise}\to\texttt{aisle}\to\texttt{smile}\koz$; 
a második szó lehet \texttt{reals} is. 
(A \texttt{tears} szótól \texttt{smile}-ig haladva, mint (\ref{keplet70-11})-ben      
Carroll\angolnevindex{Carroll, Lewis} egyik elsõ ötbetûs példája volt. 
Örömmel töltötte el az a felismerés, hogy a fordított szabály 
bonyolultabbá teszi az eljutást \texttt{smile}-tól \texttt{tears}-g, 
mert {\it négy\/} lépésre van szükség ebben az irányban.)
\ujgyak\label{megold70-39} 
Mindig feszítõ, sosem feszített.
\ujgyak\label{megold70-40} 
(a) $2^{\koz e}$, (b) $2^n$, $E$ vagy $V$ mindegyik részhalmaza esetén egy-egy. 
\ujgyak\label{megold70-41} 
(a) $n=1$ és $n=2$; $P_0$ definiálatlan. (b) $n=0$ és $n=3$.
\ujgyak\label{megold70-42} 
$G$-nek 65/2 éle van (ezért nem létezik).
\ujgyak\label{megold70-43} 
Igen: az elsõ három izomorf a \ref{abra70-2}.(e) ábrán lévõvel.
A bal oldali ábra valójában azonos a Petersen-gráf legkorábbi ismert nyomtatásban megjelent
alakjával: lásd \cite{Kempe1886}\angolnevindex{Kempe, Alfred Bray (1849--1922)}. 
A jobb oldali azonban kétségtelenül eltér tõle; 
ez síkba rajzolható\gyakindex{gráf = graph!síkba rajzolható gráf = planar graph}, 
Hamilton-gráf\gyakindex{gráf = graph!Hamilton-gráf = Hamiltonian graph}, és 4 a kerülete.
\gyakindex{gráf = graph!gráf kerülete = girth of a graph}
\ujgyak\label{megold70-44} 
Egy automorfizmus sarok pontot sarok pontba kell vigyen,
mert három különbözõ 2-hosszú út csak 
nem sarok pontok bizonyos párjai között található. 
Így a gráfnak csak $C_4$ nyolc szimmetriája van meg.  
\ujgyak\label{megold70-45} 
Ennek a gráfnak mindegyik éle olyan csúcsokat köt össze, 
amelyek ugyanabban a sorban, vagy szomszédos sorokban vannak. 
Így felváltva használhatjuk a 0 és a 2 színeket a páros sorszámú sorokban, 
az 1 és a 3 színeket pedig felváltva a páratlan sorszámú sorokban. 
Az \texttt{NV} szomszédai 5-hosszú kört alkotnak, ezért 
szükség van a négy színre. 
\ujgyak\label{megold70-46} 
(a) Mindegyik csúcs foka $\ge2$, és szomszédaiknak 
a bejövõ vonalaknak megfelelõen van egy jól definiált ciklikus sorrendje. 
Ha $u\adj v$ és $u\adj w$, ahol $v$ és $w$ $u$-nak ciklikusan 
egymás után következõ szomszédai, akkor $v\adj w$-nek is teljesülnie kell.  
Így mindegyik $u$ csúcs környékén az összes pont 
egy háromszög tartományhoz tartozik. \par
(b) A képlet érvényes, ha $n=3$. Ha $n>3$, 
húzzuk össze valamelyik 
élt\gyakindex{gráf = graph!gráf élének összehúzása = shrink any edge of a graph} az egyik végpontjához;
ez az átalakítás eltávolít egy csúcsot és három élt. 
(Ha $u\adj v$-t összehúzzuk, tegyük fel, hogy az 
$x\adj u\adj v\adj x$ és az $y\adj u\adj v\adj y$ háromszögek 
része volt. Ekkor megszûnik a $v$ csúcs, és az $\{x\adj v,u\adj v,y\adj v\}$
élek; a többi $w\adj v$ formájú élbõl $w\adj u$ él lesz.)
\ujgyak\label{megold70-47} 
Egy síkbeli ábra a síkot tartományokra osztaná,   
mindegyik tartomány határán 4 vagy 6 csúcs lenne 
($K_{3,3}$-nak ugyanis nincs páratlan köre). 
Ha $f_4$ és $f_6$ van a két fajtából, 
akkor $4f_4+6f_6=18$ kell legyen, 
így 9 él van; ebbõl $(f_4,f_6)=(3,1)$ vagy $(0,3)$.
$f_4+3f_6$ további él hozzáadásával háromszögesíthetnénk 
a gráfot; ekkor azonban legalább 15 éle lenne 
a \ref{gyak70-46}. gyakorlattal ellentmondásban.\par
Az a tény, hogy $K_{3,3}$ nem síkba rajzolható, visszanyúlik 
egy rejtvényig, amelyik arra vonatkozik, hogy 
három házat össze kell kötni három közmûvel\gyakindex{közmûvek = utilities} (víz, gáz és elektromosság) 
a vezetékek keresztezõdése nélkül.
\footnote{Három ház-három kút probléma. \textit{A fordító.}} 
A származása ismeretlen; {Dudeney}\angolnevindex{Dudeney, Henry Ernest (1857--1930)} 
\idez{õsréginek} nevezte \cite{Dudeney1913}. 
\ujgyak\label{megold70-48} 
Ha $u$, $v$, $w$ csúcsok és $u\adj v$, akkor $d(w,u)\not\equiv d(w,v)$ (modulo~2) 
fenn kell álljon; különben ugyanis $w$-tõl $u$-ig és $w$-tõl $v$-ig 
a legrövidebb utak páratlan kört eredményeznének.
Miután $w$-t 0-val színeztük, 
az eljárás így a $d(w,v)\mod2$ színt rendeli mindegyik 
nem színezett $v$ csúcshoz, amelyik szomszédos egy $u$ 
színezett csúccsal; és mindegyik $v$ csúcs, amelyikre $d(w,v)<\infty$  
színezve van, mielõtt egy új $w$ csúcsot választunk. 
\ujgyak\label{megold70-49} 
Csak három van: $K_4$, $K_{3,3}$, és \epsfxsize=14pt\epsfbox{\figdir/v4a.1615} (amelyik $\overline C_6$).
\ujgyak\label{megold70-50} 
A gráf összefüggõ kell legyen, mert $r$ komponens esetén a 3-színezések száma 
$3^r$-rel osztható. 
Ez a gráf a $K_{m,n}$ teljes kétrészes gráf része kell legyen, amelyik $3\koz(2^m+2^n-2)$-féle 
módon 3-színezhetõ. 
Ha $K_{m,n}$-bõl éleket törlünk, nem csökken?? a színezések száma;  
így $2^m+2^n-2\le8$, és azt kapjuk, hogy 
$\{m,n\}=\{1,1\}$, $\{1,2\}$, $\{1,3\}$, vagy $\{2,2\}$.
Így a lehetséges gráfok csupán a $K_{1,3}$ 
karom\gyakindex{gráf = graph!karom gráfban = claw in a graph} és a $P_4$ út.
\ujgyak\label{megold70-51} 
Egy $p_1\adj L_1\adj p_2\adj L_2\adj p_1$ 4-hosszú kör 
felelne meg két $\{L_1,L_2\}$ egyenesnek és két közös $\{p_1,p_2\}$ pontjaiknak,  
ami (ii)-nek ellentmond. Így a kerület  legalább 6. 

Ha párhuzamos egyeneseknek csak egy osztálya van, akkor a kerület $\infty$;
ha van két osztály $n\le n'$ elemmel, akkor 8 a kerület, vagy $\infty$, ha $n=1$. 
(Lásd a \ref{megold70-22}. megoldást.) Egyébként találhatunk 6-hosszú kört, ha három különbözõ osztályból 
választott egyenesbõl háromszöget készítünk. 
\ujgyak\label{megold70-52} 
Ha az átmérõ $d$ és a kerület $g$, akkor $d\ge\lfloor g/2\rfloor$, kivéve, ha $g=\infty$.
\ujgyak\label{megold70-53} 
A \texttt{happy} (amelyik össze van kötve a \texttt{tears} és a \texttt{sweat} szavakkal, 
de nincs összekötve a \texttt{world} szóval).
\ujgyak\label{megold70-54} 
(a) Ez egyetlen nagyon összefüggõ komponens. 
(Egyébként ez a gráf annak a kétrészes 
gráfnak\gyakindex{gráf = graph!kétrészes gráf = bipartite graph} 
a \textit{vonalgráfja}\gyakindex{gráf = graph!vonalgráf = line graph} 
amelyikben az egyik rész az 
$\{\texttt{A},\texttt{C},\texttt{D},\texttt{F},\texttt{G},\ldots,\texttt{W}\}$ 
kezdõbetûknek felel meg, 
a másik rész pedig a  
$\{\texttt{A},\texttt{C},\texttt{D},\texttt{E},\texttt{H},\ldots,\texttt{Z}\}$ 
utolsó betûknek.)

(b) A \texttt{WY} csúcs izolált. A többi nulla fokú csúcsok, nevezetesen az 
\texttt{FL},
\texttt{GA},
\texttt{PA},
\texttt{UT},
\texttt{WA},
\texttt{WI}, és a 
\texttt{WV} erõs komponenst képeznek saját magukkal; 
ezek mind megelõznek egy óriás komponenst, amelyiket pedig 
az összes többi egy csúcsú nulla ki-fokú erõs komponens követi: 
\texttt{AZ},
\texttt{DE},
\texttt{KY},
\texttt{ME},
\texttt{NE},
\texttt{NH},
\texttt{NJ},
\texttt{NY},
\texttt{OH},
\texttt{TX}.\par
(c) Most a $\{\texttt{GU}\}$ erõs komponens megelõzi $\{\texttt{UT}\}$-t;
\texttt{NH},
\texttt{OH},
\texttt{PA},
\texttt{WA},
\texttt{WI} és
\texttt{WV} összekötik az óriás erõs komponenst;
$\{\texttt{FM}\}$ megelõzi õt;
$\{\texttt{AE}\}$ és $\{\texttt{WY}\}$ pedig követi.
\ujgyak\label{megold70-55} 
${N\choose2}-{n_1\choose2}-\cdots-{n_k\choose2}$, ahol
$N=n_1+\cdots+n_k$.
\ujgyak\label{megold70-56} 
Igaz. Figyeljük meg, hogy $J_n$\gyakindex{gráf = graph!jén@$J_n$ = $J_n$} egyszerû, de nem 
tartozik semelyik multigráfhoz sem.
\ujgyak\label{megold70-57} 
Hamis az $u\rightarrow w\leftarrow v$ összefüggõ irányított gráfban.
(Azonban $u$ és $v$ akkor és csak akkor vannak 
ugyanabban az 
{\it{erõsen összefüggõ}\/}\gyakindex{gráf = graph!erõsen összefüggõ gráf = strongly connected graph} 
komponensben, ha $d(u,v)<\infty$ és $d(v,u)<\infty$; lásd a 2.3.4.2. alpontot)
\ujgyak\label{megold70-58} 
Mindegyik komponens egy kör, amelyik rendje legalább (a) 3 (b) 1.
\ujgyak\label{megold70-59} 
(a) $n$ szerinti indukcióval használhatjuk az 
egyszerû beszúró rendezést\gyakindex{egyszerû beszúró rendezés = straight insertion sorting}: 
Tegyük fel, hogy $v_1\rightarrow j\cdots\rightarrow v_{n-1}$. 
Ekkor vagy $v_n\rightarrow v_1$ vagy $v_{n-1}\rightarrow v_n$ 
vagy $v_{k-1}\rightarrow v_n\rightarrow v_k$, ahol $k$ a legkisebb olyan érték, 
melyre $v_n\rightarrow v_k$. 
Lásd \cite{Redei1934}.\angolnevindex{Rédei László (1900--1980)}

(b) 15: 01234, 02341, 02413, és a ciklikus eltoltjuk. Az ilyen irányított utak száma mindig páratlan; lásd 
\cite{Szele1943}\angolnevindex{Szele Tibor (1918--1955)}.

(c) Igen. (Indukcióval: Ha csak egy hely van a $v_n$ 
beszúrására, mint az (a) részben, akkor a verseny tranzitív.)
\ujgyak\label{megold70-60} 
Legyen $A=\{\koz x\mid u\rightarrow x\koz\}$,
                $B=\{\koz x\mid x\rightarrow v\koz\}$,
                $C=\{\koz x\mid v\rightarrow x\koz\}$. 
Ha $v\notin A$ és $A\cap B=\emptyset$, akkor $\vert A\vert+\vert B\vert
=\vert A\cup B\vert\le n-2$, mert $u\notin A\cup B$ és $v\notin A\cup B$.
De $\vert B\vert+\vert C\vert=n-1$; így $\vert A\vert<\vert C\vert$.
Lásd \cite{Landau1953}\angolnevindex{Landau, Hyman Garshin}. 
\ujgyak\label{megold70-61} 
$1\rightarrow 1$, $1\rightarrow 2$, $2\rightarrow 2$; ekkor $A={1\,1\choose 0\,1}$ 
és $A^k={1\,k\choose 0\,1}$ minden egész $k$ esetén.
\ujgyak\label{megold70-62} 
(a) Tegyük fel, hogy $\{1,\ldots,n\}$ csúcsok.
A permanens kifejtésében az $n!$ $a_{1p_1}\ldots a_{np_n}$ tag mindegyike 
azoknak a feszítõ permutációs digráfoknak a száma, 
amelyeknek van $j\rightarrow p_j$ irányított élük. 

(b) Hasonló érvelés  mutatja, hogy $\det A$-t úgy kapjuk, hogy 
a páros feszítõ permutációs digráfok számából 
kivonjuk a páratlanok számát. 
Lásd \cite{Harary1962}\angolnevindex{Harary, Frank (1921--2005)}, ahol a 
permutációs digráf neve 
\idez{lineáris részgráf}\gyakindex{gráf = graph!lineáris részgráf = linear subgraph}.
\ujgyak\label{megold70-63} 
Legyen $v$ valamelyik csúcs. Ha $g=2t+1$, akkor legalább $d(d-1)^{k-1}$ 
$x$ csúcs elégíti ki $d(v,x)=k$-t, ha $1\le k<t$. Ha $g=2t+2$ és $v'$ 
$v$-nek valamelyik szomszédja, akkor van legalább $(d-1)^t$ $x$ 
csúcs, amelyre $d(v,x)=t+1$ és $d(v',x)=t$.
\ujgyak\label{megold70-64} 
A \ref{megold70-63}. megoldásban az alsó határt elérve 
{\it mindegyik\/} $v$ csúcsnak $d$ kell legyen a fokszáma, 
és $v$ $d$ szomszédja mind szomszédos kell legyen a maradék 
$d-1$ csúccsal. Ez a gráf valójában a  $K_{d,d}$.
\gyakindex{gráf = graph!teljes bigráf = complete bigraph}
\ujgyak\label{megold70-65} 
(a) A \ref{megold70-63}. megoldás szerint $G$  $d$ fokú reguláris gráf kell legyen, 
és bármely két különbözõ csúcs között pontosan egy $\le 2$ hosszú út kell legyen.

(b) Feltehetjük, hogy $\lambda_1=d$, $x_1=(1\ldots1)^T$-tal. Az összes többi sajátvektor kielégíti $Jx_j=(0\ldots0)^T$-t; 
így $\lambda_j^2+\lambda\losub j=d-1$, ha $1<j\le N$.

(c) Ha $\lambda_2=\cdots=\lambda_m=(-1+\sqrt{4d{-}3}\koz\koz)/2$ és 
$\lambda_{m+1}=\cdots=\lambda_N=(-1-\sqrt{4d{-}3}\koz\koz)/2$, akkor $m-1=N-m$. 
Ezzel az értékkel azt kapjuk, hogy $\lambda_1+\cdots+\lambda_N=d-d^2\!/2$.

(d) Ha $4d-3=s^2$ és $m$ ugyanaz, mint (c)-ben, a sajátértékeket összeadjuk az alábbi értékig
$${s^2+3\over4}+(m-1){s-1\over2}-\Bigl({(s^2+3)^2\over 16}+1-m\Bigr)
                     {s+1\over2}\koz,$$
ami 15/32 plussz $s$-nek egy többszöröse. Így $s$ osztója kell legyen 15-nek.

(Ezt az eredményt Hoffman\angolnevindex{Hoffman, Alan Jerome} és Singleton\angolnevindex{Singleton, Robert Richmond}
kapták, lásd \cite{Hoffman1960}, ahol azt is bebizonyították, hogy  a $d=7$ értékre a gráf egyértelmû.)
\ujgyak\label{megold70-66} 
Jelöljük az 50 csúcsot $[a,b]$-vel és $(a,b)$-vel, ahol $0\le a,b<5$, és definiáljunk háromféle élt mod 5 aritmetikát használva: 
$$[a,b]\adj[a+1,b];\qquad
  (a,b)\adj(a+2,b);\qquad
  (a,b)\adj[a+bc,c],\quad\hbox{ha $0\le a,b,c<5$}.$$

(Lásd \cite{Brown1967a}\angolnevindex{Brown, William Gordon}. Az elsõ kétféle él nélkül a gráf kerülete 6, és megfelel az 
\ref{gyak70-51}. gyakorlatban lévõ geometriai hálónak, ha a \ref{megold70-19}. megoldás ortogonális mátrixát használjuk.)
\ujgyak\label{megold70-67} 
Bizonyos lehetõségeket kizárt Aschbacher, lásd \cite{Aschbacher1971}\angolnevindex{Aschbacher, Michael}. 
\ujgyak\label{megold70-68} 
Ha $G$-nek $s$ automorfizmusa\gyakindex{automorfizmus = automorphism} van, akkor $n!/s$ szomszédsági mátrixa van, 
mert $s$ darab $P$ permutációs mátrix\gyakindex{permutációs mátrix = permutation matrix} van, amelyre $P^-\!AP=A$.
\end{gyak}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\bibliography{KnuthMarcius30}
\bibliographystyle{infalg}
\begin{printindex}
\end{printindex}
\begin{printangolnevindex}
\end{printangolnevindex}
\begin{printnevindex}
\end{printnevindex}


\end{document}

