\documentclass[a4paper,10pt]{book}
\usepackage{KnuthMarcius30}
\usepackage{mycolortbl}

\makeindex

\renewcommand{\sfdefault}{ufu}

\setcounter{chapter}{7}
\setcounter{tocdepth}{4}
\setcounter{section}{5}
\setcounter{subsection}{1}
\setcounter{subsubsection}{3}
\setcounter{figure}{0}
\setcounter{equation}{0}
\setcounter{page}{1}
\setcounter{equation}{23}
\setcounter{figure}{2}


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%lk%
\def\figdir{abrak}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\dadj{\mathrel{\!\mathrel-\mkern-8mu\mathrel-\mkern-12mu\to\!}}

\hyphenation{lear-ning}

\newpage
\thispagestyle{empty}
\sf
\begin{center}
\vspace{3cm}


\huge

\textbf{Donald Ervin KNUTH}\angolnevindex{Knuth@\string\Knuth}

\huge

\vspace{48mm}

\textbf{A SZÁMÍTÓGÉP-PROGRAMOZÁS}

\vspace{15mm} 

\textbf{MÛVÉSZETE}

\vspace{32mm}

4. kötet  0. rész 

\vspace{6mm}

Bevezetés a kombinatorikai algoritmusokhoz és a Boole-függvényekhez

\vspace{38mm}
\Large


\vspace{6mm}
\textbf{Budapest, 2009} 
\end{center}



\hyphenation{}

\tableofcontents




\setcounter{equation}{23}
\medskip
\noindent \textbf{Irányított gráfok.} 
A 2.3.4.2. alpontban definiáltuk az \textit{irányított gráfok}\index{irányított gráf = 
directed graph}\index{irányított él = directed edge}  
fogalmát, amelyek nagyon hasonlítanak a gráfokhoz azt leszámítva, hogy élek helyett \textit{irányított élekkel} rendelkeznek. 
Az $u\rightarrow v$ irányított él az $u$ csúcsból a $v$ csúcsba fut, míg egy $u \adj v$
él azok megkülönböztetése nélkül köti össze az $u$ és $v$ csúcsot. 
Az irányított gráfok rendelkezhetnek még a csúcsokból önmagukba futó $v\rightarrow v$ hurkokkal, 
továbbá ugyanazon $u$ és $v$ csúcs között több $u\rightarrow v$ irányított él is futhat. 
 
Egy $n$-ed rendû $m$ méretû $D=(V,A)$ irányított gráf formálisan egy $n$ csúcsot tartalmazó
$V$ halmazból és egy $m$ rendezett $(u,v)$ párt tartalmazó $A$ multihalmazból áll, ahol
$u\in V$ és $v\in V$. A rendezett párokat irányított éleknek nevezzük, és 
$u\rightarrow v$ módon jelöljük, ha $(u,v)\in A$. Az irányított gráfot 
\textit{egyszerûnek}\inddef{egyszerû gráf = simple graph}\index{gráf = graph!egyszerû gráf = 
simple graph}\index{egyszerû gráf = simple graph \textit{lásd} gráf = graph} nevezzük, 
ha $A$ közönséges és nem multihalmaz, azaz ha minden $u$ és $v$ esetén legfeljebb 
egy $u\rightarrow v$ irányított él létezik. 
Minden $(u,v)$ irányított élnek $u$ a kezdõcsúcsa, $v$ pedig a 
végcsúcsa, amit az él \idez{hegyének} is nevezünk.
Egy $v$ csúcs $d^+(v)$ \textit{kifoka}\inddef{kifok = out-degree of a vertex} a csúcsból induló irányított élek száma,
míg annak $d^-(v)$ \textit{befoka}\inddef{befok = in-degree of a vertex} az oda beérkezõ, $v$ hegyû irányított élek száma. 
Egy 0 befokú csúcsot \idez{forrásnak}\inddef{source = forrás} nevezünk; egy 0 kifokú csúcsot pedig 
\idez{nyelõnek}.\inddef{nyelõ = sink} Vegyük észre, hogy $\sum_{v\in V}d^+(v)
=\sum_{v\in V}d^-(v)$, mivel mindkét összeg $m$-mel, az irányított élek teljes számával egyenlõ.

A gráfokhoz definiált fogalmak természetes módon átültethetõk irányított gráfokra
az \idez{irányított} jelzõ kitételével, amennyiben szükséges különbséget tenni az élek 
és irányított élek között. Így például az irányított gráfok irányított
részgráfjai lehetnek feszítõek, indukáltak vagy ezek egyike sem. 
Egy $D=(V,A)$ és $D'=(V',A')$ irányított gráf közötti izomorfizmus 
egy $V$-rõl $V'$-re ható kölcsönösen egyértelmû $\varphi$ leképezés,
amelyre a $D$-beli $u\rightarrow v$ irányított élek száma megegyezik 
a $D'$-beli $\varphi(u)\rightarrow\varphi(v)$ irányított élek számával minden $u,v\in V$ esetén.

Az irányított gráf ábrája egyszerû vonalak helyett nyilakat használ a csúcsok között.
A legegyszerûbb és legfontosabb $n$-ed rendû irányított gráfok a $K_n$, $P_n$ és $C_n$
gráfok irányított variánsai, vagyis 
a $K\orie_{\!n}$ \textit{tranzitív versenygráf},\inddef{tranzitív versenygráf = transitive tournament} 
a $P\orie_{\!n}$ \textit{irányított út}\inddef{irányított út = oriented path} és
a $C\orie_{\!n}$ \textit{irányított kör}.\inddef{irányított kör = oriented cycle} 
Ezek a gráfok vázlatosan a következõ ábrákkal rajzolhatók meg az $n=5$ esetben: \\

\begin{equation}\label{keplet70-24}
\begin{tabular}{ccc}
\epsfbox{\figdir/v4a.1610} \ ; \quad  & \quad  \epsfbox{\figdir/v4a.1611} \ ; \quad &  \quad \epsfbox{\figdir/v4a.1612}\koz . \\ \\
$K\orie_{5}$ & $P\orie_{5}$ & $C\orie_{5}$
\end{tabular}
\end{equation}

A $J_n$ \textit{teljes irányított gráf} a legnagyobb $n$-ed rendû egyszerû irányított gráf. Ennek $n^2$ számú $u\rightarrow v$ 
éle van, $u$ és $v$  minden lehetséges kiválasztásához egy.

A \ref{abra7-3}. ábra egy valamivel bonyolultabb, 17-ed rendû irányított gráf
ábráját mutatja, amelyet \idez{expressz-irányítottnak} is nevezhetünk: ezt az irányított
gráfot írja le Hercule Poirot Agatha Christie\angolnevindex{Christie, Agatha (1870--1976)} 
{\sl Gyilkosság az Orient expresszen} címû regényében \cite{Christie1934}. A csúcsok az 
Isztambul--Calais útvonalon közlekedõ kocsi fülkéit jelzik a történetben, 
egy $u\rightarrow v$ irányított él pedig azt, hogy az $u$ fülke lakója
megerõsíti a $v$ fülke lakójának alibijét. Ebben a példában hat összefüggõ
komponenst találunk, nevezetesen:
$\{0,1,3,6,8,12,13,14,15,16\}$,
$\{2\}$,
$\{4,5\}$,
$\{7\}$,
$\{9\}$ és
$\{10,11\}$,
mivel az irányított gráfbeli összefüggõség az irányított élek egyszerû élnek való tekintésével adódik.

\begin{figure}
\hangfig{\epsfbox{\figdir/ch7a.3}}
\small{JELMAGYARÁZAT: 
0 Pierre Michel, a francia kalauz; 1 Hercule Poirot, a belga detektív; 2 Samuel Edward Ratchett, a halott amerikai; 3 Caroline Martha Hubbard, az amerikai matróna; 
4 Edward Henry Masterman, a brit komornyik; 5 Antonio Foscarelli, az olasz autókereskedõ; 6 Hector MacQueen, az amerikai titkárnõ; 
7 Harvey Harris, a rejtõzködõ angol; 8 Hildegarde Schmidt, a német hölgy szobalánya; 9 (üres); 10 Greta Ohlsson, a svéd ápolónõ; 
11 Mary Hermione Debenham, az angol nevelõnõ; 12 Helena Maria Andrenyi, a gyönyörû grófnõ; 
13 Rudolph Andrenyi, a magyar gróf; 14 Natalia Dragomiroff, az orosz özvegy hercegnõ; 
15 Colonel Arbuthnot, a brit hivatalnok Indiából;
16 Cyrus Bettman Hardman, az amerikai detektív}
\normalsize
\caption{Az Agatha Christie által megrajzolt 17-ed rendû és 18 méretû irányítot gráf.\label{abra7-3}}
\end{figure}

Két irányított él \textit{egymást követõ}, ha az elsõ hegye a második kezdõcsúcsa. 
Egymást követõ irányított élek $(a_1,a_2,\ldots,a_k)$ sorozatát $k$ hosszúságú \textit{sétának} nevezzük;
a séta jelölése a csúcsok, valamint az irányított élek feltüntetésével történik:
\begin{equation}\label{keplet7-25}
\let\to=\longrightarrow
v_0\;\buildrel a_1\over\to\;
  v_1\;\buildrel a_2\over\to\; v_2\;\cdots\;
  v_{k-1}\;\buildrel a_k\over\to\; v_k. 
\end{equation}
Egy egyszerû irányított gráfban elég csupán a csúcsokat megadni; például $1\dadj0\dadj8\dadj14\dadj8\dadj3$ séta a 
\ref{abra7-3}. ábrán. A (\ref{keplet7-25})-ben szereplõ séta
egy irányított út, ha a $\{v_0,v_1,\ldots,v_k\}$ csúcsok különbözõek;
a séta egy irányított kör, ha a csúcsok a $v_k=v_0$ esettõl eltekintve különbözõek.

Egy irányított gráfban a $d(u,v)$ irányított távolság az $u$-ból $v$-be vezetõ 
legrövidebb \textit{irányított} út irányított éleinek a száma, ami megegyezik
az $u$-ból $v$-be vezetõ legrövidebb séta hosszával. Ez eltérhet a $d(v,u)$
értékétõl, de a (\ref{keplet7-18})-beli háromszög-egyenlõtlenség érvényben marad.

Minden gráf felfogható irányított gráfként, mivel egy $u \adj v$
él lényegében ekvivalens az $u\rightarrow v$ és $v\rightarrow u$ irányított élpárral.
\index{élek mint irányított élek = edges as arcs}
Az így elõálló irányított gráf rendelkezik az eredeti gráf minden tulajdonságával; 
például a gráf minden csúcsának foka az irányított gráf csúcsának kifoka és egyben befoka is lesz.
Megmaradnak továbbá a távolságértékek is.

Egy $(V,E)$ \textit{multigráf} hasonló egy gráfhoz attól eltekintve, hogy az $E$
élhalmaz $\{u,v\}$ párok tetszõleges \textit{multihalmaza} lehet; 
meg vannak engedve csúcsokból önmagukba futó $v \adj v$ hurokélek is, amelyek 
$\{v,v\}$ \idez{multipároknak}\index{multipár = multipair} felelnek meg. Például 
\begin{equation}
\epsfbox{\figdir/v4a.1613}\label{keplet7-26}
\end{equation}
egy 3-ad rendû, 6 éllel rendelkezõ multigráf, melynek élei: \index{párhuzamos (többszörös) élek = parallel (repeated) edges}
$\{1,1\}$, $\{1,2\}$, $\{2,3\}$, $\{2,3\}$, $\{3,3\}$ és $\{3,3\}$. A példában szereplõ csúcsok fokai $d(1)=d(2)=3$ és $d(3)=6$,
mivel minden hurok 2-vel járul az adott csúcs fokához. Egy $v \adj v$ hurokél \textit{két} irányított $v\rightarrow v$ 
hurokélre bomlik,\index{bevezetés a gráfelmélethez = introduction to graph theory} ha egy multigráfot irányított gráfnak tekintünk. 

\medskip
\noindent \textbf{Gráfok és irányított gráfok ábrázolása.}
Minden irányított gráf, így a gráf és multigráf is teljes mértékben leírható 
az $A=(a_{uv})$ \textit{szomszédsági mátrixszal}, melynek $n$ sora\index{szomszédsági mátrix = adjacency matrix} 
és $n$ oszlopa van $n$ csúcs esetén. A mátrix $a_{uv}$ eleme az $u$-ból $v$-be vezetõ irányított élek számát adja meg. 
Így például a $K\orie_{\!3}$, $P\orie_{\!3}$, $C\orie_{\!3}$, $J_3$ és (\ref{keplet7-26}) szomszédsági mátrixai rendre
\begin{equation}\label{keplet7-27}
\def\\#1#2#3#4#5#6#7#8#9{\Bigl(\,\vcenter{\eightrm\baselineskip8pt
        \hbox{#1#2#3}\hbox{#4#5#6}\hbox{#7#8#9}}\,\Bigr)}
K\orie_{\!3}=\\011001000,\enspace
P\orie_{\!3}=\\010001000,\enspace
C\orie_{\!3}=\\010001100,\enspace
J_3=\\111111111,\enspace
  A=\\210102024\koz.
\end{equation}

A mátrixelmélet hatékony matematikai eszközei lehetõvé teszik számos nem triviális 
gráfelméleti eredmény bizonyítását a szomszédsági mátrixok vizsgálatának segítségével;
a \ref{gyak7-65}. gyakorlat egy különösen frappáns példát mutat erre.
Ennek egyik fõ magyarázata, hogy a mátrixszorzásnak egy egyszerû interpretációja
létezik az irányított gráfok elméletében. Tekintsük az $A$ mátrix második hatványát, melynek
$u$-adik sorában és $v$-edik oszlopában álló eleme definíció szerint
\begin{equation}\label{keplet7-28}
(A^2)_{uv}\;=\;\sum_{w\in V} a_{uw}a_{wv}\koz.
\end{equation}
Mivel $a_{uw}$ az $u$-ból $v$-be futó élek száma, látható, hogy $a_{uw}a_{wv}$ az $u\rightarrow w\rightarrow v$ alakú séták száma.
Vagyis $(A^2)_{uv}$ az $u$-ból $v$-be vezetõ, 2 hosszúságú összes séta száma. Hasonlóan, $A^k$ elemei megadják az összes $k$ 
hosszúságú séta számát csúcsok bármely rendezett párjai között minden $k\ge 0$ esetén. 
Például a (\ref{keplet7-27})-ben szereplõ $A$ mátrixra
\begin{equation}\label{keplet7-29}
\def\\#1#2#3#4#5#6#7#8#9{\Bigl(\,\vcenter{\eightrm\baselineskip8pt
     \halign{\hbox to1em{\hfil##\hfil}&&\kern3pt\hbox to1em{\hfil##\hfil}\cr
              #1&#2&#3\cr #4&#5&#6\cr #7&#8&#9\cr}}\,\Bigr)}
  A=\\210102024,\qquad
  A^2=\\52225828{20},\qquad
  A^3=\\{12}9{12}9{18}{42}{12}{42}{96}\koz;
\end{equation}
12 darab 3 hosszúságú séta vezet a \ref{keplet7-26} multigráf 1. csúcsából a 3. csúcsába,
valamint 18 séta a 2. csúcsból önmagába.

A csúcsok átrendezése az $A$ szomszédsági mátrixot $P^-\!AP$-re módosítja, ahol $P$ egy permutációs mátrix (egy olyan $0$--1 
mátrix, melynek minden sorában és oszlopában pontosan egy 1-es áll), $P^-=P^T$ pedig az inverz permutáció mátrixa. Azaz
\begin{equation}
\def\\#1#2#3#4#5#6#7#8#9{\Bigl(\,\vcenter{\eightrm\baselineskip8pt
        \hbox{#1#2#3}\hbox{#4#5#6}\hbox{#7#8#9}}\,\Bigr)}
\\210102024,\quad
\\201042120,\quad
\\012120204,\quad
\\021240102,\quad
\\402021210\quad\hbox{és}\quad
\\420201012\label{keplet7-30}
\end{equation}
mindegyike a (\ref{keplet7-26}) szomszédsági mátrixai, továbbiak pedig nincsenek.

Több, mint $2^{n(n-1)/2}\!/n!$ darab $n$-ed rendû gráf létezik, ha $n>1$, és ezek majdnem mindegyike esetén $\Omega(n^2)$ 
adatbitre van szükség a leggazdaságosabb kódoláshoz. Ennek értelmében -- a memóriaigényt tekintve -- az összes lehetséges gráf döntõ 
többségénél a számítógépen való reprezentációjukhoz azok szomszédsági mátrixait célszerû használni. 

A gyakorlati problémák során felmerülõ gráfok azonban merõben eltérhetnek az összes lehetséges gráf közül véletlenszerûen 
kiválasztottaktól. Egy valós probléma gráfja általában \idez{ritka}, vagyis $\Omega(n^2)$helyett csak $O(n\lg n)$ 
élt tartalmaz, kivéve ha $n$ kicsi, mivel $\Omega(n^2)$ bitnyi adatot nehéz generálni. Tegyük fel például, hogy a csúcsok 
embereket, míg az élek barátságokat jelölnek. 5 milliárd embert tekintve keveseknek lesz 10000-nél több barátja. De még ha 
mindenkinek átlagosan 10000 barátja lenne is, a gráfnak csak $2.5\times 10^{13}$ éle lenne, miközben majdnem 
minden 5 milliárd csúcsú gráfnak körülbelül $6.25\times 10^{18}$ éle van.

Vagyis egy gráf számítógépen való reprezentációjának legjobb módja általában eltér az $n^2$ darab $a_{uv}$ érték szomszédsági 
mátrixelemként való tárolásától. Helyette, a Stanford GraphBase algoritmusok olyan adatstruktúrákat használnak, amelyek a 2.2.6. 
pontban tárgyalt ritka mátrixok láncolt reprezentációjával rokonok, bár azoknál valamivel egyszerûbbek. Ez a megközelítés nem 
csak sokoldalúnak és hatékonynak, hanem könnyen felhasználhatónak is bizonyult.

Egy irányított gráf SGB reprezentációja egy soros és egy láncolt helyfoglalás kombinálása csomópontok két alaposztályának 
felhasználásával. Egyes csomópontok csúcsokat, mások éleket reprezentálnak. (Létezik egy harmadik típusú csomópont is, amely az  
egész gráfot reprezentálja olyan algoritmusok számára, amelyek egyszerre több gráffal dolgoznak. Minden gráfhoz azonban csak 
egy gráfcsomópontra van szükség, így a csúcs- és élcsomópontok vannak túlsúlyban.)

A mûködési elv a következõ: minden $n$-ed rendû és $m$ méretû SGB irányított gráf $n$ csúcscsomópont egy soros tömbjére épül, 
egyszerûvé téve így a $k$-adik csúcs elérését, ahol $0\le k<n$. Ezzel szemben, az $m$ irányított élcsomópont egy általános,
alapvetõen strukturálatlan memóriaterületen keresztül kapcsolódik egymáshoz. Minden csúcscsomópont tipikusan 32 bájtot foglal 
és minden irányított élcsomópont 20 bájtot (a gráfcsomópont pedig 220 bájtot); de a csomópontok mérete egyszerûen módosítható.
\index{csomópont mérete = node size} A csomópontok néhány mezõjének rögzített, egyértelmû jelentése van minden esetben;
a kimaradó mezõk különbözõ célokra használhatóak a különbözõ algoritmusokban vagy egy adott algoritmus különbözõ fázisaiban. 
Egy csomópont rögzített célú részeit \idez{szabványos mezõknek}, a többcélú mezõit pedig \idez{segédmezõknek} nevezzük.

Minden csúcscsomópontnak van egy \texttt{NÉV} és egy \texttt{IRÁNYÍTOTT-ÉLEK} nevû szabványos mezõje. Ha $v$ egy csúcscsomópontra 
mutató változó, \textit{csúcsváltozónak} nevezzük. Ekkor a NÉV($v$) egy olyan karakterfüzérre mutat, amely a megfelelõ csúcsokat 
emberi szemlélet szerint azonosítja; például a (\ref{keplet7-17}) gráf 49 csúcsa a CA, WA, OR, \dots, RI nevekkel van ellátva.
A másik szabványos mezõ, az \texttt{IRÁNYÍTOTT-ÉLEK}, sokkal fontosabb az algoritmusokban: 
egy irányított élcsomópontra mutat, amely egy olyan $d^+(v)$ hosszúságú egyszeresen  
láncolt lista elsõ eleme, ahol a $v$ csúcsból kiinduló minden irányított élhez egy csomópont tartozik.

Minden irányított élcsomópontnak van egy \texttt{HEGY} és egy \texttt{KÖVETKEZÕ} nevû szabványos mezõje;
egy irányított élcsomópontra mutató $a$ változót \textit{irányítottél-változónak}\inddef{irányítottél-változó = arc variable} 
nevezünk. A \texttt{HEGY}($a$) az $a$ irányított él hegyét reprezentáló csúcscsomópontra mutat;
a \texttt{KÖVETKEZÕ}($a$) arra az irányított élcsomópontra mutat, amely a következõ irányított
élcsomópontot reprezentálja, melynek kezdõcsúcsa az $a$-éval megegyezik.

Egy 0 kifokú $v$ csúcs az \texttt{IRÁNYÍTOTT-ÉLEK}($v$)= $\Lambda$ (az üres mutató) módon reprezentálható. 
Más esetben, ha például a kifok 3, az adatstruktúra három irányított élcsomópontot tartalmaz, ahol
\texttt{IRÁNYÍTOTT-ÉLEK}($v$)=$a_1$, \texttt{KÖVETKEZÕ}($a_1$)=$a_2$,
\texttt{KÖVETKEZÕ}($a_2$)=$a_3$, és \texttt{KÖVETKEZÕ}($a_3$)=$\Lambda$; és a három irányított él $v$-bõl
\texttt{HEGY}($a_1$), \texttt{HEGY}($a_2$), \texttt{HEGY}($a_3$)-ba vezet.

Tegyük fel például, hogy ki akarjuk számolni a $v$ csúcs kifokát, és tárolni azt egy \texttt{KIFOK} nevû segédmezõben. Ez könnyû:
\begin{equation}\label{7-31}
\vcenter{\halign{#\hfil\cr
Legyen $a\leftarrow$\texttt{IRÁNYÍTOTT-ÉLEK}($v$) és $d\leftarrow 0$\koz.\cr
Amíg $a\neq \Lambda$, legyen $d\leftarrow d+1$ és $a\leftarrow$ \texttt{KÖVETKEZÕ}($a$)\koz.\cr
Legyen \texttt{KIFOK}($v$)$\leftarrow d$\koz.\cr}}
\end{equation}

Ha egy gráfot vagy multigráfot a fent tárgyalt módon irányított gráfnak tekintünk\index{\texttt{TÁRS} (az ellentétes irányú él) 
= \texttt{MATE} (the converse edge)}, annak minden $u \join v$ éle két, $u\rightarrow v$ és $v\rightarrow u$ éllel ekvivalens. 
Ezeket az irányított éleket \idez{társaknak} nevezzük, és két irányított élcsomópontot, például az $a$-t és $a'$-t tartalmazzák, 
ahol az $a$ az $u$-ból induló irányított élek, míg az $a'$ a $v$-bõl induló irányított élek listáján szerepel. 
Ekkor\index{társ = mate} \texttt{HEGY}($a$) = $v$ és \texttt{HEGY}($a'$) = $u$. Használjuk a
\begin{equation}\label{keplet7-32}
\texttt{TÁRS}(a)=a'\qquad\hbox{és}\qquad\texttt{TÁRS}(a')=a\koz,
\end{equation}
jelölést is olyan algoritmusokban, amelyek gyorsan át akarnak lépni egyik listáról a másikra. 
Általában nem szükséges azonban tárolnunk egy explicit mutatót egy irányított élrõl annak társára,
illetve egy \texttt{TÁRS} segédmezõt használnunk minden irányított élcsomóponton belül,
mivel egy okosan megtervezett adatstruktúra esetén a szükséges kapcsolat \textit{implicit} módon is levezethetõ.

Az implicit társ trükkje a következõképpen mûködik: egy nem irányított gráf vagy
multigráf $u \join v$ éleinek létrehozásakor \textit{egymást követõ} irányított élcsomópontokat
vezetünk be $u\rightarrow v$-re és $v\rightarrow u$-ra. Ha például minden irányított élcsomópont
20 bájton van tárolva, akkor minden új párra 40 egymást követõ bájtot foglalunk le.
Az elsõ bájt memóriacímét 8 többszöröseként állítsuk be. Ha ekkor az $a$ irányított élcsomópont 
az $\alpha$ memóriacímen található, akkor a társának a címe\index{bitszintû ÉS = bitwise AND}
\begin{equation}\label{keplet7-33}
\advance\abovedisplayskip-1pt
  \advance\belowdisplayskip-1pt
\Bigl\{\,\vcenter{\halign{$#\hfil$&\quad#\hfil\cr
\alpha+20,&ha $\alpha\mod8=0$\cr
\alpha-20,&ha $\alpha\mod8=4$\cr}}\,\Bigr\}\;=\;
\alpha-20+\bigl(40 \ \& \ ((\alpha \ \& \ 4)-1)\bigr)\koz.
\end{equation}

Az ilyen trükkök nagyon hasznosak olyan kombinatorikus problémákban, ahol
mûveletek trillióit kell végrehajtani, mivel ilyenkor a mûveletenkénti 3,6 nanomásodpercnyi 
megtakarítással a teljes számítás egy órával korábban véget ér. A (\ref{keplet7-33})
összefüggés azonban közvetlenül nem \idez{vihetõ át} az egyik implementációról a másikra. 
Ha például egy irányított gráfcsomópont mérete 20-ról 24-re változik, 
akkor a (\ref{keplet7-33})-beli 40, 20, 8 és 4 értékeket 48, 24, 16 és 8-ra kell módosítanunk.

A könyv algoritmusai nem tételeznek fel semmit a csomópontok méretérõl.
Ehelyett a C\index{C programozási nyelv = C language} programnyelv és annak leszármazottjai konvencióit
tekintjük, vagyis ha $a$ egy irányított élcsomópontra mutat, akkor `$a+1$' 
a memóriában ezt követõ irányított élcsomópontra vonatkozó mutatót jelöli.  
Általában\index{\texttt{HELY} = \texttt{LOC}}
\begin{equation}
\texttt{HELY}(\texttt{CSOMÓPONT}(a+k))\;=\;\texttt{HELY}(\texttt{CSOMÓPONT}(a))+kc\koz,\label{keplet7-34}
\end{equation}
ha minden irányított élcsomópontban $c$ bájt van. Hasonlóan, ha $v$ egy csúcs változó, `$v+k$' jelöli a $v$-t követõ 
$k$-adik csúcscsomópontot; a csomópont tényleges memóriacíme $v$ plusz $k$-szor egy csúcscsomópont mérete lesz.

Egy $g$ gráfcsomópont szabványos mezõi tartalmazzák az irányított élek \texttt{M}($g$) számát; a csúcsok \texttt{N}($g$) 
teljes számát; a csúcscsomópontok soros listájának elsõ csúcscsomópontjára mutató \texttt{CSÚCSOK}($g$) mutatót; 
a gráf \texttt{ID}($g$) azonosítóját, ami például egy \texttt{words}(5757,0,0,0) alakú karakterfüzér; továbbá bizonyos egyéb 
mezõket a memória lefoglalásához és újrahasznosításához a gráf növekedésekor vagy zsugorodásakor, vagy egy gráf külsõ formátumba 
való exportálásához, ami lehetõvé teszi a hozzáférést más felhasználók és gráfkezelõ rendszerek számára. Ezekre a gráfcsomópont 
mezõkre azonban ritkán kell majd hivatkoznunk, és itt nem lesz szükség az SGB formátum egy teljes leírásának megadására sem, 
mivel a fejezet majdnem minden gráfalgoritmusát a magyar nyelv egy meglehetõsen absztrakt szintjén fogjuk leírni ahelyett, 
hogy lehatolnánk a számítógépes programok bitszintû nyelvezetéhez.\index{irányított gráf = directed graph}

\medskip
\noindent \textbf{Egy egyszerû gráfalgoritmus.} Egy késõbb megjelenõ közepes-/magasszintû algoritmus szemléltetéseképpen
alakítsuk át a B tétel bizonyítását egy lépésrõl lépésre haladó
eljárássá, ami két színnel színezi egy adott gráf csúcsait, amennyiben az illetõ gráf páros.

\medskip
\noindent \textbf{B algoritmus} (\textit{párosság tesztelése}).
Egy SGB alakkal reprezentált gráf esetén\index{párosság tesztelése = bipartiteness testing} ez az algoritmus 
vagy egy 2-színezést készít, ahol \texttt{SZÍN}$(v)\in\{0,1\}$ minden $v$ csúcsra, vagy
sikertelenül befejezõdik, amennyiben nem lehetséges érvényes 2-színezés.
Itt a \texttt{SZÍN} egy segédmezõ minden csúcscsomópontban.
Egy másik, a \texttt{LÁNC($v$)} csúcssegédmezõ egy csúcsmutató az összes olyan színezett csúcs
egy vermének kezelésére, amelyek szomszédait még nem vizsgáltuk meg. 
Ennek a veremnek a tetejére egy $s$ csúcsváltozó mutat.
Az algoritmus használja még az $u$, $v$, $w$ változókat a csúcsokra, illetve
az $a$-t az irányított élekre. A csúcscsomópontokról feltesszük, hogy $v_0+k$ minden 
$0\le k<n$ esetén.\index{irányítottél-változó = arc variable}

\algbegin B algoritmus\label{alg7-B} (párosság tesztelése\inddef{B algoritmus = Algorithm B}). 

\algindentset{B1}
\algstep B1. (Kezdõértékek beállítása.) Legyen \texttt{COLOR}$(v_0+k)\leftarrow -1$ minden $0\le k<n$-re.
(Most az összes csúcs színezetlen.) Legyen $w\leftarrow v_0+n$.

\algstep B2. (Kész?) (Ezen a ponton minden $\ge w$ csúcs már színezett, így az összes színezett csúcs szomszédja is.) Az 
algoritmus sikeresen befejezõdik, ha $w=v_0$. Egyébként legyen $w\leftarrow w-1$, a következõ alacsonyabb indexû csúcscsomópont.

\algstep B3. ($w$ színezése, ha szükséges.) Ha \texttt{COLOR}$(w)\ge 0$, lépjünk vissza a B2-re. Egyébként legyen 
\texttt{COLOR}$(w)\leftarrow 0$, \texttt{LINK}$(w)\leftarrow \Lambda$ és $s\leftarrow w$.

\algstep B4. (Verem${}\Rightarrow u$.) Legyen $u\leftarrow s$, $s\leftarrow \texttt{LINK}(s)$,
$a\leftarrow\texttt{ARCS}(u)$. (Megvizsgáljuk a színezett $u$ csúcs minden szomszédját.)

\algstep B5. ($u$ kész?) Ha $a=\Lambda$, lépjünk a B8-ra. Egyébként legyen $v\leftarrow \texttt{TIP}(a)$.

\algstep B6. ($v$ feldolgozása.) Ha $\texttt{COLOR}(v)<0$, legyen $\texttt{COLOR}($v$)\leftarrow
1-\texttt{COLOR}(u)$, $\texttt{LINK}(v)\leftarrow s$, és $s\leftarrow v$.
Egyébként, ha $\texttt{COLOR}(v)=\texttt{COLOR}(u)$, fejezzük be sikertelenül az algoritmust.

\algstep B7. (Ciklus $a$-ra.) Legyen $a\leftarrow\texttt{NEXT}(a)$, és lépjünk vissza B5-re.

\algstep B8. (A verem nem üres?) Ha $s\neq \Lambda$, lépjünk vissza B4-re. Egyébként lépjünk B2-re.\quad\slug

\smallskip\noindent
Ez az algoritmus a \idez{mélységi bejárás}\index{mélységi keresés = depth first search} nevû általános gráfbejáró algoritmus 
egy változata, amelyet majd a 7.4.1. pontban tárgyalunk részletesen. 
Ennek $m$ irányított él és $n$ csúcs esetén a futási ideje $O(m+n)$
(lásd a \ref{gyak7-70}. gyakorlatot); vagyis jól alkalmazható a szokásos ritka gráfok esetére. 
Kisebb módosításokkal sikertelen befejezõdés esetén egy páratlan hosszúságú 
kört is létrehozhatunk kimenetként, ezzel bizonyítva a 2-színezés lehetetlenségét
(lásd a \ref{gyak7-72}. gyakorlatot).\index{irányított él = arc}

\medskip
\noindent \textbf{Példák gráfokra.}
A Stanford GraphBase\index{Stanford GraphBase = Stanford GraphBase} tartalmaz egy könyvtárat, amelyben több, mint három 
tucat elõállító eljárás van, amelynek segítségével gráfok és irányított gráfok számos változata készíthetõ el kísérleti céllal.
A \textit{worda} eljárásról már beszéltünk, tekintsünk át most néhány további eljárást a lehetõségek megismerésének céljából.

\smallskip$\bullet$
{\it roget}$(1022,0,0,0)$ egy irányított gráf 1022 csúccsal és
5075 irányított éllel. A csúcsok szavak és fogalmak kategóriáit reprezentálják, 
amelyeket Roget\angolnevindex{Roget, Peter Mark (1779--1869)} \cite{Roget1879} vezetett be 
híres XIX. századbeli mûvében. Az irányított élek a könyvben fellelhetõ kategóriák közötti kereszthivatkozások. 
Tipikus irányított élek például: $\texttt{water (víz)}\rightarrow\texttt{moisture (nedvesség)}$,
$\texttt{discovery (felfedezés)}\rightarrow\texttt{truth (igazság)}$, 
$\texttt{preparation (elõkészítés)}\rightarrow\texttt{lear-}$ $\texttt{ning (tanulás)}$,
$\texttt{vulgarity (közönségesség)}\rightarrow\texttt{ugliness (rútság)}$,
$\texttt{wit (szelle-}$ $\texttt{messég)}\rightarrow\texttt{amusement (szórakozás)}$.

\smallskip$\bullet$
\textit{book}$(\texttt{"jean"},80,0,1,356,0,0,0)$ egy gráf 80 csúccsal és 254 éllel. A csúcsok Victor Hugo \cite{Hugo1862}
{\sl Nyomorultak} címû regényének szereplõit reprezentálják; az élek azokat a szereplõket kötik össze, akik találkoznak egymással. 
Tipikus élek: $\texttt{Fantine} \adj \texttt{Javert}$, \ $\texttt{Cosette} \adj \allowbreak \texttt{Th\'enardier}$.

\smallskip$\bullet$
\textit{bi\_book}$(\texttt{"jean"},80,0,1,356,0,0,0)$ egy páros gráf $80+356$ csúccsal és 727 éllel. A csúcsok a 
{\sl Nyomorultak} szereplõit vagy fejezeteit reprezentálják; az élek a szereplõket azokkal a fejezetekkel kötik össze, amelyekben 
megjelennek (például $\texttt{Napoleon} \adj \texttt{2.1.8}$, \ $\texttt{Marius} \adj \texttt{4.14.4}$).

\smallskip$\bullet$
\textit{plane\_miles}$(128,0,0,0,1,0,0)$ egy síkgráf 129 csúccsal és 381 éllel. A csúcsok az Egyesült Államok és Kanada 128 
városát reprezentálják, plusz egy speciális \texttt{INF} csúcsot, a \idez{végtelen távoli pont} csúcsot. Az élek a városok 
ún. \textit{Delaunay-féle háromszögelését}\angolnevindex{Delanuay, Borisz Nyikolajevics (({\rus Delone, Boris 
Nikolaevich})}\index{Delaunay-féle háromszöggelés = Delaunay triangulation} 
definiálják a síkon a szélességi és hosszúsági koordináták alapján; ez azt jelenti, 
hogy $u \adj v$ pontosan akkor, ha az $u$-n és $v$-n áthaladó legkisebb kör belseje nem tartalmaz más csúcsot. További élek 
futnak az \texttt{INF} és minden olyan csúcs között, amelyek az összes város helyének konvex burkán helyezkednek el. Tipikus élek: 
$\texttt{Seattle, WA} \adj \texttt{Vancouver, BC} \adj \texttt{INF}$; \ $\texttt{Toronto, ON} \adj \texttt{Rochester, NY}$.

\smallskip$\bullet$
\textit{plane\_lisa}$(360,250,15,0,360,0,250,0,0,2295000)$ egy síkgráf 3027 csúccsal és 5967 éllel. Ez a gráf Leonardo da Vinci 
\cite{Leonardo1506} {\sl Mona Lisa} címû festményének digitalizált képével kapható meg, amelynek 360 sora és 250 oszlopa van,
továbbá a képpontok intenzitásaihoz a szürke 16 árnyalatát használjuk 0 (fekete) és 15 (fehér) között. Az eredményül kapott 
3027 vízszintesen/függõlegesen összefüggõ konstans intenzitású tartomány szomszédosnak tekintendõ, ha van közös határpontjuk. 
(Lásd a 4.7. ábrát.)

\begin{figure}[t!]
\begin{center}
\resizebox{6cm}{!}{\includegraphics{lisa16}} 
\end{center}
\caption{A {\sl Mona Lisa} egy digitális változata és annak egy kinagyított részlete (messzebbrõl nézve jobban látható).}
\end{figure}

\smallskip$\bullet$
\textit{bi\_lisa}$(360,250,0,360,0,250,8192,0)$ egy páros gráf $360+250=610$ csúccsal és 40923 éllel. Ez szintén Leonardo híres 
festményébõl származtatható, ezúttal azokat a sorokat és oszlopokat összekötve, amelyekben az intenzitás legalább $1/8$. Ilyen 
például a közvetlenül Lisa\index{Gherardini, Lisa = Gherardini, Lisa} \idez{mosolyának} közepén megjelenõ 
$\texttt{r102} \adj \texttt{c113}$ él.

\smallskip$\bullet$
\textit{raman}$(31,23,3,1)$ egy, az elõzõ példákban szereplõ SGB gráfoktól eltérõ típusú gráf. A nyelvhez, irodalomhoz vagy az 
emberi kultúra más eleméhez való kötõdés helyett, ez egy úgy nevezett\index{Ramanujan-féle expanergráf = Ramanujan expander graph} 
\idez{Ramanujan expander gráf},\angolnevindex{Ramanujan, Iyengar Srinivasa (1887--1920)} ami szigorú matematikai elveken alapul. 
Mind a $(23^3-23)/2=6072$ csúcsa 32 fokszámú; azaz \index{reguláris gráf = regular graph} 97152 éle van. A csúcsok olyan 
$2\times 2$-es mátrixok ekvivalenciaosztályaira vonatkoznak, amelyek nem szingulárisak modulo 23; egy tipikus él a 
$\texttt{(2,7;1,1)} \adj \texttt{(4,6;1,3)}$. A Ramanujan-gráfok fõleg azért fontosak, mivel szokatlanul nagy kerületük és kis 
átmérõjük van a méretükhöz és fokszámukhoz képest. A példagráfnak 4 a kerülete és 4 az átmérõje.

\smallskip$\bullet$
\textit{raman}$(5,37,4,1)$, hasonlóan az elõzõhöz, egy 6-od fokú reguláris gráf 
50616 csúccsal és 151848 éllel. A kerülete 10, az átmérõje 10 és szintén páros gráf.

\smallskip$\bullet$
\textit{random\_graph}$(1000,5000,0,0,0,0,0,0,0,s)$ egy gráf 1000 csúccsal, 5000 éllel és $s$ maggal. Ennek \idez{megalkotása} 
élek nélkül kezdõdik, miután ismétlõdõen pszeudo-véletlen csúcsindexeket választunk $0\le u,v<1000$ szerint,
és felvesszük az $u \join v$ élt, hacsak $u=v$ nem teljesül, vagy az él már jelen van.
Ha $s=0$, akkor a 908-as izolált csúcs kivételével minden csúcs egy 999-ed rendû óriás komponenshez tartozik.

\smallskip$\bullet$
\textit{random\_graph}$(1000,5000,0,0,1,0,0,0,0,0)$ egy hasonló módon kialakuló irányított gráf 1000 csúccsal és 5000 
irányított éllel. (Valójában minden irányított éle egyúttal a\index{irányított gráf = directed graph!véletlen 
irányított gráf = random directed graph}\index{irányított gráf = directed graph} 
\textit{random\_graph}$(1000,5000,0,0,0,0,0,0,0,0)$ gráfnak is része.)

\smallskip$\bullet$
\textit{subsets}$(5,1,-10,0,0,0,\Hex1,0)$ egy gráf ${11\choose5}=462$ csúccsal, a $\{0,1,\ldots,10\}$ minden öt elemû
részhalmazához eggyel. Két csúcs szomszédos, ha a megfelelõ részhalmazok diszjunktak; vagyis, a gráf reguláris 
6-odfokú 1386 éllel. Felfoghatjuk úgy is, mint a Petersen-gráf\index{Petersen-gráf = Petersen graph} egy általánosítását, 
amelynek SGB neve {\it részhalmazok}$(2,1,-4,0,0,0,\Hex1,0)$.

\smallskip$\bullet$
\textit{subsets}$(5,1,-10,0,0,0,\Hex{10},0)$ gráfnak ugyanaz a 462 csúcsa van, de ezek most akkor szomszédosak, ha 
a megfelelõ részhalmazoknak négy közös eleme van. Ez egy reguláris 30-ad fokú gráf 6930 éllel.

\smallskip$\bullet$
\textit{parts}$(30,10,30,0)$ egy másik matematikai alapú gráf. 3590 csúcsa van, minden 30 elem legfeljebb 10 osztályba való 
felosztásához egy. Két felosztás szomszédos, ha az egyik a másik egy részének továbbosztásából származik; ez a szabály 31377 
élt definiál. A \textit{parts}$(30,10,30,1)$ irányított gráf hasonló, de ennek 31377, a rövidebb felosztásoktól a hosszabbak 
felé mutató irányított éle van (például $\texttt{13+7+7+3}\rightarrow\texttt{7+7+7+6+3}$).

\smallskip$\bullet$
\textit{simplex}$(10,10,10,10,10,0,0)$ egy gráf 286 csúccsal és 1320 éllel. A csúcsai az $x_1+x_2+x_3+x_4=10$ $(x_i\ge 0)$ 
egyenlet egész megoldásai, azaz a \idez{10-es számnak négy nemnegatív egész összegére való felbontása}; a csúcsok egy tetraéder
belsejébe esõ pontok baricentrikus koordinátáinak is tekinthetõk. Az élek, mint például a $\texttt{3,1,4,2} - \texttt{3,0,4,3}$, 
az egymáshoz lehetõ legközelebb esõ felosztásokat kötik össze.

\smallskip$\bullet$
\textit{board}$(8,8,0,0,5,0,0)$, illetve {\it tábla}$(8,8,0,0,-2,0,0)$ olyan 64 csúcsú gráfok, amelyek 168, illetve 280 
élei a sakkjáték huszárjának, illetve futójának lehetséges lépéseihez tartoznak.

\smallskip\noindent
Az SGB gráfgenerátorok paramétereinek variálásával tömérdek további példa nyerhetõ.
A \ref{abra7-5}. ábra\index{háromszögháló = triangular grid} például a \textit{board} és a \textit{simplex} két 
egyszerû változatát mutatja; a \textit{board} valamelyest rejtett szabályait a \ref{gyak7-75}. gyakorlat tárja fel.

\begin{figure}[!t]
\begin{center}
\begin{tabular}{cc}
\epsfig{file=ch7a.50,width=5cm} & \epsfig{file=ch7a.51,width=5cm} \\
\small \textit{board}$(6,9,0,0,5,0,0)$ & \small \textit{simplex}$(10,8,7,6,0,0,0)$ \\
\small (Huszárlépések egy $6\times 9$-es sakktáblán) & \small (Egy csonkolt háromszögháló)
\end{tabular}
\caption{Példák táblajátékokhoz kapcsolódó SGB-gráfokra.\label{abra7216-40}}
\end{center}
\vspace{-4mm}
\end{figure} 



 
\medskip
\noindent \textbf{Gráfalgebra.}
Új gráfokat úgy is nyerhetünk,\index{gráfalgebra = algebra of graphs} hogy már meglévõ gráfokon hajtunk végre mûveleteket.
Ha például $G=(V,E)$ egy tetszõleges gráf, annak $\overline G=(V,\overline E)$ \textit{komplementere} az 
\begin{equation}\label{keplet7-35}
\hbox{$u \adj v$ a $\overline G$-ben}\qquad\iff\qquad
  \hbox{$u\neq v$ a $u \nadj v$ $G$-ben}
\end{equation}
módon nyerhetõ. Vagyis a nem-élek élekké válnak, és fordítva. Vegyük észre, hogy $\overline{\overline G}=G$\index{nullgráf = 
null graph}, és a $\overline{K_n}$ gráfnak nincsenek élei. A kapcsolódó $A$ és $\overline A$ szomszédsági mátrixokra
\begin{equation}\label{keplet7-36}
A+\overline A = J-I
\end{equation}
teljesül, ahol $J$ a csupa 1-esekbõl álló mátrix, $I$ az egységmátrix,
vagyis $J$, illetve $J-I$ a $J_n$, illetve $K_n$ szomszédsági mátrixai $n$-ed rendû $G$ esetén.

Továbbá, minden $G=(V,E)$ gráf egy $L(G)$ \textit{élgráfhoz}\index{élgráf = line graph}\index{gráf = graph!élgráf = line graph} 
vezet, amelynek csúcsai az $E$ élek; két él szomszédos $L(G)$-ben, ha van közös csúcsuk. Így például az $L(K_n)$ élgráfnak 
$\binom{n}{2}$ csúcsa van, és reguláris $2n-4$-ed fokú, ha $n\ge 2$ (lásd a \ref{gyak7-82}. gyakorlatot).
Egy gráf \textit{k-él-színezhetõ},\index{káél@$k$-élszínezhetõ gráf = $k$-edge colorable graph} ha a élgráfja $k$-színezhetõ.

Adott $G=(U,E)$ és $H=(V,F)$ gráf esetén azok $G\cup H$ \textit{uniója}\inddef{gráfok uniója =union of graphs} az az 
$(U\cup V,E\cup F)$ gráf, amelyet a csúcsok és élek egyesítésével kapunk. Tegyük fel például, hogy a $G$, illetve a $H$ gráf 
a sakkjáték bástya-, illetve futólépésének megfelelõ gráf; ekkor $G\cup H$ a vezérlépésnek megfelelõ gráf, amelynek 
hivatalos SGB neve\index{tábla = board}\index{\textit{gunió} = \textit{gunion}}
\begin{equation}\label{keplet7-37}
\hbox{\textit{gunion}}(\hbox{\textit{board}}(8,8,0,0,-1,0,0),
\hbox{\textit{board}}(8,8,0,0,-2,0,0),0,0)\koz.
\end{equation}

Abban a speciális esetben, amikor a csúcsok $U$ és $V$ halmazai diszjunktak, a $G\cup H$ unió nem követeli meg a csúcsok 
bármilyen szokásos kereszthivatkozásán keresztüli azonosítását; a $G\cup H$ ábráját egyszerûen megkaphatjuk a $G$, majd 
a $H$ ábrájának megrajzolásával. Ezt a speciális esetet \idez{egymás mellé helyezésnek}
\index{gráfok egymás mellé helyezése, \textit{lásd} gráfok direkt összege = juxtaposition of graphs, \see direct sum of graphs} 
vagy a $G$ és a $H$ \textit{direkt összegének}\inddef{gráfok direkt összege = direct sum of graphs} nevezzük, és 
$G\dirsum H$-val fogjuk jelölni. Könnyen látható például, hogy
\begin{equation}\label{keplet7-38)} 
K_m\dirsum K_n \cong \overline{K^{\vphantom y}_{m,n}}\koz,
\end{equation}
és hogy minden gráf az összefüggõ komponenseinek direkt összege.

A (\ref{keplet7-38}) képlet speciális esete a 
\begin{equation}
K_{n_1}\dirsum K_{n_2}\dirsum\cdots\dirsum K_{n_k} \cong
\overline{K^{\vphantom y}_{n_1,n_2,\ldots,n_k}}\label{keplet7-39}
\end{equation}
összefüggésnek, amely teljes $k$-részes gráfokra teljesül, ha $k \ge 2$.
(\ref{keplet7-39}) viszont $k=1$-re egy botrányos tény miatt nem áll fenn:
a teljes gráfok szabványos gráfelméleti jelölése nem konzisztens. 
Valóban, $K_{m,n}$ egy teljes 2-részes gráfot jelöl, viszont $K_n$ \textit{nem} jelöl egy teljes 1-részes 
gráfot. A gráfelméleti szakemberek valahogyan már évtizedek óta együtt tudnak élni ezzel az anomáliával
anélkül, hogy belebolondulnának.

A $G$ és $H$ diszjunkt gráfok kombinálásának egy másik fontos módja azok $G \join H$ 
\textit{összekapcsolásának}\inddef{gráfok összekapcsolása = join of graphs}\index{gráf = graph!gráfok összekapcsolása = join of graphs} 
elkészítése, ami $G\dirsum H$-ból, valamint az összes $u - v$ élbõl áll, ahol $u\in U$ és $v\in V$ 
{lásd Zykov\angolnevindex{Zykov, Alekszander Alekszandrovics ({\rus Zykov, Aleksandr Aleksandrovich})} cikkét \cite{Zykov1949}}. 
Továbbá, ha $G$ és $H$ diszjunkt {\it irányított gráfok}, a $G\rightarrow H$
\textit{irányított egyesítésük} hasonló, ami azonban a $G\dirsum H$-t csak az 
$U$-ból $V$-be tartó $u\rightarrow v$ egyirányú élekkel egészíti ki.

Az $A$ és $B$ mátrix direkt összege a $B$ halmaz $A$ halmaztól átlósan jobbra és
le való elhelyezésével készíthetõ el:
\begin{equation}
A\oplus B = 
\begin{pmatrix}
A & O\cr O & B
\end{pmatrix}\koz,
\label{keplet7-40}
\end{equation}
ahol a példában minden $O$ a csupa nullából álló halmazt jelöli, amelynek
az adott helyen megkövetelt számú sora és oszlopa van. 
Egyszerû megjegyezni a gráfok direkt összegére használt $G\dirsum H$ jelölést,
mivel a $G\dirsum H$ szomszédsági mátrixa pontosan megegyezik a 
$G$, illetve $H$ gráf $A$, illetve $B$ szomszédsági mátrixának direkt összegével.
Hasonlóan, a $G\join H$, $G\rightarrow H$ és $G\leftarrow H$ szomszédsági mátrixai rendre
\begin{equation}
A\join B =
\begin{pmatrix}
A & J \cr J & B
\end{pmatrix},\qquad
A\rightarrow B = 
\begin{pmatrix}
A & J \cr O & B
\end{pmatrix},\qquad
A\leftarrow B = 
\begin{pmatrix}
A & O \cr J & B\label{keplet7-41}
\end{pmatrix}\koz,
\end{equation}
ahol a $J$ (\ref{keplet7-36})-hoz hasonlóan csupa 1-esekbõl álló mátrix. Ezek a mûveletek asszociatívak, és 
kapcsolódnak a komplementerképzéshez:
\begin{equation}
A\dirsum(B\dirsum C)=(A\dirsum B)\dirsum C,\qquad
   A\join(B\join C)=(A\join B)\join C; \label{keplet7-42}
\end{equation}
\vspace{-4mm}
\begin{equation}
A\rightarrow(B\rightarrow C)=(A\rightarrow B)\rightarrow C,\qquad
   A\leftarrow(B\leftarrow C)=(A\leftarrow B)\leftarrow C\koz;\label{keplet7-43}
\end{equation}
\vspace{-2mm}
\begin{equation}
\overline{A\dirsum B}=\overline A\join\overline B,\qquad
  \overline{A\join B}=\overline A\dirsum\overline B\koz;\label{keplet7-44}
\end{equation}

\vspace{-2mm}
\begin{equation}
\overline{A\rightarrow B}=\overline A\leftarrow\overline B,\qquad
  \overline{A\leftarrow B}=\overline A\rightarrow\overline B\koz;\label{keplet7-45}
\end{equation}
\vspace{-2mm}
\begin{equation}
(A\dirsum B)+(A\join B)\;=\;(A\rightarrow B)+(A\leftarrow B)\koz.\label{keplet7-46}
\end{equation}
Vegyük észre, hogy a (\ref{keplet7-39}), (\ref{keplet7-42}) és (\ref{keplet7-44}) összevonásával
\begin{equation}\label{keplet7-47}
K_{n_1,n_2,\ldots,n_k}\;=\;\,\overline{\!K_{n_1}}\join
\,\overline{\! K_{n_2}}\join
\,\cdots\,\join\,\overline{\!K_{n_k}}
\end{equation}
adódik, amikor $k\ge 2$. Továbbá,\index{tranzitív verseny = transitive tournament}
\index{Knir@$K_n\hspace{-1.6mm}\vec{} \ = K_n\hspace{-1.6mm}\vec{} \hspace{1.5mm}$}
\begin{equation}
K_n=K_1\join K_1\join \, \cdots \, \join K_1\quad\hbox{és}\quad
K\orie_{\!n}=K_1\rightarrow K_1\rightarrow\cdots\rightarrow K_1\koz,\label{keplet7-48}
\end{equation}
a $K_1$ gráf $n$ példányát használva, ami azt mutatja, hogy $K_n=K_{1,1,\ldots,1}$ egy teljes $n$-részes gráf.

A direkt összegek és egyesítések hasonlóan viselkednek az összeadásra, mivel
$\,\overline{\!K_m}\dirsum\,\overline{\!K_n}=
\,\overline{\!K_{m+n}}$ és
$K_m\join K_n=K_{m+n}$. A gráfokat kombinálhatjuk algebrai mûveletekkel is,
amelyek a szorzáshoz hasonlóak. 
A \textit{Descartes-szorzat}\inddef{Descartes-szorzat = Cartesian product} mûvelet például az $m$-ed rendû $G=(U,E)$
és $n$-ed rendû $H=(V,F)$ gráfból egy $mn$-ed rendû $G\cprod H$ gráfot állít elõ.
A $G\cprod H$ csúcsai $(u,v)$ alakú rendezett párok, ahol
$u\in U$ és $v\in V$; az élek 
$(u,v) \join (u',v)$ alakúak, ha $u \join u'$ a $G$-be esik, valamint 
$(u,v) \join (u,v')$ alakúak, ha $v \join v'$ a $H\!$-ba esik. Más szóval, 
$G\cprod H$ létrehozásakor minden $G$-beli csúcs $H$ egy példányával lesz helyettesítve,
$G$ minden éle pedig a megfelelõ példányok megfelelõ csúcsai közötti élekkel:
\begin{equation}\label{keplet7-49}
\epsfbox{\figdir/v4a.882} \quad \cprod \quad \epsfbox{\figdir/v4a.881} \quad = \epsfbox{\figdir/v4a.880} \koz.
\end{equation}
Mint általában, az általános konstrukció legegyszerûbb speciális esetei kiemelkedõen
fontosnak bizonyulnak a gyakorlatban. Ha mind $G$, mind $H$ út vagy kör, 
\idez{gráfpapír gráfokat kapunk}, nevezetesen az 
$m\times n$-es $P_m\cprod P_n$ \textit{rácsgráf},\inddef{rácsgráf = grid} az
$m\times n$-es $P_m\cprod C_n$ \textit{hengergráf}\inddef{hengergráf = cylinder} és az
$m\times n$-es $C_m\cprod C_n$ \textit{tóruszgráf}\inddef{tóruszgráf = torus}
gráfokat, amelyeket az $m=3$ és $n=4$ esetre mutatunk be:
\begin{equation}\label{keplet7-50}
\begin{tabular}{ccc}
\epsfbox{\figdir/v4a.883} &\quad \quad \epsfbox{\figdir/v4a.884} \quad \quad& \epsfbox{\figdir/v4a.885}\\
\small{$P_3 \cprod P_4$} &\quad \quad \small{$P_3 \cprod C_4$} \quad \quad & \small{$C_3 \cprod C_4$} \\
\small{($3 \times 4$-es rácsgráf}) &\quad \quad \small{($3 \times 4$-es hengergráf)} \quad\quad & \small{($3 \times 4$-es tóruszgráf)} \\
\end{tabular}
\end{equation} 

A gráfok szorzásának négy másik nevezetes módja bizonyult még hasznosnak.
A szorzatgráf csúcsai minden esetben $(u,v)$ alakú rendezett párok.

\smallskip$\bullet$
A $G\dprod H$ \textit{direkt szorzat},\inddef{direkt szorzat = direct product} amit 
$G$ és a $H$ \idez{konjunkciójának} vagy  
\idez{kategorikus szorzatának}\index{tenzoriális szorzat, \textit{lásd} direkt szorzat = tensor product, \textit{see} direct product}
is neveznek, $(u,v) \join (u',v')$ teljesül, amikor $u \join u'$ a $G$-be esik és $v \join v'$ a $H$-ba esik.

\smallskip$\bullet$
A $G \sprod H$ \textit{erõs szorzat}\inddef{erõs szorzat = strong product}  
kombinálja a $G\cprod H$ és a $G\dprod H$ éleit.  

\smallskip$\bullet$
A $G \oprod H$ \textit{páratlan szorzatra}\inddef{páratlan szorzat = odd product} $(u,v) \join (u',v')$ teljesül,
amikor vagy $u \join u'$ a $G$-be esik, vagy $v \join v'$ a $H$-ba esik, de nem egyszerre.

\smallskip$\bullet$
A $G\lprod H$ \textit{lexikografikus szorzatra},\inddef{lexikografikus szorzat = lexicographic product} 
amit a $G$ és a $H$ \idez{kompozíciójának} is neveznek, $(u,v) - (u',v')$ teljesül, ha
$u - u'$ a $G$-be esik, és $(u,v) - (u,v')$, ha $v - v'$ a $H$-ba esik.

\smallskip\noindent Ezen öt mûvelet mindegyike
természetes módon kiterjeszthetõ $k \ge 2$ gráf $G_1 = (V_1,E_1)$,
\dots, $G_k = (V_k,E_k)$ szorzatára, melynek csúcsai $(v_1,\ldots,v_k)$ rendezett $k$-asok,
ahol $v_j\in V_j$ minden $1\le j\le k$ esetén. Ha például $k=3$, a 
$G_1\cprod(G_2\cprod G_3)$ és a $(G_1\cprod G_2)\cprod G_3$ Descartes-szorzatok izomorfak,
amennyiben a\index{asszociatív szabály = associative law}
$(v_1,(v_2,v_3))$ és $((v_1,v_2),v_3)$ csúcsokat a
$(v_1,v_2,v_3)$-mal megegyezõnek tekintjük. Ily módon a Descartes-szorzatból a
$G_1\cprod G_2\cprod G_3$ módon elhagyhatjuk a zárójelezést. A $k$-tényezõs Descartes-szorzatok
legfontosabb példája a 
\begin{equation}\label{keplet7-51}
\advance\abovedisplayskip-1pt
  \advance\belowdisplayskip-1pt
K_2\cprod K_2\cprod\cdots\cprod K_2
\end{equation}
$k$ dimenziós hiperkocka; ennek $2^k$ számú $(v_1,\ldots,v_k)$ csúcsa szomszédos,
ha a Hamming-távolságuk\angolnevindex{Hamming, Richard Wesley (1915--1998)} 1.

Tegyük fel általában, hogy $v=(v_1,\ldots,v_k)$ és $v'=(v'_1,\ldots,v'_k)$ csúcsokból álló $k$-asok, ahol $v_ j - v'_j$ 
a $G_j$-be esik pontosan $a$ indexre a $j$ index közül, és $v_ j=v'_j$ pontosan $b$ indexre. Ekkor:
\\$v \join v'$ pontosan akkor esik $G_1\cprod\cdots\cprod G_k$-ba, ha $a=1$ és $b=k-1$;
\\$v \join v'$ pontosan akkor esik $G_1\dprod \cdots \dprod G_k$-ba, ha $a=k$ és $b=0$;
\\$v \join v'$ pontosan akkor esik $G_1\sprod\cdots\sprod G_k$-ba, ha $a+b=k$ és $a>0$;
\\$v \join v'$ pontosan akkor esik $G_1\oprod\cdots\oprod G_k$-ba, ha $a$ páratlan.
\smallskip
\noindent A lexikografikus szorzat valamelyest különbözik, mivel nem kommutatív;
$G_1\lprod\cdots\lprod G_k$-ban $v \join v'$ pontosan akkor teljesül $v\neq v'$-re, ha 
$v_j \join v'_j$, ahol $j$ a legkisebb olyan alindex, amire $v_j\neq v'_j$.

A \ref{gyak7-91}--\ref{gyak7-102}. gyakorlat megismertet a gráfszorzatok bizonyos alaptulajdonságaival.
Lásd még Imrich\angolnevindex{Imrich, Wilfried} és Klav\v{z}ar\angolnevindex{Klav\v{z}ar, Sandi}  
könyvét \cite{Imrich2000}, amely átfogó bevezetést tartalmaz az általános 
elméletbe, beleértve egy adott gráf \idez{prím} részgráfokra való faktorizálására szolgáló algoritmusokat is.

\medskip
\noindent \textbf{Gráfok foksorozata.}\index{foksorozat = degree sequence}
Nemnegatív egészek egy $d_1d_2\ldots d_n$ sorozatát 
\textit{grafikusnak}\inddef{grafikus foksorozat = graphic degree sequence} nevezzük, ha létezik legalább egy 
$\{1,2,\ldots,n\}$ csúcsú gráf, amelyben a $k$ csúcs fokszáma $d_k$. Feltehetjük, hogy 
$d_1\ge d_2\ge\cdots\ge d_n$. Nyilvánvaló, hogy $d_1<n$ minden ilyen gráfban; 
valamint, hogy minden grafikus sorozat $m=d_1+d_2+\cdots+d_n$ összege mindig páros,
mivel ez éppen az élek számának kétszerese.
Továbbá, könnyen ellenõrizhetõ, hogy a $3311$ sorozat nem grafikus; azaz a grafikus sorozatoknak
más feltételeket is ki kell elégíteniük. Melyek ezek?

Egy adott $d_1d_2\ldots d_n$ sorozat grafikussága eldöntésének egy egyszerû módját
és egy ilyen gráf elkészítését Havel\angolnevindex{Havel, Václav (matematikus)} dolgozta ki \cite{Havel1955}. 
Egy üres tablóval indulunk, amelynek a $k.$ sorában $d_k$ cella van; ezek a cellák\index{tabló = tableaux}
\idez{nyílásokat} reprezentálnak, amelyekbe a $k$ csúcs szomszédait helyezzük a konstruált gráfban. 
Legyen $c_j$ a $j.$ oszlopban lévõ cellák száma; így $c_1\ge c_2\ge\cdots{}$, és $1\le k\le n$ esetén
$c_j\ge k$ teljesül pontosan akkor, ha $d_k\ge j$.\index{konjugált felbontás = conjugate partition}
Legyen például $n=8$, és $d_1\ldots d_8=55544322$; ekkor
\def\vedgec{\vrule height 7pt depth 2.6pt}
\def\bytej#1{\lower.7pt\hbox to1em{\ninerm\hfill#1\hfill\kern.4pt}\kern-.4pt
    \vrule}
\def\Hedge#1{\vbox{\dimen0=.55556em \dimen0=#1\dimen0
     \advance\dimen0 .4 pt \hrule width \dimen0}}
\def\lab#1{\lower.7pt\llap{\ninerm#1\enspace}}
\begin{equation}\label{keplet7-52}
\vcenter{\baselineskip0pt\lineskip0pt\halign{\lft{#}\cr
 \hedgez\cr
\lab1\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgez\cr
\lab2\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgez\cr
\lab3\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgez\cr
\lab4\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgel\cr
\lab5\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgel\cr
\lab6\vedgec\bytej{}\bytej{}\bytej{}\cr
 \hedgeg\cr
\lab7\vedgec\bytej{}\bytej{}\cr
 \hedgek\cr
\lab8\vedgec\bytej{}\bytej{}\cr
 \hedgek\cr}}
\end{equation}
a kiindulási tabló, és $c_1\ldots c_5=88653$. Havel ötlete szerint kössük össze az $n$ csúcsot a legnagyobb fokú csúcsok 
közül $d_n$-nel. Ebben az esetben létrehozzuk például a $8\adj3$ és $8\adj2$ élt, és a tabló a következõ alakúvá változik:
\begin{equation} \label{keplet7-53}
\vcenter{\baselineskip0pt\lineskip0pt\halign{\lft{#}\cr
 \hedgez\cr
\lab1\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgez\cr
\lab2\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{8}\cr
 \hedgez\cr
\lab3\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{8}\cr
 \hedgez\cr
\lab4\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgel\cr
\lab5\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\cr
 \hedgel\cr
\lab6\vedgec\bytej{}\bytej{}\bytej{}\cr
 \hedgeg\cr
\lab7\vedgec\bytej{}\bytej{}\cr
 \hedgek\cr
\lab8\vedgec\bytej{2}\bytej{3}\cr
 \hedgek\cr}}\rlap{.}
\end{equation}
(A $8 \adj 1$ élt nem akarjuk, mivel az üres nyílásokat tabló alakúra kell hozni; 
minden oszlop celláit alulról felfelé kell feltölteni.)
Ezután legyen $n\leftarrow 7$, és hozzunk létre további két, a $7 \adj 1$ és $7 \adj 5$ élt.
Ezt követi még másik három, a $6 \adj 4$, $6 \adj 3$ és $6 \adj 2$, ami már majdnem 
félig késszé teszi a tablót:
\begin{equation} \label{keplet7-54}
\vcenter{\baselineskip0pt\lineskip0pt\halign{\lft{#}\cr
 \hedgez\cr
\lab1\vedgec\bytej{}\bytej{}\bytej{}\bytej{}\bytej{7}\cr
 \hedgez\cr
\lab2\vedgec\bytej{}\bytej{}\bytej{}\bytej{6}\bytej{8}\cr
 \hedgez\cr
\lab3\vedgec\bytej{}\bytej{}\bytej{}\bytej{6}\bytej{8}\cr
 \hedgez\cr
\lab4\vedgec\bytej{}\bytej{}\bytej{}\bytej{6}\cr
 \hedgel\cr
\lab5\vedgec\bytej{}\bytej{}\bytej{}\bytej{7}\cr
 \hedgel\cr
\lab6\vedgec\bytej{2}\bytej{3}\bytej{4}\cr
 \hedgeg\cr
\lab7\vedgec\bytej{5}\bytej{1}\cr
 \hedgek\cr
\lab8\vedgec\bytej{2}\bytej{3}\cr
 \hedgek\cr}}\rlap{.}
\end{equation}

A problémát egy $d_1\ldots d_5=43333$ csúcssorozattal rendelkezõ gráf keresésévé egyszerûsítettük; 
ezen a ponton $c_1\ldots c_4=5551$ szintén teljesül. Az olvasóra bízzuk az üresen maradt helyek kitöltését,
mielõtt megtekintené a \ref{gyak7-103}. gyakorlatnál adott választ.

\algbegin H algoritmus (gráfgenerátor adott fokszámokhoz). Adott $d_1\ge\cdots\ge d_n\ge d_{n+1}=0$ esetén ez az algoritmus 
éleket hoz létre az $\{1,\ldots,n\}$ csúcsok között úgy, hogy pontosan $d_k$ él tartalmazza a $k$ csúcsot minden $1\le k\le n$ 
esetén, hacsak a $d_1\ldots d_n$ sorozat nem grafikus. Átmeneti tárolóként egy $c_1\ldots c_{d_1}$ tömböt használunk.

\algindentset{H1}
\algstep H1. (A $c$-k beállítása.) Kiindulásként legyen $k\gets d_1$ és $j\leftarrow 0$.
Végezzük el a következõ mûveleteket, amíg $k>0$ fennáll: Legyen $j\leftarrow j+1$;
amíg $k>d_{j+1}$, legyen $c_k\leftarrow j$ és $k\leftarrow k-1$.

\algstep H2. ($n$ megkeresése.) Legyen $n\leftarrow c_1$. Fejezzük be sikeresen a futást, ha $n=0$, 
és sikertelenül, ha $d_1\ge n>0$.

\algstep H3. (Ciklus $j$-re.) Legyen $i\leftarrow 1$, $t\leftarrow d_1$ és $r\leftarrow c_t$.
Hajtsuk végre a H4 lépést a $j=d_n$, $d_n-1$, \dots,~1 esetre;
majd lépjünk vissza a H2-re.

\algstep H4. (Új él létrehozása.) Legyen $c_j\leftarrow c_j-1$ és $k\gets c_t$.
Készítsük el a $k- n$ élt, és legyen $d_k\leftarrow d_k-1$, $c_t\leftarrow k-1$.
Ha $k=i$, legyen $i\leftarrow r+1$, $t\leftarrow d_i$ és $r\leftarrow c_t$ 
(lásd a \ref{gyak7-104}. gyakorlatot). \slug

\medbreak

Ha a H algoritmus sikeresen lefut, elkészít egy gráfot a kívánt fokszámokkal. 
Ha viszont sikertelen a futása, hogyan tudjuk ellenõrizni, hogy lehetetlent kértünk tõle? 
Ennek a kérdésnek a kulcsa a \idez{\textit{majorálás}} nevû fontos fogalom: 
Ha $d_1\ldots d_ n$ és $d'_1\ldots d'_n$
ugyanannak az egésznek két különbözõ felbontása (azaz, ha 
$d_1\ge\cdots\ge d_ n$ és $d'_1\ge\cdots\ge d'_n$ és
$d_1+\cdots+d_ n=d'_1+\cdots+d'_n$), akkor 
$d_1\ldots d_ n$ {\it majorálja} a $d'_1\ldots d'_n$-t, ha 
$d_1+\cdots+d_ k\ge d'_1+\cdots+d'_k$, $1\le k\le n$.

\noindent \textbf{M lemma.} {\sl Ha $d_1\ldots d_ n$ grafikus, és 
$d_1\ldots d_ n$ majorálja $d'_1\ldots d'_n$-t, akkor
$d'_1\ldots d'_n$ szintén grafikus.}

\proof. Az állítást elég arra az esetre bizonyítani, amikor 
$d_1\ldots d_ n$ és $d'_1\ldots d'_n$ csak két helyen tér el,
\begin{equation}\label{keplet7-55}
d'_k\;=\;d_k-[k=i]+[k=j],\qquad \hbox{ ahol } i<j,
\end{equation}
mivel a $d_1\ldots d_n$-nel majorált minden sorozat megkapható az
ehhez hasonló mini-majorálások ismételgetésével.
(A 7.2.1.4--55. gyakorlatok tárgyalják részletesen a majorálást.)

Az (\ref{keplet7-55}) feltételbõl következik, hogy $d_i>d'_i \ge d'_{i+1}\ge d'_j>d_j$.
Vagyis a $d_1\ldots d_n$ fokszámsorozattal rendelkezõ minden gráf 
tartalmaz egy $v$ csúcsot, melyre $v \join i$ és $v \nadj j$. 
A $v \join i$ él törlése és a $v \join j$ él hozzáadása egy 
$d'_1\ldots d'_n$ kívánt fokszám sorozattal rendelkezõ gráfot eredményez. \slug 

\medbreak

\noindent \textbf{H következmény.}
{\sl A H algoritmus sikeresen fejezõdik be, ha $d_1\ldots d_n$ grafikus.}

\proof. Feltehetjük, hogy $n>1$. Legyen $G$ egy $\{1,\ldots,n\}$ csúcsú tetszõleges gráf $d_1\ldots d_n$ fokszámsorozattal, és 
legyen $G'$ az $\{1,\ldots,n-1\}$ csúcsok által indukált részgráf; más szavakkal, készítsük el a $G'$-t az $n$ csúcs, és a hozzá  
illeszkedõ $d_n$ él eltávolításával. A $G'$ gráf $d'_1\ldots d'_{n-1}$ fokszámsorozata a $d_1\ldots d_{n-1}$-bõl kapható meg, 
$d_n$ értéket 1-gyel csökkentve, majd ezeket csökkenõ sorba rendezve. A $d'_1\ldots d'_{n-1}$ sorozat definíció szerint grafikus. 
A H3 és H4 lépéssel elõállított $d''_1\ldots d''_{n-1}$ fokszámsorozatot minden ilyen $d'_1\ldots d'_{n-1}$ sorozat majorál, mivel
1-gyel csökkenti a legnagyobb lehetséges $d_n$ értékeket. Ezért az új $d''_1\ldots d''_{n-1}$ grafikus. A 
$d_1\ldots d_{n-1}\leftarrow d''_1\ldots d''_{n-1}$-t beállító H algoritmus sikeressége ezért $n$-szerinti indukcióval 
következik.\quad\slug

A H algoritmus futási ideje durván a létrehozott élek számával arányos, amelynek nagyságrendje $n^2$ lehet.
A \ref{gyak7-105}. gyakorlat egy gyorsabb módszert közöl, ami $O(n)$ lépésben dönti
el, hogy egy adott $d_1\ldots d_n$ sorozat grafikus-e vagy sem (gráf létrehozása nélkül).

\medskip
\noindent \textbf{Túl a gráfokon.} Amennyiben egy gráf vagy irányított gráf csúcsait és/vagy éleit további adatokkal látjuk el, 
úgy azt \textit{hálózatnak}\inddef{hálózat = network} nevezzük. Például a \text{words}$(5757,0,0,0)$ gráf minden csúcsának van 
egy hozzárendlet rangja, amely a megfelelõ ötbetûs szó népszerûségét jelzi. A 
\textit{plane\_lisa}$(360,250,15,0,360,0,250,0,0,2295000)$ gráf csúcsainak van egy hozzárendelt \textit{képpont} sûrûsége 
0 és 15 között. A \textit{board}$(8,8,0,0,-2,0,0)$ minden élének van egy hozzárendelt hossz értéke, ami egy figura táblán 
való mozgásának távolságát írja le: Egy \textit{futó} egyik sarokból másikba való mozgásának a hossza 7. A 
\textit{Stanford GraphBase}\index{Stanford Gráfbázis = Stanford GraphBase} a fentieken túl számos további generátort tartalmaz, 
amelyekrõl eddig nem volt szó, mivel ezeket elsõsorban érdekes hálózatok, nem pedig érdekes struktúrával rendelkezõ 
gráfok elõállítására használják.

\smallskip$\bullet$
\textit{miles}$(128,0,0,0,0,127,0)$ egy 128 csúcsú hálózat, amelyek a korábban leírt \textit{plane\_miles} 
észak-amerikai városaira vonatkoznak. A \textit{plane\_miles} gráftól eltérõen azonban, a \textit{miles} egy teljes gráf 
${128}\choose{2}$ éllel. Minden él egész hosszúságú, annak a távolságnak a leírására, amelyet 1949-ben egy autó megtett, miközben
átutazott az egyik városból egy másikba. Például `\textsc{Vancouver},~\textsc{BC}' és\index{autópálya = highway}
`\textsc{West} \textsc{Palm} \textsc{Beach},~\textsc{FL}' távolsága 3496 mérföld a \textit{miles} hálózatban.

\smallskip$\bullet$
\textit{econ}$(81,0,0,0)$ egy 81 csúccsal és 4902 éllel rendelkezõ hálózat. A csúcsai ez Egyesült Államok egyes gazdasági szektorait, 
míg élei a pénz szektorok közötti áramlásának 1985-ben mért mennyiségét reprezentálják millió dollárban számolva.
Például az áramlási érték a \textsc{Apparel} (Ruházat) szektorból a \textsc{Household furniture} (Háztartási bútor)  
szektorba 44, vagyis a bútoripar $44.000.000$ dollárt fizetett a ruházati szektornak a nevezett évben.
Az egy csúcsba beérkezõ tételek összege megegyezik a csúcsból kiinduló tételek összegével. Él csak akkor jelenik meg, ha ez az 
áramlás nem nulla. A speciális, \textsc{Users} (Felhasználók) csúcs fogadja egy termék teljes pénzügyi igényét; egyes ilyen 
végfelhasználói tételek negatívak, az importált áruk egyes állami közgazdászok általi kezelése miatt.

\smallskip$\bullet$
\textit{games}$(120,0,0,0,0,0,128,0)$ egy 120 csúccsal és 1276 éllel rendelkezõ hálózat. A csúcsai az Egyesült Államok 
fõiskoláinak és egyetemeinek futballcsapatait reprezentálják. Élek azon csapatok között futnak, amelyek játszottak egymással 
az izgalmas 1990-es bajnokságban, és a szerzett pontokkal vannak címkézve. Például a 
$\textsc{Stanford}\rightarrow\textsc{California}$ él értéke 27, míg a $\textsc{California}\rightarrow\textsc{Stanford}$ 
értéke 25, mivel a \textit{Stanford Cardinal} a U.~C. Berkeley \textit{Golden Bears} csapatát 27--25 arányban gyõzte le 
1990. november 17-én.

\smallskip$\bullet$
{\it risc}$(16)$ egy teljesen más típusú hálózat.
3240 csúccsal és 7878 éllel rendelkezik, amely egy {\textit{irányított aciklikus gráfot} vagy 
\idez{\textit{iag}}-t definiál, nevezetesen egy \textit{irányított köröket} nem tartalmazó irányított gráfot.
\index{aciklikus: köröket nem tartalmazó = acyclic: containing no cycles}\index{RISC: csökkentett utasításkészletû 
számítógép = RISC: Reduced Instruction Set Computer}\index{körmentes irányított gráf = directed acyclic graph}
A csúcsok logikai értékekkel rendelkezõ kapukat tartalmaznak; 
a $\textsc{Z45}\leftarrow\textsc{R0:7\char`\~}$ él azt jelenti, hogy a \textsc{Z45} kapu
értéke a \textsc{R0:7\char`\~} kapu bemenete. Minden kapunak van egy (ÉS, VAGY, KIZÁRÓ VAGY, NEM, \textit{retesz} vagy külsõ 
bemeneti) típuskódja; minden élnek van egy, a késés mértékét jelzõ hossza. A hálózat tartalmazza egy miniatûr RISC áramkör 
teljes logikai felépítését, ami tizenhat regiszter irányítására képes 16-bites egyszerû parancs használatát biztosítja.

\smallbreak
Az SGB generátorokkal kapcsolatban az összes részlet megtalálható a szerzõ\angolnevindex{Knuth@\string\Knuth}
{\sl The Stanford GraphBase\/} címû könyvében \cite{Knuth1993} 
egyszerû példaprogramok tucatjaival együtt, amelyek elmagyarázzák a generátorok
által elõállított gráfok és hálózatok manipulálhatóságát. 
\index{Stanford GraphBase: teljes leírás = Stanford GraphBase: complete guide}
Egy \textsc{LÉTRÁK} címû program például bemutatja, hogyan található 
{\it legrövidebb út} két ötbetûs szó között. Egy \textsc{RISC\_HASZNÁLATA} címû program elmagyarázza, hogyan mûködik egy
\textit{nano számítógép} lépésrõl lépésre, a \textit{risc}$(16)$ kapuiból felépülõ hálózat mûveleteinek szimulálásával.

\medskip
\noindent \textbf{Hipergráfok.}\index{hipergráf = hypergraph}
A gráfok és hálózatok igen érdekesek lehetnek, de még távolról sem jelentik a történet 
végét. Sok fontos kombinatorikai algoritmust terveztek a gráfoknál általánosabb \textit{hipergráfokra}, 
melyek élei a csúcsok \textit{tetszõleges} részhalmazai lehetnek.

Lehet adva hét csúcs, amelyeket a $v=a_1a_2a_3$ alakú nemnulla bináris füzérek azonosítanak, és hét él, amelyeket pedig az  
$e=[b_1b_2b_3]$ zárójelezett nemnulla bináris füzérek azonosítanak, ahol $v\in e$ pontosan akkor, ha 
$(a_1b_1+a_2b_2+a_3b_3)\mod 2=0$ (a nemnulla füzérek nem minden eleme nulla). Ezen élek mindegyike pontosan három csúcsot tartalmaz:
\begin{equation}
[001]=\{010,100,110\};\quad
[010]=\{001,100,101\};\quad
[011]=\{011,100,111\};\nonumber
\end{equation}
\vspace{-4mm}
\begin{equation}
[100]=\{001,010,011\};\quad
[101]=\{010,101,111\};\nonumber
\end{equation}
\vspace{-4mm}
\begin{equation}
[110]=\{001,110,111\};\quad
[111]=\{011,101,110\}\koz.\label{keplet7-56}
\end{equation}
Továbbá, a szimmetria miatt, minden csúcs pontosan három élhez tartozik.
(A három vagy több csúcsot tartalmazó élt idõnként 
\textit{hiperélnek} is nevezik, hogy megkülönböztessék egy hagyományos gráf éleitõl.
\index{hipergráf éle = edges of a hypergraph}
Lehet azonban egyszerûen csak \idez{éleknek} is nevezni õket.)

Egy hipergráf \textit{r-egyenletes},\inddef{regyenletes@$r$-egyenletes hipergráf = $r$-uniform hypergraph} 
ha minden él pontosan $r$ csúcsot tartalmaz. Így (\ref{keplet7-56}) egy 3-egyenletes hipergráf, egy 2-egyenletes
hipergráf pedig egy hagyományos gráf. A $K^{(r)}_n$ teljes $r$-egyenletes hipergráfnak 
$n$ csúcsa és $\binom{n}{r}$ éle van.\index{Krn@$K^{(r)}_n$ = $K^{(r)}_n$}

A gráfelmélet legtöbb alapfogalma természetes módon kiterjeszthetõ hipergráfokra.
Ha például $H=(V,E)$ egy hipergráf és $U\subseteq V$, akkor az $U$ által {\it indukált} $H\rest U$ részhipergráf 
$\{e\mid e\in E$ és $e\subseteq U\}$ élekkel rendelkezik. Egy \textit{r-egyenletes hipergráf $\overline H$ komplementere} 
\smash{$K{(r)}_n$} azon éleivel rendelkezik, amelyek $H$-nak nem elemei. 
Egy {hipergráf $k$-színezése} színek csúcsokhoz való rendelése úgy, hogy ne legyenek egyszínû élek. És így tovább.

A hipergráfokat gyakran más névvel is illetik, mivel ugyanezek a tulajdonságok 
sok más módon is megfogalmazhatók. Például, minden $H=(V,E)$ hipergráf
alapvetõen \textit{halmazok egy családja},\index{halmazrendszer, \textit{lásd} hipergráf = set system, \textit{see} hypergraph}
mivel minden él $V$ egy részhalmaza. Egy 3-egyenletes hipergráfot 
\textit{tripla rendszernek}\inddef{tripla rendszer = triple system} is szoktak hívni. Egy hipergráf $0$-k és $1$-ek egy $B$
mátrixával is ekvivalensek, \index{nullaegy@0--1 mátrix = 0--1 matrix}
ahol minden $v$ csúcshoz egy sor és minden $e$ élhez egy oszlop tartozik; 
a mátrix $v$ sora és $e$ oszlopa a $b_{ve}=[v\in e]$ értéket tartalmazza. 
A $B$ mátrixot a $H$ \textit{illeszkedési mátrixának}\inddef{illeszkedési mátrix = incidence matrix} nevezzük,
és \idez{$v$ elõfordul az $e$-ben}, ha $v\in e$.
Továbbá, egy hipergráf egy \textit{páros gráffal}\index{páros gráf = bipartite graph}\index{gráf = graph!páros gráf 
\textit{lásd} páros gráf = bipartite graph \textit{see} bipartite graph} ekvivalens, 
$V\cup E$ csúcshalmazzal és $v \join e$ éllel, amennyiben $v$ elõfordul az $e$-ben. 
A hipergráfot pontosan akkor nevezzük \textit{összefüggõnek},\inddef{összefüggõ gráf = connected 
graph}\index{gráf = graph!összefüggõ gráf = connected graph} ha 
a megfelelõ páros gráf összefüggõ. Egy hipergráf $k$-hosszú \textit{körét}\inddef{hipergráf köre = cycle of a hypergraph}
a megfelelõ páros gráf $2k$-hosszú köreként definiáljuk.

Az (\ref{keplet7-56}) hipergráf például egy ekvivalens elõfordulási mátrixszal vagy
páros gráffal is definiálható a következõképpen:
\begin{equation}\label{keplet7-57}
\advance\abovedisplayskip10pt
\vcenter{\kern-1.2\baselineskip
           \halign{\llap{$\scriptstyle#$}\ &#\hfil\kern-4pt&
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil\ &
                    \hfil$#$\hfil&\kern-4pt\hfil#\cr
&&\scriptstyle[001]&\scriptstyle[010]&\scriptstyle[011]&\scriptstyle[100]&
\scriptstyle[101]&\scriptstyle[110]&\scriptstyle[111]\cr
\noalign{\vskip.2\baselineskip}
001&&0&1&0&1&0&1&0\cr
010&&1&0&0&1&1&0&0\cr
011&&0&0&1&1&0&0&1\cr
100&\smash{$\left(\vrule height3.5\baselineskip width0pt\right.$}&
 1&1&1&0&0&0&0&\smash{$\left.\vrule height3.5\baselineskip width0pt\right)$}\cr
101&&0&1&0&0&1&0&1\cr
110&&1&0&0&0&0&1&1\cr
111&&0&0&1&0&1&1&0\cr}}
\qquad\vcenter{\epsfbox{\figdir/v4a.1515}}
\end{equation}
Ez a hipergráf 28 darab 3 hosszúságú utat tartalmaz, mint például
\begin{equation}
[101]\adj101\adj[010]\adj001\adj[100]\adj010\adj[101]\koz.\label{keplet7-58}
\end{equation}

Egy $H$ hipergráf $H^T$ \textit{duálisát} a csúcsok és élek szerepének felcserélésével
képezzük az illeszkedési reláció megõrzésével. Más szóval, az illeszkedési mátrixot transzponáljuk. 
Vegyük észre például, hogy egy $r$-\textit{reguláris} gráf duálisa egy $r$-egyenletes hipergráf.

Az illeszkedési mátrixok és páros gráfok vonatkozhatnak olyan hipergráfokra, 
amelyekben egyes élek egynél többször jelennek meg, mivel a mátrixban két oszlop megegyezhet.
Egy ismétlõdõ élekkel nem rendelkezõ $H=(V,E)$ hipergráf\index{különbözõ oszlopok = distinct columns}
egy másik kombinatorikai objektumnak, nevezetesen egy {\it{logikai függvénynek}} is megfelel. 
Ha például a $V$ csúcshalmaz $\{1,2,\ldots,n\}$, akkor a 
\begin{equation}
h(x_1,x_2,\ldots,x_n)\;=\;\big[\{j\mid x_j=1\}\in E\big]\label{keplet7-59}
\end{equation}
függvény leírja a $H$ éleit. (\ref{keplet7-56}) és (\ref{keplet7-57}) hipergráfja például a
\begin{equation}
(x_1\xor x_2\xor x_4)\land
  (x_2\xor x_3\xor x_5)\land
  (x_3\xor x_4\xor x_6)\land
  (x_4\xor x_5\xor x_7)\nonumber
 \end{equation}
 \begin{equation}
\land(x_5\xor x_6\xor x_1)\land
  (x_6\xor x_7\xor x_2)\land
  (x_7\xor x_1\xor x_3)\land
  (\bar x_1\lor\bar x_2\lor\bar x_3)\label{keplet7-60}
\end{equation}
logikai képlettel is leírható.

Kissé zavaró lehet, hogy a kombinatorikai objektumok ilyen sokféleképpen felfoghatók. 
Ez azonban egyúttal roppant hasznos is, mivel ekvivalens problémák megoldásához számos 
ötletet kapunk. Ha egy problémát több oldalról is górcsõ alá veszünk, 
az agyunk természetes módon több irányból is próbál a megoldáshoz eljutni. 
Idõnként a mátrix sorai és oszlopai cserélgetésének 
végiggondolása vezethet el a probléma mélyebb megértéséhez. 
Más esetben a csúcsok útvonalként való értelmezésével vagy pontosztályok térbeli 
megjelenítésével érhetünk el haladást.
Megint máskor, a Boole-algebra\angolnevindex{Boole, George (1815--1864)}\index{Boole-algebra = Boolean algebra} 
a megfelelõ eszköz. Ha az egyik megközelítéssel elakadunk, egy másik siethet a segítségünkre.

\medskip
\noindent \textbf{Lefedés és függetlenség.}
Egy $H=(V,E)$ gráf vagy hipergráf esetén, csúcsok egy $U$ halmaza 
\textit{lefedi} a $H$-t, ha minden él tartalmazza az $U$ legalább egy elemét.
Csúcsok egy $W$ halmazát \textit{függetlennek}\inddef{független csúcsok = independent vertices} (vagy \textit{stabilnak}) 
nevezzük\index{stabil halmaz = stable set \textit{lásd} független csúcsok = independent vertices} 
a $H$-ban ha, a $W$ egyetlen élt sem tartalmaz teljesen.

Az illeszkedési mátrixot tekintve, egy lefedés olyan sorok egy halmaza,
amelyek oszlopösszege sehol sem nulla. Amennyiben $H$ speciálisan egy gráf,
a mátrix minden oszlopa csak két 1-est tartalmaz;
vagyis egy gráf egy független halmaza egymásra kölcsönösen 
\textit{merõleges} sorok egy halmazát jelenti -- azaz egy olyan halmazt,
amelyre bármely két különbözõ sor \textit{skaláris szorzata} nulla.

Ezek a fogalmak egyazon érme két oldalát jelentik. Ha az $U$ lefedi a $H$-t,
akkor $W=V\setminus U$ független a $H$-ban; megfordítva, ha a 
$W$ független a $H$-ban, akkor $U=V\setminus W$ lefedi a $H$-t.
Mindkét állítás azzal ekvivalens, hogy az indukált
$H\rest W$ hipergráfnak nincsenek élei.

A lefedésnek és függetlenségnek ez a duális kapcsolata, amelyet elõször Claude 
Berge\angolnevindex{Berge, Claude (1926--2002)} \cite{Berge1957} figyelt meg, meglehetõsen paradox. 
Habár logikailag nyilvánvaló és könnyen ellenõrizhetõ, 
intuitíve mégis meglepõ. Ha egy gráfot vizsgálunk, és egy nagy méretû
független halmazt próbálunk találni, másképpen gondolkodunk, mint amikor 
egy kis méretû csúcs lefedõt keresünk ugyanazon gráfban;
miközben a cél mindkét esetben ugyanaz.

Egy lefedõ $U$ halmaz \textit{minimális}\inddef{minimális lefedõ halmaz = minimal covering set}, 
ha $U\setminus u$ nem lefedõ minden $u\in U$ esetén. Hasonlóan, egy független $W$ halmaz 
\textit{maximális}\inddef{maximális lefedõ halmaz = maximal covering set}, 
ha $W\cup w$ nem független minden $w\notin W$ esetén.
Lejjebb példaként megadjuk a 49-csúcsú \textit{összeföggõ Egyesült Államok} (\ref{keplet7-17}) gráf
egy minimális lefedését és a kapcsolódó maximális független halmazt:

\begin{equation}\label{keplet7-61}
\begin{tabular}{cc}
\epsfbox{\figdir/v4a.1511} &\quad \quad \epsfbox{\figdir/v4a.1510}\\
\small{Minimális csúcslefedés} &\quad \quad \small{Maximális független halmaz} \\
\small{38 csúccsal} &\quad \quad \small{11 csúccsal} \\
\end{tabular}
\end{equation} 

Egy lefedést {\it minimumnak} nevezünk, ha a mérete a lehetõ legkisebb,
illetve egy lefedõ halmazt {\it maximumnak}, ha a mérete a lehetõ legnagyobb.
Például a (\ref{keplet7-17})-es gráffal a (\ref{keplet7-61})-esnél lényegesen jobb eredményt érhetünk el:
\begin{equation}\label{keplet7-62}
\begin{tabular}{cc}
\epsfbox{\figdir/v4a.1513} &\quad \quad \epsfbox{\figdir/v4a.1512}\\
\small{Minimális csúcslefedés} &\quad \quad \small{Maximális független halmaz} \\
\small{30 csúccsal} &\quad \quad \small{10 csúccsal} \\
\end{tabular}
\end{equation}
Ezen a ponton figyeljük meg a \idez{minimális} és a \idez{minimum} közötti finom különbséget:
Általában (bár a legtöbb \textit{angol szótártól} eltérõen)
\index{minimális és minimum közötti különbség = minimal versus minimum}
\index{maximális és maximum közötti különbség = maximal versus maximum}
\index{optimális és optimum közötti különbség = optimal versus optimum}
a kombinatorikai algoritmusokkal dolgozók a \idez{minimális} vagy \idez{optimális}  
szóhasználattal élnek a \textit{lokálisan} legjobb kombinatorikai konfigurációk megjelöléséhez,
amelyek kisebb módosítások hatására nem javulnak. 
A \idez{minimum} vagy \idez{optimum} kifejezések az összes szóba jövõ között \textit{globálisan} legjobb 
konfigurációk számára van fenntartva. Minden optimalizációs
problémára könnyû találni egy gyengébb, helyi értelemben optimális megoldást,
folyamatosan mászva a hegyet a csúcs eléréséig.
A valódi optimumot szolgáltató megoldások megkeresése általában jóval nehezebb feladat.
Így például a 7.9. alfejezetben látni fogjuk, hogy egy adott gráf 
\textit{maximum független halmazának} megkeresése a bonyolult, \textit{NP-teljes} feladatok
osztályába tartozik.

Nem kell azonban kétségbe esnünk NP-teljes problémák esetén sem. 
Minimum lefedõk keresésére használt technikákat a fejezet számos pontján tárgyalni fogunk,
amelyek kisebb problémák esetén jól mûködnek; A (\ref{keplet7-62}) optimum megoldása
kevesebb, mint egy másodperc alatt megtalálható volt 
a $2^{49}$ lehetõség csak egy kis szeletének átvizsgálásával.
Továbbá, NP-teljes problémák speciális esetei gyakran bizonyulnak
az általános esetnél egyszerûbbnek. A 7.5.1. pontban látható lesz, hogy 
egy minimum csúcslefedõ gyorsan megkereshetõ egy \textit{páros gráfban} vagy
ennek a gráfnak egy \textit{duális} hipergráfjában. 
A 7.5.5. pontban pedig hatékony módszereket tárgyalunk 
maximum \textit{párosítás}\index{párosítás = matching} keresésére, ami egy adott gráf \textit{élgráfjának}
maximum független halmaza.

Egy független halmaz méretének maximalizálása annyira gyakori probléma, hogy célszerû saját jelöléssel ellátni:
Egy $H$ hipergráf esetén az\index{alfa@$\alpha(H)$ = $\alpha(H)$}
\begin{equation}
\alpha(H)\;=\;\max\bigl\{\vert W\vert\bigm\vert
  \hbox{$W$ független csúcsok halmaza $H$-ban}\bigr\}\label{keplet7-63}
\end{equation}
értéket a $H$ {\it{függetlenségi számának}} (vagy {\it stabilitási számának})
nevezzük. Hasonlóan, a
\begin{equation}
\chi(H)\;=\;\min\{k\mid 
  \hbox{$H$ $k$-színezhetõ}\}\label{keplet7-64}
\end{equation}
értéket a $H$ \textit{kromatikus számának}} nevezzük. Vegyük észre, hogy 
$\chi(H)$ a $H$ független halmazokkal val\inddef{kromatikus szám = chromatic number} minimum lefedõjének a mérete, 
mivel az egyes színeket kapó csúcsoknak a definíciónk szerint függetlennek kell lenniük.

Az $\alpha(H)$ és $\chi(H)$ ezen definíciói elsõsorban arra az esetre vonatkoznak,
amikor $H$ egy szokásos gráf, és ilyenkor természetesen gyakran használjuk az 
$\alpha(G)$ és $\chi(G)$ jelölést is.
A gráfokhoz kapcsolódik még egy másik fontos érték, az
\begin{equation}
\omega(G)\;=\;\max\bigl\{\vert X\vert\bigm\vert
  \hbox{$X$ klikk $G$-ben}\bigr\}\koz,\label{keplet7-65}
\end{equation}
{\it{klikkszám}}, ahol egy \idez{\textit{klikk}} kölcsönösen szomszédos csúcsok egy halmaza. 
\begin{equation}
\omega(G)\;=\;\alpha(\overline G)\koz,\label{7-66}
\end{equation}
nyilvánvalóan fennáll, mivel egy $G$-beli klikk a \textit{komplementer gráf} egy \textit{független halmaza}. Hasonlóan látható, 
hogy $\chi(\overline G)$ egy \textit{klikk lefedõ} legkisebb mérete, ami az összes csúcsot lefedõ klikkek egy halmaza.

Ebben az alfejezetben több helyen is említettünk \idez{pontos \textit{lefedési} problémákat} anélkül, hogy
precízen elmagyaráztuk volna egy ilyen probléma mibenlétét. 
Mostanra készen állunk a definícióra: Egy $H$ hipergráf \textit{illeszkedési mátrixa} esetén,
a $H$ egy \textit{pontos lefedése} a mátrix olyan sorainak egy halmaza, 
amelyek összege $(1\,1\,\ldots\,1)$. Más szóval, egy pontos lefedés olyan csúcsok egy halmaza,
amelyek minden hiperélt pontosan egyszer érintenek;
egy szokásos lefedésnek minden hiperélt \textit{legalább}
egyszer kell érintenie.\index{gráf = graph}

{\small
\vspace{8mm}
\textbf{GYAKORLATOK}\small
\vspace{2mm}
\begin{gyak}
%%% 1
\ujgyak \label{gyak70-1}
\sz{25}
%%% 2
\ujgyak \label{gyak70-2}
\sz{18}
\setcounter{gyakcounter}{144}
\vspace{3mm}
\textbf{\ldots}
\vspace{3mm}
%%% 145

\setcounter{gyakcounter}{68}
\ujgyak \label{gyak7-69} \sz{20}
A \ref{gyak7-31}. gyakorlatot kiterjesztve magyarázzuk el, hogyan kell egy SGB formátumban ábrázolt gráf \textit{minden} 
csúcsához kiszámítani a KIFOK(v) kifokot és a BEFOK(v) befokot.
\ujgyak \label{gyak7-70} \sz{M20}
Hányszor futnak le a B algoritmus egyes lépései, amikor az algoritmus
sikeresen 2-színez egy $m$ élû és $n$ csúcsú gráfot?
\ujgyak \label{gyak7-71} \sz{M26}
Implementáljuk a B algoritmust az MMIX számítógép számára úgy, hogy
a MMIXAL assembly nyelvet használjuk. Tegyük fel, hogy a program kezdetekor a $v0$ regiszter
az elsõ csúcspontra mutat, és az $n$ regiszter a csúcsok számát tartalmazza.
\ujgyak \label{gyak7-72} \sz{M22}
Amikor a B6-os lépésben beállítjuk a COLOR(v) értéket, akkor $u$-t nevezzük $v$
\textit{szülõjének}; viszont amikor a B3-as lépésben állítjuk be a COLOR(w)-t, akkor mondjuk azt, hogy
$w$-nek nincs szülõje. Definiáljuk a $v$ csúcs \textit{õseit} rekurzívan $v$ és $v$ szülõjének õseivel,
már ha van szülõje.
a) Bizonyítsuk be, hogy ha a B algoritmus mûködése során $v$ lejjebb van a veremben, mint
$u$, akkor $v$ szülõje egyben $u$ õse is.
b) Továbbá, ha a B6-os lépésben COLOR($v$) = COLOR($u$), akkor $v$ aktuálisan a veremben van.
c) Használjuk fel ezeket az összefüggéseket, a B algoritmus kiterjesztéséhez úgy, hogy
ha a gráf nem páros, akkor a kimenet a csúcsok nevei legyenek egy páratlan hosszúságú körben.
\ujgyak \label{gyak7-73} \sz{15}
Hogyan nevezzük másképpen a \textit{véletlen\_gráf}$(10,45,0,0,0,0,0,0,0,0)$-t?
\ujgyak \label{gyak7-74} \sz{21}
A \textit{roget}$(1022,0,0,0)$ mely csúcsának van a legnagyobb kifoka?
\ujgyak \label{gyak7-75} \sz{22}
A \textit{tábla}$(n_1,n_2,n_3,n_4,p,w,o)$ SGB gráf generátor egy olyan gráfot hoz létre,
amelynek csúcsai az $(x_1, \ldots, x_t)$ $t$-dimenziós egész vektorok, ahol $0 \le x_i < b_i$, amelyet az elsõ négy
$(n_1,n_2,n_3,n_4)$ paraméter határoz meg a következõképpen: Legyen $n_5\gets 0$
és $j\ge 0$ az a minimális érték, hogy $n_{j+1}\le 0$ teljesül. Ha $j=0$, akkor
legyen $b_1\gets b_2\gets 8$ és $t\gets 2$; ez lesz az alapértelmezett
$8\times\nobreak 8$-as tábla. Egyébként, ha $n_{j+1}=0$, akkor legyen $b_i\gets n_i$, ahol 
$1\le i\le j$ és $t \leftarrow j$. Végül, ha $n_{j+1}<0$, akkor legyen $t\gets\vert n_{j+1}\vert$,
és legyen $b_i$ az $i.$ eleme az $(n_1,\ldots,n_j,\allowbreak
n_1,\ldots,n_j,n_1,\ldots{})$
periodikus sorozatnak. (Például az $(n_1, n_2, n_3, n_4)=(2,3,5,-7)$ eset olyan ravasz,
amilyen csak lehet; egy 7-dimenziós táblát állít elõ $(b_1, \ldots, b_7) = (2,3,5,2,3,5,2)$-
vel, tehát egy $2 \cdot 3 \cdot 5 \cdot 2 \cdot 3 \cdot 5 \cdot 2 = 1800$ csúcsú gráfot.)

A maradék $(p,w,o)$ paraméterek a gráf éleit határozzák meg.
Elõször tegyük fel, hogy $w=o=0$. Ha $p>0$, $(x_1,\ldots,x_t)\dadj(y_1,\ldots,y_t)$
pontosan akkor, ha $y_i=x_i+\delta_i$ $1\le i\le t$-re, ahol $(\delta_1,\ldots,\delta_ t$) 
egész megoldása a $\delta_1^2+\cdots+\delta_t^2=\vert p\vert$ egyenletnek. Ha $p<0$, akkor megengedett az 
$y_i=x_i+k\delta_i$ eset is, ahol $k\ge1$, amely megfelel annak, hogy $k$ azonos irányba mozog.

Ha $w\neq 0$, akkor legyen $w=(w_t\ldots w_1)_2$ bináris alakban. Engedélyezzük a
\idez{bekerítést}: $y_i=(x_i+\delta_i)\mod b_i$ vagy $y_i=(x_i+k\delta_i)\mod b_i$,
minden olyan $i$ koordinátára, amelyre $w_i = 1$.

Ha $o \neq 0$, akkor a gráf irányított; a $(\delta_1, \ldots , \delta_t)$ eltolás csak
akkor hoz létre éleket, ha lexikografikus rendezés szerint nagyobbak, mint $(0, \ldots, 0)$.
De ha $o = 0$, akkor a gráf nem irányított.

Találjunk olyan $(n_1,n_2,n_3,n_4,p,w,o)$ konfigurációt, amikor a \textit{tábla} a következõ alapgráfot
hozza létre: (a) a $k_n$ teljes gráf; (b) a $P_n$ út; (c) a $C_n$ kör;
(d) a $K\orie_{n}$ tranzitív verseny; (e) a $P\orie_{\!n}$ irányított út;
(f) a $C\orie_{n}$ irányított kör; (g) a $P_m\cprod P_n$ $m\times n$-es rács;
(h) a $P_m\cprod C_n$ $m\times n$-es henger; (i) a $C_m\cprod C_n$ $m\times n$-es tórusz;
(j) a $K_m\cprod K_n$ $m\times n$-es bástya gráf 
(k) a $C\orie_{m}\cprod C\orie_{n}$ $m\times n$-es irányított tórusz;
(l) a $\overline{K_n}$ zérusgráf; (m) A $P_2\cprod\cdots\cprod P_2$ ${2^n}$ csúcsú $n$-kocka.
\ujgyak \label{gyak7-76} \sz{20}
A \textit{tábla}$(n_1,n_2,n_3,n_4,p,w,o)$-ban lehetnek körök vagy többszörös élek?
\ujgyak \label{gyak7-77} \sz{M20}
Legyen adva egy $G$ gráf, amelynek átmérõje $\ge 3$. Bizonyítsuk be, hogy
$\overline{G}$-nek az átmérõje $\le 3$.
\ujgyak \label{gyak7-78}
Legyen $G=(V,E)$ olyan gráf, hogy $\vert V\vert=n$ és $G \cong \overline{G}$ teljesül. 
(Tehát a G gráf \textit{komplementerével megegyezõ}:
$V$-nek van olyan $\varphi$ permutációja, hogy $u \adj v$ pontosan akkor, ha $\varphi(u) \nadj \varphi(v)$ és $u \neq v$.
Elképzelhetõ, hogy $K_n$ élei fekete vagy fehér színnel vannak színezve; a fehér élek egy olyan gráfot definiálnak, 
amely izomorf a fekete élek gráfjával.)

(a) Bizonyítsuk be, hogy $n \mod 4$ értéke $0$ vagy $1$ lehet. Készítsünk ábrát minden olyan gráfhoz, amelyre $n<8$ teljesül.

(b) Bizonyítsuk be, hogy ha $n \mod 4=0$, akkor a $\varphi$ permutációban lévõ minden kör hosszúsága $4$ többszöröse.

(c) Megfordítva, minden $\varphi$ permutációban, amelyben elõfordul ilyen kör, valamilyen G gráfból adódik.

(d) Terjesszük ki az eredményeinket az $n \mod 4=1$ esetre.
\ujgyak \label{gyak7-79} \sz{M22}
Legyen adva $k \ge 0$. Készítsünk egy olyan gráfot, amelynek csúcsai ${0,1,\ldots,4k}$, valamint reguláris és 
komplementerével megegyezõ.
\ujgyak \label{gyak7-80} \sz{M22}
A \ref{gyak7-77}. gyakorlatból következõen a komplementerével megegyezõ gráfoknak $2$ vagy $3$ lehet az átmérõje. 
Ha adva van $k \ge 2$, készítsünk komplementerével megegyezõ gráfot mindkét lehetséges átmérõre, amikor

(a) $V = \{1,2,\ldots,4k\}$; (b) $V = \{0,1,2,\ldots,4k\}$.
\ujgyak \label{gyak7-81} \sz{20}
Egy egyszerû, körmentes irányított gráf komplementere (35) és (36) kiterjesztésével történik úgy, hogy
$\underline{D}$-ben $u\to v$ akkor és csakis akkor teljesül, ha $D$-ben $u \neq v$ és $u\not\to v$.
Melyek a $3$-rendû, komplementerükkel megegyezõ irányított gráfok?
\ujgyak \label{gyak7-82} \sz{M21}
A vonal gráf következõ állításai közül melyek igazak és melyek hamisak?

(a) Ha $G$-t tartalmazza $G'$, akkor $L(G)$ indukált részgráfja $L(G')$-nek.

(b) Ha $G$ reguláris gráf, akkor $L(G)$ is az.

(c) $L(K_{m,n})$ reguláris minden $m,n>0$-ra.

(d) $L(K_{m,n,r})$ reguláris minden $m,n,r>0$-ra.

(e) $L(K_{m,n})\cong K_m\cprod K_n$.

(f) $L(K_4) \cong K_{2,2,2}$.

(g) $L(P_{n+1}) \cong P_n$.

(h) $G$ és $L(G)$ gráfoknak ugyanannyi komponense van.
\ujgyak \label{gyak7-83} \sz{16}
Ábrázoljuk az $\overline{L(K_5)}$ gráfot.
\ujgyak \label{gyak7-84} \sz{M21}
Az $L(K_{3,3})$ gráf komplementerével megegyezõ?
\ujgyak \label{gyak7-85} \sz{M22}
(O. Ore,\angolnevindex{Ore, \O ystein} 1962.) Mely $G$ gráfokra igaz, hogy $G \cong L(G)$?
\ujgyak \label{gyak7-86} \sz{M20}
(R. G. Wilson.\angolnevindex{Wilson, Richard Michael}) Keressünk olyan $6$-od rendû G gráfot, melyre igaz, 
hogy $\underline{G} \cong L(G)$.
\ujgyak \label{gyak7-87} \sz{20}
A Petersen-gráf

(a) $3$ színezhetõ?

(b) $3$ él-színezhetõ?
\hangfig{\epsfbox{\figdir/v4a.88}}
\ujgyak \label{gyak7-88} \sz{M20}
A $W_n = K_1 \adj C_{n-1}$ gráfot $n$-ed rendû \textit{keréknek}\gyakindex{kerékgráf = wheel} nevezzük, ha $n \ge 4$.
Hány kör található benne, mint részgráf?
\hangindent-.75in\hangafter-2\hfill\rlap{\hbox to.75in{\hfil
\smash{\lower7pt\vbox{\halign{\hfil#\hfil\cr
\epsfxsize=.3in\epsfbox{\figdir/v4a.88}\cr
\noalign{\vskip-3pt}\small{$W_8$}\cr}}}\qquad}} 
\ujgyak \label{gyak7-89} \sz{M20}
Bizonyítsuk be a (\ref{keplet7-42}) és (\ref{keplet7-43}) asszociatív szabályokat.
\ujgyak \label{gyak7-90} \sz{M24}
Egy gráfot {\it generáltnak} nevezünk, ha az 1 elemû gráfból algebrailag konstruálható 
a komplementer képzés és/vagy a direkt összeg mûveleteket használva. Például $4$ darab nem izomorf
$3$-ad rendû gráf létezik, és ezek mindegyike generált: $\overline{K_3}=K_1\dirsum K_1\dirsum K_1$ és
a komplementere, $K_3$; $\overline{K_{1,2}}=K_1\dirsum K_2$ és a komplementere, $K_{1,2}$, ahol
$K_2=\overline{K_1\dirsum K_1}$.

Hosszú felsorolás munkája árán kiderül, hogy $11$ darab nem izomorf $4$-ed rendû gráf létezik.
Adjunk algebrai kifejezéseket, amellyel bebizonyíthatjuk, hogy közülük $10$ generált. Melyik nem az?
\ujgyak \label{gyak7-91} \sz{20}
Készítsünk ábrát a $4$ csúcsú gráfokhoz, amelyekre

(a) $K_2\cprod K_2$ (b) $K_2\dprod K_2$; (c) $K_2\sprod K_2$; (d) $K_2\oprod K_2$; (e) $K_2\lprod K_2$; (f) $\overline{K_2}\lprod K_2$; 
(g) $K_2\lprod\overline{K_2}$.
\ujgyak \label{gyak7-92} \sz{21}
A gráfok szorzatára definiált $5$-féle lehetõség mûködik egyszerû irányított gráfokra és közönséges gráfokra is.
Készítsünk ábrát a $4$ csúcsú irányított gráfokhoz, amelyekre

(a)~$K\orie_{2}\cprod K\orie_{2}\,$;
(b)~$K\orie_{2}\dprod K\orie_{2}\,$;
(c)~$K\orie_{2}\sprod K\orie_{2}\,$;

(d)~$K\orie_{2}\oprod K\orie_{2}\,$;
(e)~$K\orie_{2}\lprod K\orie_{2}\,$. 
\ujgyak \label{gyak7-93} \sz{15}
A gráf szorzatok közül melyek viszik át $K_m$ és $K_n$-et $K_{mn}$-be?
\ujgyak \label{gyak7-94} \sz{10}
Az SGB \textit{szó} gráfok\index{szógráf@\textit{szó} gráf = \textit{words} graph} a 
$P_{26}\cprod P_{26}\cprod P_{26}\cprod P_{26}\cprod P_{26}$ indukált részgráfjai?
\ujgyak \label{gyak7-95} \sz{M20}
Ha a $G$ gráf $u$ csúcsának $d_u$ a foka, a $H$ gráf $v$ csúcsának $d_v$ a foka, akkor mennyi a foka az $(u,v)$ csúcsnak a
következõ gráfokban:

(a)~$G\cprod H$?
(b)~$G\dprod H$?
(c)~$G\sprod H$?
(d)~$G\oprod H$?
(e)~$G\lprod H$?
\ujgyak \label{gyak7-96} \sz{M22}
Legyen $A$ $m \times m'$-es mátrix $a_{uu'}$ elemekkel az $u$ sorban és $u'$ oszlopban; 
Legyen $B$ $n \times n'$-es mátrix $b_{vv'}$ elemekkel z $v$ sorban és $v'$ oszlopban. Az $A \otimes B$ \textit{direkt szorzat} 
egy $mn \times m'n'$-es mátrix $a_{uu'}b_{vv'}$ elemekkel az $(u,v)$ sorban és $(u',v')$ oszlopban. Ennél fogva 
$A \otimes B$ a $G \otimes H$ szomszédsági mátrixa lesz, ha $A$ és $B$ rendre a $G$, illetve $H$ szomszédsági mátrixai.

Keressünk hasonló formulákat a következõ mûveletek szomszédsági mátrixára:
(a)~$G\cprod H$;
(b)~$G\sprod H$;
(c)~$G\oprod H$;
(d)~$G\lprod H$.
\ujgyak \label{gyak7-97} \sz{M25}
Keressünk annyi érdekes kapcsolatot a gráf szorzások és összeadások között, amennyit csak tudunk.
(Például az $(A \oplus B) \otimes C = (A \otimes C) \oplus (B \otimes C)$ disztributív szabály 
a mátrixok direkt összegére és szorzatára
indukálja, hogy $(G\dirsum G')\dprod H=(G\dprod H)\dirsum(G'\dprod H)$. Teljesül például az is, hogy 
$\overline{K_m}\cprod H=H\dirsum\cdots\dirsum H$, H-nak $m$ példányára, stb.)
\ujgyak \label{gyak7-98} \sz{M20}
Ha a $G$ gráfnak $k$ komponense van, a $H$ gráfnak pedig $l$ komponense, akkor hány komponense van 
$G\cprod H$-nak és $G\sprod H$-nak?
\ujgyak \label{gyak7-99} \sz{M20}
Legyen $d_G(u,u')$ a $G$ gráfban az $u$ és $u'$ csúcsok távolsága. Bizonyítsuk be, hogy 
%$d_{G\subsqprod H}((u,v),(u',v'))=
$d_{G\cprod H}((u,v),(u',v'))=
d_G(u,u')+d_H(v,v')$, és keressünk hasonló formulát $d_{G\sprod H}((u,v),(u',v'))$-re.
\vspace{-1mm}
\ujgyak \label{gyak7-100} \sz{M21}
Mely összefüggõ gráfok $G\dprod H$ összefüggõek?
\ujgyak \label{gyak7-101} \sz{M25}
Keressük meg az összes olyan összefüggõ $G$ és $H$ gráfot, amelyekre $G\cprod H\cong G\dprod H$.
\vspace{-4mm}
\ujgyak \label{gyak7-102} \sz{M20}
Milyen egyszerû algebrai formulát lehet adni a {\it király lépés} gráfjára egy $m \times n$-es táblán?
(Egy lépést tesz vízszintesen, függõlegesen vagy átlósan.)
\ujgyak \label{gyak7-103} \sz{20}
Fejezzük be a (\ref{keplet7-54})-es tablót. Ezen kívül alkalmazzuk a H algoritmust a $866444444$ sorozatra.
\ujgyak \label{gyak7-104} \sz{18}
Magyarázzuk el az $i,t,r$ változók manipulálását a H3 és H4 lépésben.
\ujgyak \label{gyak7-105} \sz{M34}
Tegyük fel, hogy $d_1 \ge \cdots \ge d_n \ge 0$, és legyen $c_1 \ge \cdots c_{d_1}$ ennek konjugáltja, úgy mint 
a H algoritmusban. Bizonyítsuk be, hogy $d_1 \ldots d_n$ pontosan akkor grafikus, ha $d_1+ \cdots + d_n$ páros és 
$d_1 + \cdots + d_k \le c_1 + \cdots c_k -k$, ahol $1 \le k \le s$ és $s$ az a maximális érték, melyre $d_s \ge s$.
\ujgyak \label{gyak7-106} \sz{20}
Igaz-e a következõ állítás: Ha $d_1 = \cdots = d_n = d <n$ és $nd$ páros, akkor a H algoritmus {\it összefüggõ gráfot} konstruál.
\ujgyak \label{gyak7-107} \sz{M21}
Bizonyítsuk be, hogy egy komplementerével megegyezõ gráf $d_1 \ldots d_n$ foksorozata $1 \le j \le n/2$-re teljesíti a $d_j+d_{n+1-j}=n-1$ és
a $d_{2j-1}=d_{2j}$ egyenlõségeket.
\ujgyak \label{gyak7-108} \sz{M23}
Tervezzünk egy olyan H algoritmushoz hasonló algoritmust, amely adott ${1, \ldots, n}$ csúcsok és
azokhoz tartozó $d_k^{-}$ és a $d_k^{+}$ be- és kifokok esetén
{ó\textit egyszerû irányított gráfot} konstruál, ha létezik egyáltalán ilyen gráf.
\ujgyak \label{gyak7-109} \sz{M20}
Tervezzünk egy olyan H algoritmushoz hasonló algoritmust, amely adott ${1, \ldots, m+n}$ csúcsok és azokhoz 
tartozó $d_k$ fokszámok esetén \textit{páros gráfot}
konstruál, ha létezik egyáltalán ilyen gráf; Minden $j \adj k$ élre teljesülnie kell, hogy $j \le m$ és $k>m$.
\ujgyak \label{gyak7-110} \sz{M22}
A H algoritmus használata nélkül mutassunk egy direkt konstrukciót arra, hogy ha $n>d1 \ge \cdots \ge d_n \ge d_1-1$ és
$d_1 + \cdots + d_n$ páros, akkor a $d_1, \ldots, d_n$ grafikus.
\ujgyak \label{gyak7-111} \sz{25}
Legyen adva a $G$ gráf a $V=\{1,\ldots,n\}$ csúcsokkal, és legyen $d_k$
a $k$ foka és $\max(d_1,\ldots,$ $d_n)=d$. Bizonyítsuk be, hogy létezik egy olyan $N$ egész, $n\le N \le 2n$ és egy 
$H$ gráf, amelynek csúcsai $\{1,\ldots,N\}$ úgy, hogy $H$ reguláris $d$ fokkal és $H\rest V=G$. 
Magyarázzuk meg, hogy miként lehet ilyen reguláris gráfot készíteni a lehetõ legkisebb $N$ esetén. 
\ujgyak \label{gyak7-112} \sz{20}
A \textit{mérföldek}$(128,0,0,0,0,127,0)$
hálóban van három, egyenlõ távolságra lévõ város?
Ha nem, akkor mely $3$ város van a legközelebb az egyenlõ oldalú háromszög elrendezéshez?
\ujgyak \label{gyak7-113} \sz{05}
Ha $H$ egy hipergráf $m$ éllel és $n$ csúccsal,
akkor mennyi sora és oszlopa van az illeszkedési mátrixának?
\ujgyak \label{gyak7-114} \sz{M20}
Tegyük fel, hogy a (\ref{keplet7-26})-ban lévõ multigráfot hipergráfnak tekintjük.
Mi az ennek megfelelõ illeszkedési mátrix? Mi az ennek megfelelõ páros gráf?
\ujgyak \label{gyak7-115} \sz{M20}
Ha $B$ a $G$ gráfnak az illeszkedési mátrixa, akkor mi a 
$B^TB$ és $BB^T$ szimmetrikus mátrixok jelentõsége?
\ujgyak \label{gyak7-116} \sz{M17}
Írja le az éleit a teljes, páros, $r$-egyenletes $K^{(r)}_{m,n}$ hipergráfnak.
\ujgyak \label{gyak7-117} \sz{M22}
Hány, egymással nem izomorf 1-egyenletes hipergráfnak van $m$ éle és $n$ csúcsa? (Többszörös él elõfordulhat.) 
Soroljuk fel az összeset $m=4$ és $n=3$ esetén.
\ujgyak \label{gyak7-118} \sz{M20}
A \idez{hipererdõ} egy olyan hipergráf, ami körmentes.

Ha egy hipererdõnek $m$ éle, $n$ csúcsa, és $p$ komponense van, akkor mennyi lesz a csúcsai fokszámának összege?
\ujgyak \label{gyak7-119} \sz{M18}
Mely hipergráf feleltethetõ meg a (60)-nak a $(\bar x_1\lor\bar x_2\lor\bar x_3)$ záró tagot elhagyva?
\ujgyak \label{gyak7-120} \sz{M20}
Definiáljuk az {\it irányított hipergráfot} az irányított gráfok általánosításával. 
\ujgyak \label{gyak7-121} \sz{M19}
Legyen adva a $H=(V,E)$ hipergráf, és legyen $I(H)=(V,F)$, ahol 
$F$ a $H$ összes maximálisan független halmazainak családja.

Fejezzük ki $\chi(H)$-t a \/ $\vert V\vert$, $\vert F\vert$, és az $\alpha(I(H)^T)$ segítségével. 
\ujgyak \label{gyak7-122} \sz{M24}
Találjunk egy maximálisan független halmazt és egy minimális színezést a következõ hármas rendszereknek:

(a) (\ref{keplet7-56}) hipergráf; (b) a Petersen gráf duálisa.
\ujgyak \label{gyak7-123} \sz{17}
Mutassuk meg, hogy a $K_n\cprod K_n$ optimális színezései ekvivalensek egy híres kombinatorikai probléma megoldásával.
\ujgyak \label{gyak7-124} \sz{M22}
Mi a \textit{Chvátal-gráf}\angolnevindex{Chvátal, Václav} (2(f) ábra) színezési száma?
\ujgyak \label{gyak7-125} \sz{M48}
Milyen $g$ értékhez van 4-reguláris, 4-színezési számú, $g$ kerületû gráf? 
\ujgyak \label{gyak7-126} \sz{M22}
Találjunk optimális színezést a $C_m\sprod C_n$ \idez{\textit{király alapú tórusznak}}, ha $m,n \ge 3$.
\ujgyak \label{gyak7-127} \sz{M22}
Bizonyítsuk be, hogy (a) $\chi(G)+\chi(\overline G)\le n+1$ és 
(b) $\chi(G)\chi(\overline G)\ge n$ ha 
$G$ ~$n$-ed rendû gráf, 
és találjunk olyan gráfokat, ahol egyenlõség áll fenn.
\ujgyak \label{gyak7-128} \sz{M18}
Fejezzük ki $\chi(G\cprod H)$-t a $\chi(G)$ és $\chi(H)$-vel, ahol $G$ és $H$ gráfok.
\ujgyak \label{gyak7-129} \sz{23}
Írjuk le a $8\times 8$-as (\ref{keplet7-37}) \textit{királynõ gráfnak} a maximális klikkjeit.
\ujgyak \label{gyak7-130} \sz{M20}
Hány maximális klikkje van egy teljes, $k$-paritású gráfnak?
\ujgyak \label{gyak7-131} \sz{M20}
Legyen $N(n)$ az $n$ csúcsú gráf maximális klikkjeinek legnagyobb lehetséges száma. 
Bizonyítsuk be, hogy $3^{\lfloor n/3\rfloor}\le N(n)\le 3^{\lceil n/3\rceil}$.
\ujgyak \label{gyak7-132} \sz{M20}
$G$-t \textit{alig színezhetõnek}\gyakindex{alig színezhetõ gráf = tightly colorable graph}
\index{gráf = graph!alig színezhetõ gráf = tightly colorable graph} nevezzük, ha $\chi(G)=\omega(G)$.
Bizonyítsuk be, hogy $\chi(G\sprod H)=\chi(G)\chi(H)$ ha $G$ és $H$ alig színezhetõek.
\ujgyak \label{gyak7-133} \sz{21}
\parshape 12
0pt 212.51pt
0pt 204.45pt
0pt 198.75pt
0pt 194.93pt
0pt 192.72pt
0pt 192pt
0pt 192.72pt
0pt 194.93pt
0pt 198.75pt
0pt 
204.45pt
0pt 212.51pt
0pt 224.04pt
Az itt látható \idez{\textit{zenei gráf}} egy kellemes lehetõséget ad arra, hogy áttekintsünk számos definíciót, 
amit ebben a részben adtunk meg, hiszen a tulajdonságai könnyen elemezhetõk.  Határozzuk meg a  
(a) \textit{rendjét};
(b) \textit{méretét};
(c) \textit{kerületét};
(d) \textit{átmérõjét};
(e) $\alpha(G)$ \textit{függetlenségi számát};
(f) $\chi(G)$ \textit{színezési számát};
(g) $\chi(L(G))$ \textit{él-színezési számát};
(h) $\omega(G)$ \textit{klikk számát};
(i) algebrai alakját jól ismert kisebb gráfok szorzataként.

Mekkora a mérete 
(j) egy \textit{minimum csúcs lefedésnek}?
(k) a \textit{maximális illesztésnek}?

A $G$ gráf
(l) reguláris?
(m) síkgráf?
(n) összefüggõ?
(o) irányított?
(p) szabad fa?
(q) Hamilton-gráf?
\epsfbox{\figdir/v4a.1812} 
\ujgyak \label{gyak7-134} \sz{M22}
Hány \textit{automorfizmusa} van a zenei gráfnak?
\ujgyak \label{gyak7-135} \sz{F26}
Tegyük fel, hogy egy zeneszerzõ tesz egy \textit{véletlen lépést} a \textit{zenei gráfban} a $C$ csúcsból kiindulva, 
és utána minden lépésnél $5$ ehhez teljesen hasonló döntést hoz. Mutassuk meg, hogy páros számú lépés után, 
több az esélye, hogy a séta a $C$ csúcsban fejezõdik be, mint bármely más csúcsban. Egy $12$ lépéses sétánál 
mennyi a pontos valószínûsége annak, hogy a séta a $C$-bõl $C$-be megy?
\ujgyak \label{gyak7-136} \sz{F23}
Egy \textit{Cayley irányított gráf} egy olyan irányított gráf, amelynek $V$ csúcsai egy adott csoport elemei, és amelynek 
irányított élei $v\dadj v\alpha_j$, ahol $1\le j\le d$ és minden csúcsa $v$,
ahol $(\alpha_1,\ldots,\alpha_d)$ fix elemek a csoportban.

A \textit{Cayley-gráf} egy olyan Cayley irányított gráf, ami egyben gráf is.
A \textit{Petersen-gráf} Cayley-gráf? 
\epsfbox{\figdir/v4a.1520} \epsfbox{\figdir/v4a.1521} 
\ujgyak \label{gyak7-137} \sz{M25}
({\it Általánosított tóruszok.}) Egy $m\times n$-es tórusz tekinthetõ a sík egy felosztásának. 
Képzeljük el például, hogy az (\ref{keplet7-50})-beli $3\times 4$-es tórusz végtelen sok másolata 
el van helyezve egy rácsban, ahogy ez a fenti ábra bal oldalán látható; egy megadott csúcsból tudunk mozogni északra, 
délre, keletre, vagy nyugatra a tórusz egy másik csúcsába. A csúcsok itt meg vannak számozva, tehát egy észak lépés a
~$v$-bõl a $(v+4)\mod 12$-be megy, és egy kelet lépés $(v+3)\mod 12$-be stb. 
A jobb oldali ábra ugyanazt a tóruszt mutatja más alakú elrendezéssel; 
\textit{Bármely} utat választjuk a $12$ lehetséges útból: 
$\{0,1,\ldots,11\}$, az ki fogja parkettázni a síkot, pontosan ugyanazzal az alapul vett gráffal.

Ha egy alakzatnak az eltolt másolatát alkalmazzuk, akkor is ki fogják parkettázni a síkot, 
ha \textit{általánosított} tóruszt alkotnak, 
amennyiben az $(x,y)$ cella ugyanannak a csúcsnak felel meg, mint az $(x+a,y+b)$ és $(x+c,y+d)$ cellák, 
ahol $(a,b)$ és $(c,d)$ egész vektorok, valamint $n=ad-bc>0$. 
Az általánosított tórusznak $n$ pontja lesz. Ezek az $(a,b)$ és $(c,d)$ vektorok  
$(4,0)$ és $(0,3)$ értékûek a fenti $3\times 4$-es példában; amikor pedig az értékük
$(5,2)$ és $(1,3)$, akkor 
$$\epsfbox{\figdir/v4a.1522}\koz.$$
Itt $n=13$, és egy észak lépés $v$-bõl $(v+4)\mod 13$-ba megy; egy kelet lépés $(v+1)\mod 13$-be. Bizonyítsuk be, hogy ha 
$lnko(a,b,c,d)=1$, akkor az ilyen általánosított tóruszok csúcsaihoz mindig hozzá lehet rendelni $\{0,1,\ldots,n{-}1\}$ egész 
címkéket oly módon, hogy a $v$ szomszédai $(v\pm p)\mod n$ és $(v\pm q)\mod n$ valamilyen $p$ és $q$ egész értékekre.
\ujgyak \label{gyak7-138} \sz{F27}
A \ref{gyak7-137}. gyakorlatot folytatva, mi lehet egy jó módszer a 
$k$-dimenziós $x=(x_1,\ldots,x_k)$ csúcsok egy címkézéséhez, 
amikor adottak $\alpha_j$ egész vektorok úgy, hogy minden ~$x$ vektor ekvivalens 
$x+\alpha_j$-vel, ahol $1\le j\le k$?
 
Illusztráljuk a módszert a $k=3$,
$\alpha_1=(3,1,1)$, $\alpha_2=(1,3,1)$, $\alpha_3=(1,1,3)$ esetben.
\ujgyak \label{gyak7-139} \sz{M22}
Legyen $H$ egy $h$-ad rendû fix gráf, és legyen 
$\#(H{:}G)$ azon elõfordulások száma, amikor a $H$ elõfordul egy adott $G$ gráf {\it indukált részgráfjában}. 
Ha $G$-t véletlenszerûen választjuk ki a $V=\{1,2,\ldots,n\}$ csúcsú, összesen $2^{n(n-1)/2}$ gráf közül, 
mennyi az átlagos értéke $\#(H{:}G)$-nek, ha $H$ 
(a)~$K_h$; (b)~$P_h$, ahol $h>1$; (c)~$C_h$, ahol $h>2$; (d)~tetszõleges?
\ujgyak \label{gyak7-140} \sz{M30}
A $G$ gráfot \textit{arányosnak} nevezzük, ha az indukált részgráfjainak száma 
$\#(K_3{:}G)$, $\#(\overline{K_3}{:}G)$, és
$\#(P_3{:}G)$, amelyek mindegyike megfelel a \ref{gyak7-139}. gyakorlatban kiszámolt értékeknek.
\begin{itemize}
\item
Mutassuk meg, hogy a $W_8$ \textit{kerékgráf}\gyakindex{kerékgráf = wheel graph}\gyakindex{gráf = graph!kerékgráf = wheel graph} 
a \ref{gyak7-88}. gyakorlatban arányos ebben az értelemben.
\item Bizonyítsuk be, hogy $G$ pontosan akkor arányos, ha $\#(K_3{:}G)=
\frac{1}{8}\binom{n}{n3}$ és a csúcsainak $d_1\ldots d_n$ \textit{foksorozata}\gyakindex{foksorozat = degree sequence} 
kielégíti a következõ egyenlõségeket: 
$$d_1+\cdots+d_n=\Bigl(\binom{n}{2}\Bigr),\qquad
  %d_1^2+\cdots+d_n^2=\fraction{n}{2}\Bigl(\binom{n}{2}\Bigr)\koz.\EQNO(*)$$ 
d_1^2+\cdots+d_n^2=\frac{n}{2}\Bigl(\binom{n}{2}\Bigr)\koz.\hfill (*)$$
\end{itemize}
\ujgyak \label{gyak7-141} \sz{26}
A \ref{gyak7-140}(b) gyakorlatban leírt feltétel csak akkor áll fenn, ha $n\mod 16\in \{0,1,8\}$. 
Írjunk programot az összes olyan arányos gráf megtalálására, aminek $n=8$ csúcsa van.
\ujgyak \label{gyak7-142} \sz{M30}
(S. Janson\angolnevindex{Janson, Carl Svante} és J. Kratochvíl,\angolnevindex{Kratochvíl, Jan} 1991.) 
Bizonyítsuk be, hogy egy $4$ vagy több csúcsú $G$ 
gráf sem lehet \idez{túlarányos} abban az értelemben, hogy a $(H{:}G)$ részgráf száma  
megegyezik a \ref{gyak7-139}. gyakorlatban kiszámolt értékkel mind a $11$ lehetséges nemizomorf 4-ed rendû $H$ gráfban.
\textit{Útmutató:} $(n-3)\# (K_3{:}G)= 4\# (K_4{:}G)+2\# (K_{1,1,2}{:}G)+\# (K_1{\dirsum}K_3{:}G)$.
\ujgyak \label{gyak7-143} \sz{M25}
Legyen $A$ tetszõleges mátrix, melynek $m>1$ {\it különbözõ sora}, és $n\ge m$ oszlopa van. 
Bizonyítsuk be, hogy legalább egy oszlopát törölhetjük az $A$-nak 
anélkül, hogy a mûvelet után 2 megegyezõ sor keletkezne.
\ujgyak \label{gyak7-144} \sz{21}
Legyen $X$ egy $m\times n$-es mátrix, amelynek $x_{ij}$ elemei 0,~1, vagy ~$\ast$. 
Az $X$ mátrix \textit{kiegészítése}\gyakindex{mátrix kiegészítése = completion of a matrix} egy olyan $X^\ast$
 mátrix, ahol minden $\ast$-ot $0$-ra vagy $1$-re cserélünk ki. 
Bizonyítsuk be, hogy a lehetõ legkevesebb sorral rendelkezõ kiegészítõ 
mátrix meghatározásának problémája ekvivalens egy gráf 
\textit{színezési számának}\gyakindex{színezési szám = chromatic number} megkeresésével.
\ujgyak \label{gyak7-145} \sz{25}
(R. S. Boyer\angolnevindex{Boyer, Robert Stephen} és J. S. Moore,\angolnevindex{Moore, Ronald Williams} 1980.) 
Tegyük fel, hogy az $a_1\ldots a_n$ tömb tartalmaz egy \textit{gyakori elemet},\gyakindex{gyakori elem = majority element} 
nevezetesen egy értéket, ami több, mint $n/2$ alkalommal elõfordul. Készítsünk olyan algoritmust, ami megtalálja az 
elemet kevesebb, mint $n$ összehasonlítással.
\textit{Útmutatás}: Ha $n \ge 3$ és $a_{n-1}\neq a_n$, akkor az $a_1\ldots a_n$
gyakori eleme egyben gyakori eleme az $a_1\ldots a_{n-2}$-nek is.
\end{gyak}
}

\chapter*{MEGOLDÁSOK}
\addcontentsline{toc}{chapter}{MEGOLDÁSOK}
\markboth{\sf 7. KOMBINATORIKUS ELEMZÉS (4. kötet, 0. rész)}{\sf 7.0. ALFEJEZET GYAKORLATAINAK MEGOLDÁSA}
\pagestyle{myheadings}
\section*{A 7.0. alfejezet gyakorlatainak megoldása}
\addcontentsline{toc}{section}{A 7.0. alfejezet gyakorlatainak a megoldása}
\small{
\begin{gyak}
%%% 1
\ujgyak \label{megold70-1}
%%% 2
\ujgyak \label{megold70-2}
\vspace{3mm}
\textbf{\ldots}
\vspace{3mm}
\setcounter{gyakcounter}{7}
%%% 8
\ujgyak \label{megold70-8}
\vspace{3mm}
\textbf{\ldots}
\vspace{3mm}
%\setcounter{gyakcounter}{80}
%%% 81
\setcounter{gyakcounter}{68}
\ujgyak \label{megold7-69}
Elõször legyen $\texttt{BEFOK}(v)\gets 0$ minden $v$ csúcsra. 
Utána alkalmazzuk (\ref{keplet7-31})-et minden $v$-re, és legyen $u\gets\texttt{TIP}($a$)$ és 
$\texttt{BEFOK}(u)\gets\texttt{BEFOK}(u)+1$ a mini-algoritmus második sorában.

Ahhoz, hogy az SGB formátumban elvégezzük a \idez{minden $v$-re} mûveletet, elõbb legyen 
$v\gets\texttt{CSÚCSOK}(g)$; majd, amíg $v<\texttt{CSÚCSOK}(g)+\texttt{N}(g)$, végezzük el a mûveletet, és legyen $v\gets v+1$.
\ujgyak \label{megold7-70}
A B1-es lépés egyszer kerül végrehajtásra (de $O(n)$ idõbe kerül).

A (B2, B3, \dots, B8) lépések egyenként $(n+1,n,n,m+n,m,m,n)$ alkalommal kerülnek végrehajtásra, mindegyik $O(1)$ költséggel. 
\ujgyak \label{megold7-71}
Sok lehetõség van. Mi itt 32-bites mutatókat alkalmazunk, és mindegyik relatív egy \texttt{Sor} szimbolikus címhez, ami 
az \texttt{Adat\_Szegmens}-ben található.

A következõ deklaráció segítségével alakíthatjuk ki azokat a szabályokat, hogy alap SGB adatstruktúrával tudjunk dolgozni.

\newpage
\assembly{
\komment{VSIZE IS 32 ;ASIZE IS 24\hspace{17mm}Csomópont méretek}\cr
\komment{ARCS IS 0 ;COLOR IS 8 ;LINK IS 12\hspace{2mm}Eltolások a csúcsmezõkben}\cr
\komment{TIP IS 0 ;NEXT IS 4\hspace{25mm}Eltolás az irányított él mezõben}\cr
\komment{arcs  GREG Pool+ARCS ;color GREG Pool+COLOR ;link  GREG Pool+LINK}\cr
\komment{tip   GREG Pool+TIP ;next  GREG Pool+NEXT}\cr
\komment{u  GREG ;v  GREG  ;w GREG ;s GREG ;a GREG ;mone GREG -1}\cr
AlgB  &BZ  &n,Success&Kilépés, ha a gráf nullgráf.\cr
      &MUL &\$0,n,VSIZE&\underline{\textit{B1. Kezdõértékek megadása.}}\cr
      &ADDU&v,v0,\$0&$v\gets v_0+n$.\cr
      &SET &w,v0&$w\gets v_0$.\cr
1H&STT &mone,color,w&$COLOR(w)\gets-1$.\cr
       &ADDU&w,w,VSIZE&$w\gets w+1$.\cr
       &CMP &\$0,w,v\cr
       &PBNZ&\$0,1B&Repeat until $w=v$.\cr
0H     &SUBU&w,w,VSIZE&$w\gets w-1$.\cr
3H     &LDT &\$0,color,w&\underline{\textit{B3. Ha szükséges, $w$ színezése.}}\cr
       &PBNN&\$0,2F&To B2 if $COLOR($w$)\ge 0$.\cr
       &STCO&0,link,w&$COLOR(w)\gets 0$, $LINK(w)\gets\Lambda$.\cr
       &SET &s,w&$s\gets w$.\cr
4H     &SET &u,s&\let\|=\Rightarrow\underline{\textit{B4. Tegyük${}\|u$-t a verembe.}} Set $u\gets s$.\cr
       &LDTU&s,link,s&$s\gets LINK(s)$.\cr
       &LDT &\$1,color,u\cr
       &NEG &\$1,1,\$1&$\$1\gets 1-COLOR(u)$.\cr
       &LDTU&a,arcs,u&$a\gets ARCS(u)$.\cr
5H     &BZ  &a,8F&\underline{\textit{B5. Végeztünk $u$-val?}} Ha $a=\Lambda$, menjünk B8-ra.\cr
5H     &LDTU&v,tip,a&$v\gets TIP(a)$.\cr
6H     &LDT &\$0,color,v&\underline{\textit{B6. v feldolgozása.}}\cr
       &CMP &\$2,\$0,\$1&(A program itt meglehetõsen okos)\cr
       &PBZ &\$2,7F&To B7 if $COLOR(v)=1-COLOR(u)$.\cr
       &BNN &\$0,Failure&Nem sikerül, ha $COLOR(v)=COLOR(u)$.\cr
       &STT &\$1,color,v&$COLOR(v)\gets 1-COLOR(u)$.\cr
       &STTU&s,link,v&$LINK(v)\gets s$.\cr
       &SET &s,v&$s\gets v$.\cr
7H     &LDTU&a,next,a&\underline{\textit{B7. Ciklus a szerint}}. Legyen $a\gets NEXT(a)$.\cr
       &PBNZ&a,5B&To B5 if $a\neq\Lambda$.\cr
8H     &PBNZ&s,4B&\underline{\textit{B8. A verem nem üres?}} Ha $s\neq\Lambda$, menj B4-re.\cr
2H     &CMP &\$0,w,v0&\underline{\textit{B2. Kész?}}\cr
       &PBNZ&\$0,0B&Ha $w\neq v_0$, csökkentsük $w$-t és menjünk B3-ra.\cr
Siker&LOC&@&(Sikeres befejezés)\quad\slug
}
	   
\medskip
\smallskip
%\def\1#1{\multispan3{\hskip\parindent\tt#1\quad}}\ansmmixthree
%\1{VSIZE IS 32 ;ASIZE IS 24}&Csomópont méret\cr
%\1{ARCS IS 0 ;
%COLOR IS 8 ;LINK IS 12}&Eltolás a csúcs mezõben\cr
%\1{TIP IS 0 ;NEXT IS 4}&Eltolás az irányított él mezõben\cr
%\noalign{\smallbreak}
%arcs  GREG Pool+ARCS ;
%color GREG Pool+COLOR ;link  GREG Pool+LINK\hidewidth\cr
%tip   GREG Pool+TIP ;next  GREG Pool+NEXT\hidewidth\cr
%u  GREG ;v  GREG  ;w GREG ;s GREG ;a GREG ;
%mone GREG -1\hidewidth\cr
%\noalign{\smallbreak}
%AlgB  &BZ  &n,Success&
%Ha a zérusgráf, akkor kilépünk.\cr
%  &MUL &$0,n,VSIZE&\undertext B1. Inicializálás.
%\\\cr
%  &ADDU&v,v0,$0&$v\gets v_0+n$.\cr
%  &SET &w,v0&$w\gets v_0$.\cr
%1H&STT &mone,color,w&$\.{COLOR($w$)}\gets-1$.\cr
%  
%&ADDU&w,w,VSIZE&$w\gets w+1$.\cr
%  &CMP &$0,w,v\cr
%  &PBNZ&$0,1B&Ciklus amíg $w=v$.\cr
%0H&SUBU&w,w,VSIZE&$w\gets w-1$.\cr
%3H&LDT &$0,color,w&\undertext B3. 
%A $w$ szín, ha szükséges.\\\cr
%  &PBNN&$0,2F&B2-höz 
%ha $\.{COLOR($w$)}\ge0$.\cr
%  &STCO&0,link,w&$\.{COLOR($w$)}\gets0$, $\.{LINK($w$)}\gets\Lambda$.\cr
%  
%&SET &s,w&$s\gets w$.\cr
%4H&SET &u,s&\let\|=\Rightarrow\undertext B4. Stack${}\|u$.\\ 
%Legyen $u\gets s$.\cr
%  &LDTU&s,link,s&$s\gets\.
%{LINK($s$)}$.\cr
%  &LDT &$1,color,u\cr
%  &NEG &$1,1,$1&$\$1\gets1-\.{COLOR($u$)}$.\cr
%  &LDTU&a,arcs,u&$a\gets\.{ARCS($u$)}$.\cr
%5H&BZ  &a,8F&\undertext B5. 
%$u$-val kész vagyunk?\\ To B8 if $a=\Lambda$.\cr
%5H&LDTU&v,tip,a&$v\gets\.{TIP($a$)}$.\cr
%6H&LDT &$0,color,v&\undertext B6. 
%$v$ feldolgozása.\\\cr
%  &CMP &$2,$0,$1&(Itt a program kissé ravasz)\cr
%  &PBZ &$2,7F&B7-hez ha $\.{COLOR($v$)}=1-\.{COLOR($u$)}$.\cr
%  &BNN &$0,
%Failure&Nem sikerül,ha$\.{COLOR($v$)}=\.{COLOR($u$)}$.\cr
%  &STT &$1,color,v&$\.{COLOR($v$)}\gets1-\.{COLOR($u$)}$.\cr
%  &STTU&s,link,v&$\.{LINK($v$)}\gets s$.\cr
%  
%&SET &s,v&$s\gets v$.\cr
%7H&LDTU&a,next,a&\undertext B7. 
%$a$-val ismétlünk.\\ 
%Legyen $a\gets\.{NEXT($a$)}$.\cr
%  &PBNZ&a,5B&B5-höz ha $a\ne\Lambda$.
%\cr
%8H&PBNZ&s,4B&\undertext B8. A verem nem üres?\\ B4-hez ha $s\ne\Lambda$.\cr
%2H&CMP &$0,w,v0&\undertext B2. 
%Kész?\\\cr
%  &PBNZ&$0,0B&Ha $w\ne v_0$, csökkentsük $w$-t és menjünk B3-ra.\cr
%Success&LOC&@&(Sikeres befejezés)\quad\slug\cr
%\endmmix 

\ujgyak \label{megold7-72}
(a) Ez a feltétel tisztán invariáns marad, amikor a csúcs bekerül a verembe, vagy kikerül onnan.

(b) A $v$ csúcs ki lett már színezve, de még nincs felfedezve, mivel minden felfedezett csúcs szomszédai már megfelelõ színûek.

(c) Éppen azelõtt a lépés elõtt, mielõtt beállítjuk $s\gets v$-t a B6-os lépésben, legyen \texttt{SZÜLÕ}$(v) \gets u$,
ahol \texttt{SZÜLÕ} egy új segédmezõ. Továbbá, mielõtt sikeresen befejezõdne a mûködés ebben a lépésben, tegyük a következõt: 
\idez{Ismétlõdõen tegyük a kimenetre \texttt{NÉV}$(u)$-t, és legyen $u\gets$\texttt{SZÜLÕ}$(u)$, amíg $u = $\texttt{SZÜLÕ}$(v)$; 
majd tegyük kimenetre \texttt{NÉV}$(u)$-t és \texttt{NÉV}$(v)$($v$)-t.} 
\ujgyak \label{megold7-73}
$K_{10}$. (Továbbá, a \textit{véletlen\_gráf}$(10,100,0,1,1,0,0,0,0,0)$ a $J_{10}$.)
\ujgyak \label{megold7-74}
A \textit{rosszaság}-nak $22$ a kifoka; nincs másik olyan csúcs, aminek a kifoka $>20$.
\ujgyak \label{megold7-75}
Legyenek az $(n_1,n_2,n_3,n_4,p,w,o)$ paraméterek rendre

(a) $(n,0,0,0,-1,0,0)$;

(b) $(n,0,0,0, 1,0,0)$;

(c) $(n,0,0,0, 1,1,0)$;

(d) $(n,0,0,0,-1,0,1)$;

(e) $(n,0,0,0, 1,0,1)$;

(f) $(n,0,0,0, 1,1,1)$;

(g) $(m,n,0,0, 1,0,0)$;

(h) $(m,n,0,0, 1,2,0)$;

(i) $(m,n,0,0, 1,3,0)$;

(j) $(m,n,0,0,-1,0,0)$;

(k) $(m,n,0,0, 1,3,1)$;

(l) $(n,0,0,0, 2,0,0)$;

(m) $(2,-n,0,0,1,0,0)$. 
\ujgyak \label{megold7-76}
Igen, például a \ref{megold7-75}(c) válaszban a $C_1$ és $C_2$-ben. 
(De valódi hurok elõfordulhat a $p<0$ esetben, hiszen az $x\dadj y=x+k\delta$
 irányított élek $k=1, 2, \dots$ esetén generálásra kerülnek egészen addig,
amíg $y$ kilép a tartományból, vagy $y=x$.) 
\ujgyak \label{megold7-77}
Tegyük fel, hogy $x$ és $y$ olyan csúcsok, melyekre igaz, hogy $d(x,y)>2$. Így $x\not{-} y$;
és ha $v$ bármely más csúcs, akkor vagy $v\not{-} x$, vagy $v\not{-} y$. 
Ezek az összefüggések $\overline G$-ban megengednek 
bármely két $u$ és $v$ csúcs között egy legfeljebb $3$ hosszúságú utat. 
\ujgyak \label{megold7-78}
(a) Az élek száma ${n\choose2}/2$, egésznek kell lennie.

A legkisebb példa $K_0$, $K_1$, $P_4$, $C_5$, és \epsfbox{\figdir/v4a.1614}.

(b) Ha $q$ egy tetszõleges páratlan szám, 
akkor $u\adj v$ akkor és csakis akkor, ha $\varphi^q(u)
\nadj\varphi^q(v)$. Ezért $\varphi^q$-nek nem lehet két fixpontja,
és nem lehet benne 2-kör.\par

(c) $V$-nek egy ilyen permutációja egyben definiál egy újabb $\widehat\varphi$
 permutációt a $K_n$ élein, 
mivel $\{u,v\}\mapsto
\widehat\varphi(\{u,v\})=\{\varphi(u),\varphi(v)\}$, és könnyen belátható, hogy a
~$\widehat\varphi$ köreinek a hossza mind ~4 többszöröse.

Ha $\widehat\varphi$-ben $t$ kör van, akkor $2^t$ komplementerével megegyezõ gráfot kapunk úgy, 
hogy minden körnek az éleit váltakozó színnel színezzük.\par

(d) Ez esetben $\varphi$-nek van egy egyedi $v$ fixpontja, és $G'=G\setminus v$ a komplementerével megegyezõ. 
Tegyük fel, hogy $\varphi$-ben $r$ kör van ~$(v)$-n kívül;
ekkor $\widehat\varphi$-ben $r$ kör van, amely magába foglalja azokat az éleket,
amelyek érintik a ~$v$ csúcsot, és $2^r$ módon terjeszthetõ ki a $G'$ gráf egy ~$G$ gráffá.\par

{\textit{Hivatkozások}: Sachs\angolnevindex{Sachs, Horst} \cite{Sachs1962} 
és Ringel\angolnevindex{Ringel, Gerhard} \cite{Ringel1963}}.
\ujgyak \label{megold7-79}
1. megoldás (H. Sachs) $\varphi=(1\,2\,\ldots\,4k)$ esetén:
Legyen $u\adj v$, ha $u>v>0$ és $u+v\mod 4\le 1$; ezzel együtt
$0\adj v$ ha $v\mod 2=0$.

2. megoldás, $\varphi=(a_1\,b_1\,c_1\,d_1)\ldots(a_k\,b_k\,c_k\,d_k)$ esetén,
ahol $a_j=4j-3$, $b_j=4j-2$, $c_j=4j-1$, és $d_j=4j$:
Legyen $0\adj b_j\adj a_j\adj c_j\adj d_j\adj 0$, ha $1\le j\le k$, és
$a_i\adj a_j\adj b_i\adj d_j\adj c_i\adj c_j\adj d_i\adj b_j\adj a_i$,
ha $1\le i<j\le k$.
\ujgyak \label{megold7-80}
(G. Ringel megoldása.) Legyen $\varphi$ olyan, mint a \ref{gyak7-79}. gyakorlat 2. megoldásában. Legyen $E_0$ a $3k$ 
$b_j\adj a_j\adj c_j\adj d_j$ él, ha $1\le j\le k$; legyen $E_1$ a $8{k\choose2}$ él $\{a_i,b_i,c_i,d_i\}$ és $\{b_j,d_j\}$ 
között, ha $1\le i<j\le k$; legyen $E_2$ a $8{k\choose2}$ él $\{a_i,b_i,c_i,d_i\}$ és $\{a_j,c_j\}$ között, ha $1\le i<j\le k$.
Az ~(a) esetben, $E_0\cup E_1$ ~2 átmérõt ad; $E_0\cup E_2$ pedig 3 átmérõt. A (b) eset hasonló, de itt hozzáadjuk a 
következõ $2k$ élt: $b_j\adj 0\adj d_j$-t $E_1$-hez, $a_j\adj 0\adj c_j$-t $E_2$-höz.
\ujgyak \label{megold7-81}
$C\orie_{\!3}$, $K\orie_{\!3}$, $D = \epsfbox{\figdir/v4a.585}$, és $\epsfbox{\figdir/v4a.587}$. 

(A $D$ irányított gráf $D^T$ \textit{fordítottját}
megkaphatjuk úgy, hogy irányított éleinek megfordítjuk az irányát.

16, egymással nem izomorf \textit{egyszerû, 3-ad rendû, irányított, körmentes gráf} van,
 közülük 10 \textit{önfordított}, beleértve $C\orie_{\!3}$-t és $K\orie_{\!3}$-t.)
\ujgyak \label{megold7-82}
(a) Igaz, definíció szerint.

(b)~Igaz: Ha minden csúcsnak $d$ szomszédja van, akkor minden 
$u\adj v$ élnek $d-1$ $u\adj w$ szomszédja van és $d-1$ $w\adj v$ szomszédja.

(c)~Igaz: $\{a_i,b_j\}$-nek $m+n-2$ szomszédja van, ha $0\le i<m$ és $0\le j<n$.

(d)~Hamis: $L(K_{1,1,2})$-nek 5~ csúcsa és 8~ éle van.

(e)~Igaz.

(f)~Igaz: A nem szomszédos élek csak: $\{0,1\}\nadj\{2,3\}$,
$\{0,2\}\nadj\{1,3\}$, $\{0,3\}\nadj\{1,2\}$.

(g)~Igaz,minden $n>0$.

(h)~Hamis, feltéve ha $G$-ben nincs \textit{izolált csúcs}. 
\ujgyak \label{megold7-83}
Ez a \textit{Petersen-gráf} {lásd Kowalewski cikkét \cite{Kowalewski1917}.}\angolnevindex{Kowalewski, Arnold (1873--1945)}
\ujgyak \label{megold7-84}
Igen: Legyen $\varphi(\{a_u,b_v\})=\{a_{(u+v)\mod 3},b_{(u-v)\mod 3}\}$, ahol $0\le u,v<3$. 
\ujgyak \label{megold7-85}
Legyenek a csúcsok fokszámai $\{d_1,\ldots,d_n\}$. Ekkor $G$-nek 
$\half(d_1+\cdots+d_n)$, $L(G)$-nek pedig $\half(d_1(d_1-1)+\cdots+d_n(d_n-1))$ éle van.
Így $G$-nek és $L(G)$-nek pontosan $n$~ éle van pontosan akkor, ha
$(d_1-2)^2+\cdots+(d_n-2)^2=0$. Ebbõl következõen az \ref{gyak7-58}. gyakorlat megadja a választ.

{Lásd Menon\angolnevindex{Menon, Vairelil Vishwanath} cikkét \cite{Menon1965}.}
\ujgyak \label{megold7-86}
Ha $\epsfbox{\figdir/v4a.1607}$, akkor $\epsfbox{\figdir/v4a.1606} = L(G)$.
\ujgyak \label{megold70-87}
(a) Igen, könnyedén. {Valójában, Brooks bebizonyította \cite{Brooks1941}, hogy 
\textit{minden} összefüggõ gráf, amelynek a maximális csúcs fokszáma $d>2$, $d$-színezhetõ, 
kivéve a $K_{d+1}$ teljes gráfot.}

(b) Nem. Alapvetõen csak egy módja van, hogy 3-színezzük a belsõ 
5-kör éleit a 2(e) ábrán; ez ellentmondásban van a belsõ 5-körrel.
{Petersen 1898-ban bebizonyította.} 
\ujgyak \label{megold7-88}
Egy kör nem használja a középsõ csúcsot, és van $(n-1)(n-2)$ kör, ami igen (nevezetesen van egy minden, a szélén lévõ 
különbözõ csúcsokból rendezett párban.) A $C_0$-t nem számítjuk bele.
\ujgyak \label{megold7-89}
Mindkét oldal egyenlõ rendre a következõ mátrixokkal:
$$\begin{pmatrix}
A & O & O \cr O & B & O \cr O & O & C
\end{pmatrix}, \quad
\begin{pmatrix}
A & J & J \cr J & B & J \cr J & J & C
\end{pmatrix}, \quad
\begin{pmatrix}
A & J & J \cr O & B & J \cr O & O & C
\end{pmatrix}, \quad
\begin{pmatrix}
A & O & O \cr J & B & O \cr J & J & C
\end{pmatrix}\koz .
$$
%$\eightpoint\let\quad=
%\enspace\pmatrix{A&O&O\cr O&B&O\cr O&O&C\cr}$,
%$\eightpoint\let\quad=\enspace\pmatrix{A&J&J\cr J&B&J\cr J&J&C\cr}$,
%$\eightpoint\let\quad=\enspace
%\pmatrix{A&J&J\cr O&B&J\cr O&O&C\cr}$,
%$\eightpoint\let\quad=\enspace\pmatrix{A&O&O\cr J&B&O\cr J&J&C\cr}$-vel. 
\ujgyak \label{megold7-90}
$K_4$ és $\overline{K_4}$; $K_{1,1,2}$ és $\overline{K_{1,1,2}}$;
$K_{2,2}=C_4$ és $\overline{K_{2,2}}$; $K_{1,3}$ és $\overline{K_{1,3}}$;
$K_1\dirsum K_{1,2}$ és a komplementere; 
minden $K_\alpha$ gráf generált (\ref{keplet7-47}) alapján. A $P_4=\overline{P_4}$ hiányzik.
(Egy generált gráf minden összefüggõ részgráfjának átmérõje $\le 2$;
$W_5$ generált, de $W_6$ nem.)
\ujgyak \label{megold7-91} IDE ÁBRÁK KELLENEK
(a) 1; 
(b) 2; 
(c) 3; 
(d) 1; 
(e) 3; 
(f) 4; 
(g) 5.

(Általánosan $K_2\oprod 
H=(K_2\cprod H)\cup(K_2\dprod\overline H)$,és $K_2\lprod H=H\adj H$. Így a $K_2\oprod H=K_2\cprod H$ és a 
$K_2\lprod H=K_2\sprod H$ egyenlõségek pontosan akkor teljesülnek, ha $H$ teljes gráf.)

\textit{Hivatkozások}:
A $G\cprod H$ és a $G\sprod H$ \textit{jelölés} szépen megfeleltethetõ az (a) és~(c) jelölésének, ahogy ezt 
Ne\v{s}et\v{r}il\angolnevindex{Ne\v{s}et\v{r}il, Jaroslav} \cite{Nesetril1981} javasolta.  
A $G\times H$ analóg jelölés szintén csábító a 
(b)-re; de ezt itt nem vezettük be, hiszen írók százai használták a $G\times H$ jelölést a $G\cprod H$-ra. 
\ujgyak \label{megold7-92} IDE ÁBRÁK KELLENEK
(a) ; \ (b) ; \ (c) ; \ (d) ; \ (e) . 
\ujgyak \label{megold7-93}
$K_m\sprod K_n=K_m\lprod K_n\cong K_{mn}$. 
\ujgyak \label{megold7-94}
Nem; ezek $K_{26}\cprod K_{26}\cprod K_{26}\cprod K_{26}\cprod K_{26}$ indukált részgráfjai. 
\ujgyak \label{megold7-95}
(a) $d_u+d_v$. (b)~$d_ud_v$. (c)~$d_ud_v+d_u+d_v$.
(d)~$d_u(n-d_v)+(m-d_u)d_v$. (e)~$d_un+d_v$.
\ujgyak \label{megold7-96}
(a) $A\cprod B=A\otimes I+I\otimes B$.
(b) $A\sprod B=A\cprod B+A\otimes B$.
(c)~$A\oprod B=A\otimes J+J\otimes B-2A\otimes B$.
(d)~$A\lprod B=A\otimes J+I\otimes B$.

{Az (a), (b), és (d) formulák tetszõleges \textit{irányított gráfra}\gyakindex{irányított gráf = directed graph} 
és \textit{multigráfra}\gyakindex{multigráf = multigraph} definiálják a \textit{gráf szorzást}\gyakindex{gráf szorzat = graph product}. 
A (c) \textit{egyszerû irányított gráfok}\gyakindex{egyszerû irányított gráf = simple directed graph} 
esetén is igaz; de elõfordulhatnak negatív elemek is, ha $A$ és $B$ tartalmaz $>1$ értékeket.}

\textit{Történelmi megjegyzés.} A mátrixok direkt szorzatát gyakran 
\textit{Kronecker szorzatnak}\angolnevindex{Kronecker, Leopold (1823--1891)}\index{Kronecker-szorzat = Kronecker product} 
nevezzük, mivel Hensel\angolnevindex{Hensel, Kurt Wilhelm Sebastian (1861--1941)} elmondása szerint \cite{Hensel1889} 
Kronecker elõadásain hallotta; Kronecker azonban soha nem publikált semmit róla. Az elsõ ismert megjelenése 
Zehfuss\angolnevindex{Zehfuss, Johann Georg} cikkében \cite{Zehfuss1858} történt, 
aki bebizonyította, hogy $\det(A\otimes B)=(\det A)^n(\det B)^m$, ha $m=m'$ és $n=n'$. Az alapvetõ 
$(A\otimes B)^T=A^T\otimes B^T$,
$(A\otimes B)(A'\otimes B')=AA'\otimes BB'$, 
és $(A\otimes B)\_=A\_\otimes B\_$ formulák A-nak következménye 
{lásd Hurwitz\angolnevindex{Hurwitz, Adolf (1859--1919)} cikkét \cite{Hurwitz1894}}.
\ujgyak \label{megold7-97}
A szomszédsági mátrixokkal elvégezhetõ mûveletek bizonyítják, hogy 
$(G\dirsum G')\cprod H=(G\cprod H)\dirsum(G'\cprod H)$;
$(G\dirsum G')\sprod H=(G\sprod H)\dirsum(G'\sprod H)$;
$(G\dirsum G')\lprod H=(G\lprod H)\dirsum(G'\lprod H)$. Mivel $G\cprod H\cong H\cprod G$,
$G\dprod H\cong H\dprod G$, és $G\sprod H\cong H\sprod G$, így vannak 
$G\cprod(H\dirsum H')\cong(G\cprod H)\dirsum(G\cprod H')$;
$G\dprod(H\dirsum H')\cong(G\dprod H)\dirsum(G\dprod H')$;
$G\sprod(H\dirsum H')\cong(G\sprod H)\dirsum(G\sprod H')$ jobb-disztributív szabályok is.

A lexikografikus szorzás kielégíti a 
$\overline{G\lprod H}=\overline G\lprod\overline H$ egyenlõséget; tehát 
$K_m\lprod H=H\adj\cdots\adj H\!$, így 
$K_m\lprod\overline K_n=K_{n,\ldots,n}$.

Továbbá, $G\lprod K_n=G\sprod K_n$; $K_m\dprod K_n=\overline{K_m\cprod K_n}=L(K_{m,n})$.
\ujgyak \label{megold7-98}
$kl$ komponens van (Az elõzõ gyakorlat \textit{disztributív szabályai}, valamint az alapján, hogy $G\cprod H$ és $G\sprod H$
összefüggõ, ha $G$ és $H$ összefüggõ). 
\ujgyak \label{megold7-99}
Minden út $(u,v)$-ból $(u',v')$-be a $G\cprod H$-ban legalább $d_G(u,u')$ \idez{$G$-lépést} és legalább $d_H(v,v')$ 
\idez{$H$-lépést} használ; és ez a minimum elérhetõ. Hasonló érvelés mutatja, hogy 
$d_{G\sprod H}((u,v),(u',v'))=\max(d_G(u,u'),d_H(v,v'))$.
%\par\begingroup \advance\parindent by 4pt 
% for them BIG answer numbers
%
%\begingroup \advance\parindent by 4pt % for them BIG exercise numbers
\ujgyak \label{megold7-100}
Ha $G$ és $H$ összefüggõ, és mindkettõnek van legalább 2 csúcsa, $G\dprod H$ pontosan akkor nem összefüggõ, 
ha $G$ és $H$ páros.
A \idez{ha} rész könnyû; megfordítva, ha van egy páratlan kör $G$-ben, akkor $(u,v)$-ból $(u',v')$-be eljuthatunk a következõ módon: 
Elõször menjünk $(u'',v')$-be, ahol $u''$ $G$-nek egy megfelelõ csúcsa.
Majd menjünk páros számú lépést $G$-ben $u''$-bõl $u'$-be, míg a $H$-ban a $v'$ és az egyik szomszédja között 
ingázunk {lásd Weichsel\angolnevindex{Weichsel, Paul Morris} cikkét \cite{Weichsel1962}.} 
\ujgyak \label{megold7-101}
Válasszuk ki az $u$ és $v$ csúcsokat maximális fokszámmal. 
Ekkor $d_u+d_v=d_ud_v$ a ~\ref{gyak7-95}. gyakorlat alapján; tehát vagy $G=H=K_1$, vagy 
$d_u=d_v=2$. Utóbbi esetben, $G=P_m$ vagy $C_m$, és $H=P_n$ vagy $C_n$. $G\cprod H$ azonban összefüggõ, 
tehát $G$ vagy $H$ mindenképpen páratlan, mondjuk $G$. Ekkor $G\cprod H$ páratlan, tehát $H$-nak mindenképpen 
páratlannak kell lennie; így $G=C_m$ és $H=C_n$,
miközben $m$ és $n$ is páratlan. 
$C_m \cprod C_n$-ben a legrövidebb kör hossza $\min(m,n)$; $C_m\dprod C_n$-ben a hossza $\max(m,n)$; így $m=n$.

Megfordítva, ha $n \ge 3$ páratlan, akkor $C_n \cprod C_n\cong C_n \dprod C_n$, azon izomorfizmus alatt, 
amelynek alakja: $(u,v)\mapsto((u+v)\mod n,(u-v)\mod n)$, ahol $0\le u,v<n$ 
{lásd Miller\angolnevindex{Miller, Donald John} cikkét \cite{Miller1968}.} 
\ujgyak \label{megold7-102}
$P_m\sprod P_n$. (Ez csak akkor {\it síkgráf}, ha $\min(m,n)\le2$ vagy $m=n=3$.) 
\ujgyak \label{megold7-103} 
\qquad\def\vedgec{\vrule height 6.5pt depth 2.1pt}%
\def\bytej#1{\lower.3pt\hbox to1em{\eightrm\hfill#1\hfill\kern.4pt}\kern-.4pt
    \vrule}%
\def\Hedge#1{\vbox{\dimen0=.55556em \dimen0=#1\dimen0
     \advance\dimen0 .4 pt \hrule width \dimen0}}%
\def\lab#1{\lower.3pt\llap{\eightrm#1\enspace}}%
\raise7pt\vtop{\baselineskip0pt\lineskip0pt\halign{\lft{#}\cr
 \hedgez\cr % this is the arcane macro of 1981; z=5, l=4, g=3, k=2, h=1!
\lab1\vedgec\bytej2\bytej3\bytej4\bytej5\bytej7\cr
 \hedgez\cr
\lab2\vedgec\bytej1\bytej3\bytej4\bytej6\bytej8\cr
 \hedgez\cr
\lab3\vedgec\bytej1\bytej2\bytej5\bytej6\bytej8\cr
 \hedgez\cr
\lab4\vedgec\bytej1\bytej2\bytej5\bytej6\cr
 \hedgel\cr
\lab5\vedgec\bytej3\bytej4\bytej1\bytej7\cr
 \hedgel\cr
\lab6\vedgec\bytej2\bytej3\bytej4\cr
 \hedgeg\cr
\lab7\vedgec\bytej5\bytej1\cr
 \hedgek\cr
\lab8\vedgec\bytej2\bytej3\cr
 \hedgek\cr}}
\qquad
\raise7pt\vtop{\baselineskip0pt\lineskip0pt\halign{\lft{#}\cr
 \hedgei\cr
\lab1\vedgec\bytej2\bytej3\bytej4\bytej5\bytej6\bytej7\bytej8\bytej9\cr
 \hedgei\cr
\lab2\vedgec\bytej1\bytej3\bytej4\bytej6\bytej8\bytej9\cr
 \hedgef\cr
\lab3\vedgec\bytej1\bytej2\bytej5\bytej6\bytej8\bytej9\cr
 \hedgef\cr
\lab4\vedgec\bytej1\bytej2\bytej5\bytej7\cr
 \hedgel\cr
\lab5\vedgec\bytej3\bytej4\bytej1\bytej7\cr
 \hedgel\cr
\lab6\vedgec\bytej2\bytej3\bytej1\bytej7\cr
 \hedgel\cr
\lab7\vedgec\bytej4\bytej5\bytej6\bytej1\cr
 \hedgel\cr
\lab8\vedgec\bytej2\bytej3\bytej1\bytej9\cr
 \hedgel\cr
\lab9\vedgec\bytej8\bytej2\bytej3\bytej1\cr
 \hedgel\cr
\noalign{\breathe}}}
\ujgyak \label{megold7-104}
Az éleket kissé körülményes sorrendben kell létrehozni, hogy fenntartsuk a tabló alakját. 
Az $r$ és $i$ változók jelölik a kezdõ - és utolsó sorát a ~$t$ oszlopban. Például, a 
\ref{gyak7-103}. gyakorlat második része a következõképpen kezdõdik: 
$i\gets 1$, $t\gets 8$, $r\gets 1$; majd $9\adj 1$, $i\gets 2$, $t\gets 6$,
$r\gets 3$; utána $9\adj 3$, $9\adj 2$, $i\gets 4$, $t\gets 4$, $r\gets 8$; végül $9\adj 8$. 
\ujgyak \label{megold7-105}
Vegyük észre, hogy $d_k\ge k$ pontosan akkor, ha $c_k\ge k$.

Ha $d_k\ge k$, akkor $$c_1+\cdots+c_k\;=\;k^2+\min(k,d_{k+1})+\min(k,d_{k+2})+\cdots+\min(k,d_n);$$
ennek következtében a $d_1+\cdots+d_k\le c_1+\cdots+c_k-k$ feltétel ekvivalens a következõvel: 
$$d_1+\cdots+d_k\le f(k),\quad\hbox{ahol} f(k)=k(k{-}1)+
\min(k,d_{k+1})+\cdots+\min(k,d_n)\hfill(*)$$

Ha $k\ge s$, akkor $f(k+1)-f(k)=2k-d_{k+1}\ge d_{k+1}$; így $(*)$ fennáll $1\le k\le n$ esetén pontosan akkor, 
ha fennáll $1\le k\le s$-re.

A $(*)$ kifejezést Erd\H{o}s\angolnevindex{Erdõs Pál (= Paul, 1913--1996)} és Gallai\angolnevindex{Gallai Tibor (1912--1992)}
\cite{Erdos1960} fedezték fel. Használata nyilvánvalóan szükséges, ha az $\{1,\ldots,k\}$ és $\{k{+}1,\ldots,n\}$ 
közötti éleket tekintjük.

 Legyen $a_k=d_1+\cdots+d_k-c_1-\cdots-c_k+k$, és tegyük fel, hogy 
$a_k>0$ valamely ~$k\le s$-re miután a H3 és H4 lépés életbe lépett.
Legyen $A_j$, $C_j$, $D_j$, $N$, és $S$ rendre az $a_j$, $c_j$, $d_j$, $n$, 
és $s$-nek megfelelõ számok a H3 és H4 lépések \textit{elõtt}; így
$N=n+1$, $D_j=d_j+(0$~or~1), stb. Be akarjuk bizonyítani, hogy $A_K>0$
 valamely $K\le S$ esetén. A H3 és H4 eltávolította a legalsó $q$ cellát a ~$t$ oszlopban, 
valamely $t\ge S$-re, az $1$-tõl ~$p$. sor legjobboldali celláival együtt, ahol 
$q+p=D_N$. Így $A_j=a_j$, ha $1\le j\le p$; továbbá $A_j=a_j$, ha $j\ge C_t$.
Legyen $k$ minimális $a_k>0$-val, és legyen $d_k=d$; vegyük észre, hogy $c_k\le d$. Ha $d>t$, akkor $k\le p$, 
tehát $A_k=a_k>0$. Ennélfogva feltehetjük, hogy 
$d=t-(0$ or~1), és $D_k=t$. Ha $k<j\le C_t$, 
akkor $d_j\ge D_j-1=t-1\ge d-1\ge c_k-1\ge c_j-1$.Ennek következtében $A_K=a_K\ge a_k$, ha $K=C_t$; feltehetjük, 
hogy $C_t>S$. Most $D_S=D_{S+1}=t$, tehát $S=t$. $k=t$ szintén fennáll; egyébként $c_k\ge S+1>t\ge d$.

Így $s=S$ és $d=t=c_t$. További vizsgálatok megmutatják, hogy az egyetlen 
lehetõség $A_t\le 0$-ra $D_j=t + [j\ge t]$, ha $1\le j\le N=t+2$.
 A H algoritmus tényleg kicseréli ezt a \idez{jó} sort 
egy \idez{rosszra}; de $D_1+\cdots+D_N=t^2+3t-1$ páratlan. 
\ujgyak \label{megold7-106}
Hamis az olyan triviális esetekben, mint $d\le 1$ és $n\ge d+2$. Egyébként igaz: Valójában, a H4-es lépés során 
generált elsõ $n-1$ él körmentes, tehát feszítõfát alkot. 
\ujgyak \label{megold70-107}
A \ref{gyak7-78}. gyakorlat $\varphi$ permutációja megfeleltet egy $d$ fokú csúcsot egy $n-1-d$ fokú csúcsnak. 
$\varphi^2$ pedig egy \textit{automorfizmus}, ami két egyenlõ fokú csúcsot párosít össze, kivéve egy lehetséges 
$(n-1)/2$ fokú fixpontot. (Megfordítva, a H algoritmus egy kissé bonyolult kiterjesztése egy komplementerével megegyezõ 
gráfot konstruál minden grafikus sorozatból, ami kielégíti a feltételeket, feltéve, hogy 
$d_{(n-1)/2}=(n-1)/2$ ha $n$ páratlan. Lásd Clapham\angolnevindex{Clapham, Christopher Robert Jasper} és 
Kleitman\angolnevindex{Kleitman, Daniel J (Isaiah Solomon)} cikkét \cite{Clapham1976}.
\ujgyak \label{megold7-108}
Feltehetõ, hogy $d^+_1\ge\cdots\ge d^+_n$; a $d_k^-$ befokoknak nem szükséges egy megadott sorrendben állniuk. 
Alkalmazzuk a H algoritmust a $d_1\ldots d_ n=d^+_1\ldots d^+_n$ sorozatra, de változtassuk meg a következõket: 
A H2-es lépés a következõ lesz: `\idez{[Kész?] Sikeresen befejezõdik, ha $d_1=n=0$; sikertelenül fejezõdik be, ha $d_1>n$.'} 
Miután beállítottuk az $i$, $t$, és~$r$ értékét a H3-as lépésben, sikertelenül fejezõdjön be, 
ha $d_n^->c_1$; egyébként hajtsuk végre a H4-es lépést, ha $1\le j\le d_n^-$, 
és legyen $n\gets n-1$, majd térjünk vissza H2-höz.
H5-ben hagyjuk el a \idez{$c_j\gets c_j-1$}-t, és készítsük el a $k\rightarrow n$ irányított élt a $k\adj n$ él helyett. 
Az M lemma és H következmény igazolja megközelítésünket.

(A 7.2.1.4--57. gyakorlat bebizonyítja, hogy ilyen irányított gráf pontosan akkor létezik, ha 
$d_1^-+\cdots+d_n^-=d_1^++\cdots+d_n^+$ és $d_1^-\ldots d_n^-=\{d_1',\ldots,d_n'\}$, 
ahol $d_1'\ge\cdots\ge d_n'$ és $d_1'\ldots d_n'$ {\it majorálva} van a 
$c_1\ldots c_ n=(d_1^+\ldots d_n^+)^T$ {\it konjugált partícióval}.
Nehezebb az az eset, amikor a $v\dadj v$ hurok nem megengedett; lásd 
Fulkerson\angolnevindex{Fulkerson, Delbert Ray (1924--1976)} cikkét \cite{Fulkerson1960}. 
\ujgyak \label{megold7-109}
Ugyanaz, mint a \ref{gyak7-108}. gyakorlat a következõ kiegészítésekkel: $d_k^+=d_k[k\le m]$ és $d_k^-=d_k[k>m]$.
\ujgyak \label{megold7-110}
$p$ csúcs van, amely $d=d_1$ fokú, és $q$ csúcs van, amely $d-1$ fokú, ahol $p+q=n$. 
 1.eset, $d=2k+1$. 
Legyen $u\adj v$, ha $(u-v)\mod n\in
\{2,3,\ldots,k+1,\allowbreak n-k-1,\ldots,n-3,n-2\}$; továbbá vegyük fel a $p/2$ darab
$1\adj2$, $3\adj4$, \dots,~$(p{-}1)\adj p$ élt.

2. eset,  $d=2k$.
Legyen $u\adj v$, ha $(u-v)\mod n\in \{2,3,\ldots,k,\allowbreak n-k,\ldots,\allowbreak n-3,n-2\}$;
továbbá vegyük fel az $1\adj 2$, \dots, $(q{-}1)\adj q$ éleket, valamint a 
$(q=0{?}\ n{:}\ q)\adj(q{+}1)\adj\cdots\adj(n{-}1)\adj n$ kört vagy utat. 
{Wang\angolnevindex{Wang Da@\string\WangDa} és Kleitman\angolnevindex{Kleitman, Daniel J (Isaiah Solomon)} 
 bebizonyították \cite{Wang1973}, hogy az ilyen gráfok erõsen összefüggõek.}
\vspace{-2mm}
\ujgyak \label{megold7-111}
Tegyük fel, hogy $N=n+n'$, és $V'=\{n+1,\ldots,N\}$. Konstruálni akarunk 
$e_k=d-d_k$ éleket $k$ és~$V'\!$ között, és további éleket~$V'\!$-n belül
úgy, hogy ~$V'$ minden csúcsának ~$d$ legyen a foka. Legyen $s=e_1+\cdots+e_n$.
Ez a lépés pontosan akkor végezhetõ el, ha (i)~$n'\ge\max(e_1,\ldots,e_n)$;
(ii)~$n'd\ge s$; 
(iii)~$n'd\le s+n'(n'-1)$; és (iv)~$(n+n')d$ páros.

Ilyen élek léteznek, már ha $n'$ kielégíti (i)--(iv)-et: Elõször, (i) miatt,
$s$ megfelelõ él $V$ és~$V'$ között létrehozható úgy, hogy ciklikusan választjuk végpontnak 
$(n{+}1,n{+}2,\ldots,n{+}n',\allowbreak
n{+}1,\ldots{})$-et. Ez a folyamat hozzárendeli vagy az $\lfloor s/n'\rfloor$ vagy az $\lceil s/n'\rceil$ éleket 
~$V'$ minden csúcsához; $\lceil s/n'\rceil\le d$ teljesül ~(ii) miatt, és 
$d-\lfloor s/n'\rfloor\le n'-1$ ~(iii) miatt. Ennél fogva a további élek, amelyek szükségesek~$V'$-n belül, 
megkonstruálhatók a 110-es feladathoz hasonlóan (iv) segítségével.

Az $n'=n$ választás mindig jó. Megfordítva, ha
$G=K_n(V)\setminus\{1\adj2\}$, az (iii) feltétel megköveteli, hogy $n'\ge n$, ha $n \ge 4$. 
{lásd Erdõs\angolnevindex{Erdõs Pál (= Paul, 1913--1996)} és Kelly \angolnevindex{Kelly, Paul Joseph} \cite{Erdos1963}}.
\ujgyak \label{megold7-112}
Az egyértelmûen legjobb háromszög a \textit{miles} adatok között 
$$\texttt{Saint Louis, MO} \hfil \buildrel 748 \over \adj \hfil
\texttt{Toronto, ON} \hfil \buildrel 746 \over \adj \hfil
\texttt{Winston-Salem, NC} \hfil \buildrel 748 \over \adj \hfil
\texttt{Saint Louis, MO}.$$
\ujgyak \label{megold7-113}
Murphy törvénye\index{Murphy törvénye = Murphy's law} szerint, 
$n$ sora és $m$ oszlopa van; tehát $n\times m$-es, nem pedig $m\times n$-es. 
\ujgyak \label{megold7-114}
Egy \textit{hurok} egy adott multigráfban egy $\{a,a\}$ él, amelyben ismétlõdõ csúcsok vannak,
és egy multigráf 2-egyenletes hipergráf. Így egy általános hipergráfnak az illeszkedési mátrixában meg vannak engedve 
$1$-nél nagyobb értékek, ha egy él egy megadott csúcsot többször is tartalmaz. 
Egy vaskalapos ember valószínûleg ezt \idez{\textit{multihipergráfnak}} hívná abból a megfontolásból, hogy 
a (\ref{keplet7-26})-nak megfelelõ illeszkedési mátrix és páros gráf a következõ: 
$$\Bigl(\,\vcenter{\eightrm\baselineskip8pt
        \hbox{210000}\hbox{011100}\hbox{001122}}\,\Bigr)@;\qquad\qquad
\vcenter{\epsfbox{\figdir/v4a.1516}}\,.$$
\noindent \ujgyak \label{megold7-115}
A $B^T\!B$ $e$ sorban és $f$ oszlopban lévõ eleme $\sum_v b_{ve}b_{vf}$; tehát $B^T\!B$ megegyezik $2I$ plusz 
az $L(G)$ szomszédsági mátrixával. 
Hasonlóan, $BB^T$ a $D$ plusz $G$ szomszédsági mátrixa, 
ahol $D$ a diagonális mátrix, melyben $d_{vv}$ a $v$ \textit{foka}.
(Lásd a 2.3.4.2--18., 19. és 20. gyakorlatokat.)
\ujgyak \label{megold7-116}
$\overline{K^{(r)}_{m,n}}=K^{(r)}_m\dirsum K^{(r)}_n$, (\ref{keplet7-38})-at általánosítva minden $r\ge 1$-re.
\ujgyak \label{megold7-117}
$m=4$ és $V=\{0,1,2\}$ esetén az egyszeres élek nemizomorf multihalmazai a következõk lehetnek:  

$\{\{0\},\{0\},\{0\},\{0\}\}$,
$\{\{0\},\{0\},\{0\},\{1\}\}$,
$\{\{0\},\{0\},\{1\},\{1\}\}$ és 
$\{\{0\},\{0\},\{1\},\{2\}\}\koz.$

A válasz általában az $m$ legfeljebb $n$ részre való \textit{felosztásának} a száma, nevezetesen 
$\begin{vmatrix} m + n \\ n\end{vmatrix}$
%$m+n\parts n$ 
a 7.2.1.4. alpont jelöléseit használva. (Természetesen kevés ok van arra, hogy a partíciókra úgy tekintsünk, mint 
1-egyenletes hipergráfokra, kivéve, ha speciális feladatokat akarunk megoldani.) 
\vspace{-4mm}
\ujgyak \label{megold70-118}
Legyen $d$ a csúcs fokszámok összege. 
A megfelelõ páros gráf egy erdõ $m+n$ csúccsal, $d$ éllel és $p$ komponenssel. 
Így $d=m+n-p$, a 2.3.4.1.A tétel szerint. 
\ujgyak \label{megold7-119}
Van egy további él, ami tartalmazza mind a $7$ csúcsot.
\ujgyak \label{megold7-120}
Azt mondhatjuk, hogy az irányított (hiper) élek csúcsok tetszõleges sorozata, vagy különbözõ csúcsok sorozata. 
A legtöbb szerzõ az \textit{irányított hiperélt} azonban $A\rightarrow v$-nek definiálja, ahol az $A$ csúcsok rendezetlen halmaza.

A legjobb definíciót úgy találhatjuk meg, hogy megnézzük, melyiknek van a legfontosabb gyakorlati alkalmazása.
\ujgyak \label{megold7-121}
$\chi(H)=\vert F\vert-\alpha(I(H)^T)$ a $V$ minimális lefedésének a mérete az ~$F$ halmazokkal. 
\ujgyak \label{megold7-122}
(a) Igazolható, hogy csak $7$ darab 3-elemû lefedés van, nevezetesen az él csúcsai; 
tehát $7$ darab 4-elemû független halmaz létezik, nevezetesen az élek komplementerei. Nem tudjuk 2-színezni 
a hipergráfot, mivel egy színt 4~alkalommal kellene használni, és a maradék 3 szín egy él lenne. 
(Az (\ref{keplet7-56}) hipergráf alapvetõen a $7$ pontból, és $7$ egyenesbõl álló 
\textit{projektív sík}.)

(b) Mivel duálist használunk, nevezzük a Petersen-gráf csúcsait és éleit \idez{pontoknak} és\linebreak
\noindent \idez{egyeneseknek}; így a duális csúcsai és élei rendre az egyenesek és a pontok. Színezzük pirosra azt az 
5 egyenest, melyek egy külsõ pontot belsõ ponttal kötnek össze.

A maradék $10$ egyenes független (nem tartalmazzák mind a három, valamely pontot érintõ egyenest); tehát zöldre színezhetõk.

Bármely 11 egyenes halmaza nem lehet független, mivel nincs olyan 4 egyenes, amely egyszerre tudná érinteni mind a $10$ pontot. 
(Így a Petersen duálisa a \textit{páros hipergráf}, annak ellenére, hogy van benne 5 hosszúságú kör.) 
\ujgyak \label{megold7-123}
Megfeleltethetõek az $n\times n$ \textit{latin négyzetnek}, amelynek elemei csúcsszínek. 
\ujgyak \label{megold7-124}
$4$ szín bõven elegendõ. Ha \textit{3-színezhetõ} lenne, akkor minden színre jutna 4 csúcs, 
mivel nincs olyan 5 csúcs, ami független lenne.
Így $2$ ellentétes saroknak ugyanolyan színûnek kell lenni, vagyis ellentmondásra jutunk. 
\ujgyak \label{megold7-125}
A \textit{Chvátal-gráf}\angolnevindex{Chvátal, Václav} a legkisebb gráf $g=4$-gyel.
\textit{Brinkmann}\angolnevindex{Brinkman, Gunnar} megtalálta a legkisebbet $g=5$-tel: 
21 csúcsa van: 
$a_j$, $b_j$, $c_j$, ha $0\le j<7$, élei $a_j\adj a_{j+2}$,
$a_j\adj b_j$, $a_j\adj b_{j+1}$, $b_j\adj c_j$, 
$b_j\adj c_{j+2}$,
$c_j\adj c_{j+3}$ és az alsó indexei mod 7.
Meringer megmutatta, hogy legalább 35 csúcsnak kell lennie, ha $g>5$. Grünbaum\angolnevindex{Grünbaum, Branko} azt sejtette, 
hogy $g$ tetszõlegesen nagy lehet; de további konstrukciók nem ismertek {lásd \cite{Grunbaum1970,Grunbaum1997}}. 
\ujgyak \label{megold7-126}
Amikor $m$ és $n$ páros, mind a $C_m$ és $C_n$ páros, és könnyû a {\it 4-színezés}. 
Egyébként egy 4-színezés lehetetlen. Ha $m=n=3$, egy 9-színezés megfelelõ a \ref{gyak7-93}. gyakorlat alapján. 
Ha $m=3$ és $n=4$ vagy 5, akkor legfeljebb két csúcs független; könnyû találni egy megfelelõ 6- vagy 8-színezést.

Egyébként megkapunk egy 5-színezést úgy, hogy a $(j,k)$ csúcsot 
$(a_j+2b_k)\mod 5$-tel színezzük, ahol az $\langle a_j\rangle$
és $\langle b_k\rangle$ periodikus sorozatok léteznek rendre $m$ és ~$n$ periódussal 
úgy, hogy $a_j-a_{j+1}\equiv\pm1$ és $b_k-b_{k+1}\equiv\pm1$ minden $j$-re és~$k$-ra 
{lásd K. Vesztergombi cikkét\angolnevindex{Vesztergombi Katalin} \cite{Vesztergombi1978}}.
\ujgyak \label{megold7-127}
(a) Az eredmény $n=1$ esetén igaz. Különben legyen $H=G\setminus v$,
ahol $v$ tetszõleges csúcs. 
Ekkor $\overline H=\overline G\setminus v$, és $\chi(H)+\chi(\overline H)\le n$ indukció alapján. 
Világos, hogy $\chi(G)\le\chi(H)+1$ és $\chi(\overline G)\le\chi(\overline H)+1$; tehát nincs probléma egészen addig, 
amíg mindhárom esetben nem teljesül az egyenlõség. De ez nem történhet meg; ebbõl következik, hogy 
$\chi(H)\le d$ és $\chi(\overline H)\le n-1-d$, ahol $d$ a ~$v$ foka a ~$G$-ben
{lásd Nordhaus\angolnevindex{Nordhaus, Edward Alfred} és Gaddum\angolnevindex{Gaddum, Jerry William} cikkét \cite{Nordhaus1956}}.

Ahhoz, hogy egyenlõséget kapjunk, legyen $G=K_a\dirsum\overline{K_b}$, 
ahol $ab>0$ és $a+b=n$. Ekkor $\overline G=\overline{K_a}\join K_b$, $\chi(G)=a$, és $\chi(\overline G)=b+1$. 
{Minden gráf, amelyben fennáll az egyenlõség, megtalálható Finck\angolnevindex{Finck, Hans-Joachim} cikkében \cite{Finck1966}}.

(b) A $G$ egy $k$-színezésében van legalább $\lceil n/k\rceil$ színezett csúcs; 
azok a csúcsok, amelyek a~$\overline G$ egy klikkjében vannak. Így
$\chi(G)\chi(\overline G)\ge\chi(G)\lceil n/\chi(G)\rceil\ge n$.

Egyenlõség áll fenn, ha $G=K_n$.\par
(Az (a) és (b)-bõl következtetjük, hogy $\chi(G)+\chi(\overline G) \ge 2\sqrt n$ és
$\chi(G)\chi(\overline G)\le{1\over 4}(n+1)^2$.) 
\ujgyak \label{megold7-128}
$\chi(G\cprod H)=\max(\chi(G),\chi(H))$. Ennyi színre mindenképpen szükségünk van. 
Ha továbbá az $a(u)$ és $b(v)$ függvények kiszínezik $G$-t és $H$-t a $\{0,1,\ldots,k-1\}$ színekkel, 
ki tudjuk színezni $G\cprod H$-t $c(u,v)=(a(u)+b(v))\mod k$-val. 
\ujgyak \label{megold7-129}
Egy teljes sor vagy oszlop (16 eset);
egy teljes, 4 vagy több hosszú átló (18 eset);
egy 5-cellás minta $\{(x,y),(x{-}a,y{-}a),(x{-}a,y{+}a),(x{+}a,y{-}a),(x{+}a,y{+}a)\}$, ha $a\in\{1,2,3\}$ ($36+16+4$ eset);
egy 5-cellás minta $\{(x,y),(x{-}a,y),(x{+}a,y),(x,y{-}a),\allowbreak(x,y{+}a)\}$,
ha $a\in\{1,2,3\}$ ($36+16+4$ eset);
egy minta, amelyben az 5 cellából 4 van, ha az ötödik kívül esik a táblán ($24+32+24$ eset);
vagy egy 4-cellás $\{(x,y), (x{+}a,y), (x,y{+}a), (x{+}a,y{+}a)\}$ minta,
ha $a\in\{1,3,5,7\}$ ($49+25+9+1$ eset).

Összesen maximum 310 klikk, rendre $(168,116,4,4,18)$ és $(4,5,6,7,8)$ méretekkel. 
\ujgyak \label{megold7-130}
Ha a $G$ gráfnak $p$ maximális klikkje van, a ~$H$ gráfnak pedig $q$, akkor az {\it egyesített} $G\join H$-nak $pq$, 
mivel a $G\join H$ klikkjei egyszerûen a $G$ és~$H$ klikkjeinek az uniója. Továbbá, 
a $\,\overline{\!K_n}$
üres gráfnak $n$ maximális klikkje van (nevezetesen az egyszeres halmazai).

Így az $\{n_1,\ldots,n_k\}$ partícióméretekkel rendelkezõ teljes $k$-partíciós gráfnak, ami egyébként az adott méretû 
üres gráfok egyesítésével keletkezik, $n_1\ldots n_k$ maximális klikkje van.
\ujgyak \label{megold7-131}
Feltehetõ, hogy $n>1$. Egy teljes $k$-partíciós gráfban, akkor maximálisak az $n_1\ldots n_k$ számok, ha mindegyik 
résznek a mérete 3, kivéve talán egy vagy két részt, amelyek mérete 2.
(Lásd a 7.2.1.4--68(a) gyakorlatot.) Tehát be kell bizonyítani, hogy $N(n)$ ennél nem lehet nagyobb \textit{bármely} 
gráfban.

 Legyen $m(v)$ azon klikkeknek a maximális száma, amelyek tartalmazzák a ~$v$ csúcsot. Ha $u\nadj v$ és $m(u)\le m(v)$, 
 akkor készítsük el a ~$G'$ gráfot hasonlóan a~$G$-hez, kivéve, hogy $u$ most szomszédos ~$v$ minden szomszédjával, 
kivéve a korábbi szomszédjait. Minden ~$U$ maximális klikk valamelyik gráfban a következõ $3$ osztály egyikébe tartozik:
\begin{itemize}
\item{i)} $u\in U$; 
Ezek közül $m(u)$ a $G$-ben van és $m(v)$ a másikból $G'$-ben.
\item{ii)} $v\in U$; Ezek közül $m(v)$ a $G$-ben és a $G'$-ben is van.
\item{iii)} $u\notin U$ és $v\notin U$; az ilyen maximális klikkek a $G$-ben egyben maximálisak a $G'$-ben is.
\end{itemize}

\noindent Ebbõl következõen $G'$-nek legalább annyi maximális klikkje van, mint $G$-nek. 
Így, a folyamat megismétlésével megkaphatunk egy $k$-partíciós gráfot.

{Az érvelés Erd\H{o}s Páltól\angolnevindex{Erdõs Pál (= Paul, 1913--1996)} származik, lásd Moon\angolnevindex{Moon, John Wesley}  
és Moser cikkét \cite{Moon1965}}.
\ujgyak \label{megold7-132}
A $G$-ben és a $H$-ban lévõ klikkek erõs szorzata klikk 
$G\sprod H$-ban a 93-as gyakorlat szerint; így $\omega(G\sprod H)\ge\omega(G)\omega(H)=
\chi(G)\chi(H)$. Másrészt, 
a $G$ $a(u)$ és $H$ $b(v)$ színezése elvezet a $G\sprod H$ $c(u,v)=(a(u),b(v))$ színezéséhez;
tehát $\chi(G\sprod H)\le\chi(G)\chi(H)$. 
Továbbá, $\omega(G\sprod H) \le\chi(G\sprod H)$. 
\vspace{-2mm}
\ujgyak \label{megold7-133}
(a) 24; (b)~60; (c)~3; (d)~6; (e)~6; (f)~4; (g)~5; (h)~4;
(i)~$K_2\sprod C_{12}$; 
(j)~18; (k)~12.
(l)~Igen, 5 fokkal.
(m)~Nem. {Le lehet rajzolni 12 \textit{vonal} segítségével?}
(n) Igen; Valójában, 4-összefüggõ (lásd 7.4.1). 
(o)~Igen; \textit{minden} gráfot irányítottnak tekintünk, 2 irányított éllel egy élnél.
(p)~Természetesen nem.
(q)~Igen, könnyedén.

{A zenei gráf egyszerû modulációt reprezentál a kulcs hangjegyek között.
Megtekinthetõ Wilson\angolnevindex{Wilson, Robin James} és Watkins\angolnevindex{Watkins, John Jaeger} 
könyvében \cite[73.oldal]{Wilson1990}}. 
\ujgyak \label{megold7-134}
Ha elforgatjuk és/vagy kicseréljük a belsõ és külsõ csúcsokat, 
találhatunk egy automorfizmust, amely bármely csúcsot $C\null$-ba visz. Ha $C$ fix, akkor 
felcserélhetjük a külsõ és belsõ csúcsát a fennmaradó 11 pár bármely részhalmazában, 
és/vagy megejthetünk egy bal-jobb tükrözést.

Ebbõl következõen $24\times 2^{11}\times 2=98304$ automorfizmus van összesen. 
\ujgyak \label{megold7-135}
Legyen $\omega=e^{2\pi i/6}$, és definiáljuk a $Q=(q_{ij})$,
$S=(s_{ij})$ mátrixokat, 
ahol $q_{ij}=[j=(i+1)\mod 12]$ és $s_{ij}=\omega^{ij}$,
$0\le i,j<12$ esetén. A \ref{gyak7-96}(b) gyakorlat szerint a $K_2\sprod C_{12}$ zenei gráf szomszédsági mátrixa  
$A={1\,1\choose1\,1}\otimes(I+Q+Q^-)-I$. 
Legyen $T$ a ${1\,\phantom-1\choose1\,-1}\otimes S$ mátrix; ekkor $T^-\!AT$ egy ~$D$ diagonális mátrix, amelynek elsõ 12 
eleme $1+4\cos{j\pi\over 6}$, ha $0\le j<12$, és a maradék $12$ eleme $-1$.
Ezért $A^{2m}=TD^mT^-$, továbbá a $2m$-lépéses utak száma $C$-bõl $\rm(C,G,D,A,E,B,F^\sharp)$-be rendre
$$
\begin{array}{ccccccc}
{\rm C}_m&=&\frac{1}{24}(25^m   & + 2(13+4\sqrt 3)^m      & +3^{2m+1} & +2(13-4\sqrt 3)^m & +16)\koz;\\
{\rm G}_m&=&\frac{1}{24}(25^m   & +\sqrt 3(13+4\sqrt 3)^m &-\sqrt 3(13-4\sqrt 3)^m        & -1)\koz;\\
{\rm D}_m&=&\frac{1}{24}(25^m   & +(13+4\sqrt 3)^m         & + (13-4\sqrt 3)^m-3)          & \koz;\\
{\rm A}_m&=&\frac{1}{24}(25^m   & -3^{2m+1}+2)\koz;\\
{\rm E}_m&=&\frac{1}{24}(25^m   & - (13+4\sqrt 3)^m        & - (13-4\sqrt 3)^m+1)\koz;\\
{\rm B}_m&=&\frac{1}{24}(25^m   & -\sqrt 3(13+4\sqrt3)^m   & +\sqrt3(13-4\sqrt 3)^m-1)\koz;\\
{\rm F}^\sharp_m&=&\frac{1}{24}(25^m & -2(13+4\sqrt 3)^m & +3^{2m+1} & -2(13-4\sqrt 3)^m)\koz;\cr
\end{array}
$$
%{\advance\thickmuskip-3mu
Teljesül még, hogy ${\rm a}_m = {\rm C}_m -1$,
${\rm d}_m = {\rm F}_m = {\rm e}_m = {\rm G}_m$ stb. Speciálisan, 

$\rm(C_6,G_6,D_6,A_6,E_6,B_6,F^\sharp_6) =$ 
(15462617, 14689116, 12784356, 10106096, 7560696, 5655936, 5015296),
tehát a keresett valószínûség $15462617/5^{12}\approx 6.33$. Ha $m \to \infty$, akkor a 
valószínûségek mindegyike ${1\over 24}+O(0.8^m)$.
\ujgyak \label{megold7-136}
Nem. Csak két 10-ed rendû Cayley-gráf harmadfokú, nevezetesen $K_2\cprod C_5$ (amelynek csúcsai
$\{e,\alpha,\alpha^2,\alpha^3,\alpha^4,
\beta,\beta\alpha,\beta\alpha^2,\beta\alpha^3,\beta\alpha^4\}$ alakba írhatók, ahol
$\alpha^5=\beta^2=(\alpha\beta)^2=e$$\bigr)$ és a $\{0,1,\ldots,9\}$ csúcsokkal rendelkezõ gráf és 
irányított élei 
$v \to (v{\pm}1)\mod 10$, $v \to{(v{+}5)\mod 10}$.
{Lásd Holton\angolnevindex{Holton, Derek Alan} és Sheehan\angolnevindex{Sheehan, John} könyvét \cite[9.10. gyakorlat]{Holton1993}.
Mellékesen, a \textit{raman}$(p,q,t,0)$ SGB gráfok Cayley-gráfok.}\gyakindex{Cayley-gráf = Cayley graph}

\ujgyak \label{megold70-137}
Legyen $[x,y]$ az $(x,y)$ címkéjének a jelölése; Azt szeretnénk, hogy
$[x,y]=[x+a,y+b]=[x+c,y+d]$ legyen minden $x$-re és~$y$-ra. 
Ha $A$ az $\begin{pmatrix}a & b \cr c & d\end{pmatrix}$
%\smash{$\\abcd$} 
mátrix, akkor az $A$ legalsó sorát $t$-szer hozzáadva a felsõ sorhoz 
megváltoztatja az $A$ mátrixot az $A'=\begin{pmatrix}1 & t \cr 0 & 1\end{pmatrix} 
A= \begin{pmatrix}a' & b' \cr c' & d'\end{pmatrix}$ mátrixra,
ahol $a'=a+tc$, $b'=b+td$, $c'=c$, $d'=d$. Az új
$[x,y]=[x+a\prime,y+b\prime]=[x+c^\prime,y+d^\prime]$ feltételek ekvivalensek a régivel; és
$\mbox{lnko}(a',b',c',d')=\mbox{lnko}(a,b,c,d)$. Hasonlóan tudjuk az $A$-t $\begin{pmatrix}1 0 & t & 1\end{pmatrix}$-gyel
%$\\10t1$-gyel 
balszorozni a probléma megváltoztatása nélkül.

Az oszlopokkal is tudunk manipulálni úgy, hogy az $A$-t kicseréljük az 
$$
\begin{pmatrix}
1 & t\cr 0 & 1
\end{pmatrix} = 
\begin{pmatrix}
a'' & b'' \cr c'' & d''
\end{pmatrix}
$$ 
mátrixra, 
%$A''=A\\1t01=\\{a''}{b''}{c''}{d''}$-re, 
ahol $a''=a$, $b''=ta+b$, $c''=c$, $d''=tc+d$.
Ez a mûvelet csak egy kicsit változtatja meg a gyakorlat lényegét: 
Ha találunk egy címkézést, ami kielégíti az $<x,y>=<x+a'',y+b''>=<x+c'',y+d''>$-t minden 
$x$-re és~$y$-ra, akkor $[x,y]=[x+a,y+b]=[x+c,x+d]$, ha
$[x,y]=<x,y+tx>$. Hasonlóan tudjuk az ~$A$-t jobbszorozni a
%%$\\10t1$-gyel; 
$$
\begin{pmatrix}
1 & 0 \cr t & 1
\end{pmatrix}
$$
mátrixszal, a probléma majdnem ugyanaz marad.

Az ilyen sor- és oszlopmûveletek sorozata $A$-t az 
%$U\!AV=\\100n$ 
$\textit{UAV} = \begin{pmatrix} 1 & 0 \cr 0 & n \end{pmatrix}$
alakra egyszerûsíti, ahol $U$ és $V$ egész mátrixok, melyekre teljesül, hogy $\det U=\det V=1$. 
Ha pedig $V=\begin{pmatrix}\alpha & \beta \cr \gamma & \delta\end{pmatrix}$, akkor a redukált feladat címkézése, ami kielégíti 
az $<x,y>=<x+1,y>=<x,y+n>$ feltételt, egy egyszerû megoldást ad az eredeti címkézési feladatra
$[x,y]=<\alpha x+\gamma y,\beta x+\delta y>$ megadással. 
Végül, a redukált címkézési probléma egyszerû: 
legyen $<x,y>=y\mod n$. Így a keresett válasz a $p=\beta$, $q=\delta$ beállítás. 
\ujgyak \label{megold70-138}
Folytatva azt, amit elkezdtünk, de most egy $k\times k$-os $A$ mátrixszal, a sor- és oszlop mûveletek redukálják a 
problémát az $U\!AV$ diagonális mátrixra. A $(d_1,\ldots,d_k)$ diagonális elemek azokkal a feltétellel vannak jellemezve, hogy 
$d_1\ldots d_j$ az $A$ minden $j\times j$-s részmátrixa determinánsainak a legnagyobb közös osztója. 
[Ez a \idez{\textit{Smith normál forma}}; {lásd Smith\angolnevindex{Smith, Mark Andrew} cikkét \cite{Smith1861}}.
Ha az $<x>$ címkézés kielégíti a redukált problémát, az eredeti feladat is meg van oldva
$[x]=<xV>$ választással. Az általánosított tórusz elemeinek száma $n=\det A=d_1\ldots d_k$.

Mint ahogy azt említettük, a redukált problémának van egyszerû megoldása, ha $d_1=\cdots=d_{k-1}=1$. 
De általánosságban a redukált címkézés egy rendes $r$-dimenziós tórusz $(d_{k-r+1},\ldots,d_k)$ dimenzióval, 
ahol $d_{k-r+1}>d_{k-r}=1$. (Itt $d_0=1$; lehetséges, hogy $r=k$.)

A kért példában azt találjuk, hogy $d_1=1$, $d_2=2$, $d_3=10$, $n=20$; valóban,
$$UAV = \begin{pmatrix}1 & -2 & 0\cr 0 & 1 & -1 \cr -1 & -1 & 4\cr\end{pmatrix}
\begin{pmatrix}3 &  1 & 1\cr 1 & 3 &  1 \cr  1 &  1 & 3\cr\end{pmatrix}
\begin{pmatrix}1 &  5 & 6\cr 0 & 1 &  1\cr   0 &  0 & 1\cr\end{pmatrix} =
\begin{pmatrix}1 &  0 & 0\cr 0 & 2 &  0\cr   0 &  0 &10\cr\end{pmatrix}\koz.$$

Minden $(x,y,z)$ ponthoz most egy 2-dimenziós  
$(u,v)=((5x+y)\mod 2, (6x+ y+z)\mod 10)$ címke tartozik.

Az $(u,v)$ 6 szomszédja 
$((u\pm1)\mod2,v)$, $((u\pm1)\mod2,\allowbreak(v\pm1)\mod10)$,
$(u,(v\pm1)\mod 10)$.

Ez egy \textit{multigráf}, mivel az elsõ 2 szomszéd azonos; de ez nem ugyanaz, mint a $C_2\sprod C_{10}$ multigráf, 
amely 8-ad fokú.

{Az általánosított tóruszok tulajdonképpen az Ábel-csoportok {\textit{Cayley-gráfjai}; lásd a \ref{gyak7-136}. gyakorlatot.}  
Úgy vannak tervezve, mint megfelelõ összekapcsolt hálózatok, melyben fontos az átmérõ minimalizálása, 
amikor $k$ és~$n$ meg vannak adva. Lásd Wong\angolnevindex{Wong, Chak-Kuen} és Coppersmith\angolnevindex{Coppersmith, Don} 
\cite{Wong1974}, valamint Fiduccia\angolnevindex{Fiduccia, Charles Michael}, Forcade\angolnevindex{Forcade, Rodney Warring} 
és Zito\angolnevindex{Zito, Jennifer Snyder} cikkét \cite{Fiduccia1998}}. 
\ujgyak \label{megold7-139}
(Ez a gyakorlat segít tisztázni a különbséget a 
$G$ \textit{címkézett gráfok}\gyakindex{címkézett gráf = labeled graph}, ahol a csúcsoknak határozott neve van,
és a \ref{abra7-2}. ábrán látható $H$ \textit{címkézetlen gráfok}\gyakindex{címkézetlen gráf = unlabeled 
graph}\gyakindex{gráf = graph!címkézetlen gráf = unlabeled graph} között.) 
Ha $N_H$ azon címkézett gráfok száma $\{1,2,\ldots,h\}$ felett, amelyek izomorfak ~$H$-val, és ha $U$ bármely $h$-elemû 
részhalmaza ~$V$-nek, annak a valószínûsége, hogy 
$G\rest U$ izomorf ~$H$-val $N_H/2^{h(h-1)/2}$. Ezért a válasz $\binom{n}{h}N_H/2^{h(h-1)/2}$. 
Meg kell határoznunk az ~$N_H$ értékét, amely:
(a)~1; (b)~$h!/2$; (c)~$(h-1)!/2$; (d)~$h!/a$, ahol $H$-nak 
$a$\textit{automorfizmusa}\gyakindex{automorfizmus = automorphism} van.
\ujgyak \label{megold7-140}
(a) $\#(K_3{:}W_n)=n{-}1$ és 
$\#(P_3{:}W_n)= \binom{n -1}{2}$, ha $n\ge 5$; valamint $\#(\,\overline{\!K_3}{:}W_8)=7$.\par
(b) $G$ pontosan akkor arányos, ha 
$\#(K_3{:}G)=\#(\,\overline{\!K_3}{:}G) = \frac{1}{n}\binom{n}{3}$ és
$\#(P_3{:}G)=\#({\overline P}_{\!3}{:}G)= \frac{3}{8}\binom{n}{3}$.
Ha $G$-nek $e$ éle van, akkor $(n-2)e=3\#(K_3{:}G)+2\#(P_3{:}G)
+\#({\overline P}_{\!3}{:}G)$,  mivel minden csúcspár 
$n{-}2$ indukált részgráfban szerepel. Ha $G$-nek $d_1\ldots d_n$ foksorozata van, akkor 
$d_1+\cdots+d_n=2e$, \ ${d_1\choose2}+\cdots+{d_n\choose2}=3\#(K_3{:}G)+\#(P_3{:}G)$, és
$d_1(n{-}1{-}d_1)+\cdots+d_n(n{-}1{-}d_n)= 2\#(P_3{:}G)+2\#({\overline P}_{\!3}{:}G)$.

Ezért egy arányos gráf kielégíti ($*$)-ot -- kivéve ha $n=2$.
(A gyakorlatnak ki kell zárnia ezt az esetet.) 

Másrészt, ha $G$ kielégíti ($*$)-ot és megvan a helyes $\#(K_3{:}G)$ érték, akkor megvan a helyes
$\#(P_3{:}G)$, $\#({\overline P}_{\!3}{:}G)$,
és $\#(\,\overline{\!K_3}{:}G)$ érték is.

{\textit{Hivatkozások:} Janson\angolnevindex{Janson, Carl Svante} és Kratochvíl\angolnevindex{Kratochvíl, Jan} 
cikke \cite{Janson1991}. A \cite{Barbour1989} közleményben 
Barbour\angolnevindex{Barbour, Andrew David}, Karo$\acute{\textnormal{n}}$ski\angolnevindex{Karo$\acute{\textnormal{n}}$ski, 
Micha{\l}} és Ruci$\acute{\textnormal{n}}$ski\angolnevindex{Ruci$\acute{\textnormal{n}}$ski, Andrzej} megmutatta, 
hogy a $\#(H{:}G)$ eltérése arányos vagy $n^{2h-2}$-vel, vagy $n^{2h-3}$-mal, vagy $n^{2h-4}$-el, ahol az elsõ eset akkor áll elõ, 
ha $H$-nak nincsen $\half{\binom{h}{2}}$ éle, és a harmadik eset akkor áll elõ, ha $H$ arányos gráf.}
\ujgyak \label{megold7-141}
Csak 8 darab $d_1\ldots d_8$ foksorozat elégíti ki ($*$)-ot:
73333333\thinspace(1/2), 65433322\thinspace(26/64),\linebreak
\noindent 64444222\thinspace(2/10), 64443331\thinspace(8/22),
55543222\thinspace(8/20), 55533331\thinspace(2/10), 
55444321\thinspace(26/64), és \linebreak
\noindent 44444440\thinspace(1/2). Minden foksorozat itt $(N_1/N)$ statisztikával van bemutatva, 
ahol $N$ nemizomorf gráfnak van ez a sorozata, és $N_1$ közülük arányos. Az utolsó három eset az elsõ három komplementere.

Nincs olyan 8-ad rendû gráf, amely egyszerre arányos és \textit{komplementerével megegyezõ}.
Maximálisan szimmetrikus példák az elsõ 5 esetre $W_8$,
$$\epsfbox{\figdir/v4a.2200}\koz, \quad \epsfbox{\figdir/v4a.2201}\koz, \quad \epsfbox{\figdir/v4a.2202}\koz \quad és
\epsfbox{\figdir/v4a.2203}\koz.$$
\ujgyak \label{megold7-142}
A tipp ugyanaz, mint amit az elõzõ feladatban csináltunk;
$(n-3)\#({\overline{K}}_{\!3}{:}G)$ és $(n-3)\#(P_3{:}G)$ 
kifejezhetõ négycsúcsok számában. Továbbá egy $e$ élû gráfra 
${e\choose2}=\#(P_3\subseteq G)+ \#(K_2\dirsum K_2\subseteq G)$, mivel bármely két él 
$P_3$-at vagy $K_2\dirsum K_2$-t alkot; ebben a formulában $\#(P_3\subseteq G)$ nem feltétlenül indukált 
részgráfot számol.

$\#(P_3\subseteq G)= \#(P_3{:}G)+3\#(K_3{:}G)$, és egy hasonló formula kifejezi 
$\#(K_2\dirsum K_2\subseteq G)$-t az indukáltak megszámlálásának a segítségével.

Így egy túlarányos gráfnak arányosnak kell lenni és ki kell elégítenie $e={1\over2}{n\choose2}$-t, 
$\#(P_3\subseteq G)={3\over4}{n\choose3}$-t, $\#(K_2\dirsum K_2\subseteq G)={3\over4}{n\choose4}$-t. 
Ezek az értékek azonban ellentmondanak az ${e\choose2}$ formulának.
\vspace{-2mm}
\ujgyak \label{megold7-143}
Tekintsük azt a gráfot, amelynek csúcsai az $A$-nak a sorai, és amelynek $u\adj v$ élei olyan $u$ és~$v$ sorokat
kötnek össze, amelyek a $j$ oszlop kivételével megegyeznek. Cimkézzünk egy ilyen élt $j$-vel.

Ha a gráfban van kör, töröljük valamely élét a körnek, és ismételjük a folyamatot mindaddig, amíg nem lesz kör. Vegyük észre, 
hogy a törölt élnek a címkéje valahol máshol feltûnik a körben; így a törlés nem befolyásolja az él címkék halmazát. 
Ekkor azonban már csak kevesebb, mint $m\le n$ él maradt a 2.3.4.1A tétel szerint; tehát kevesebb, mint $n$ különbözõ címke van.
{Lásd Bondy cikkét \cite{Bondy1972}.}
\ujgyak \label{megold7-144}
Legyen $G$ gráf az $\{1,\ldots,m\}$ csúcsokkal, és 
$i\adj j$ élekkel akkor és csakis akkor, ha $\ast\neq x_{il}\neq x_{jl}\ne\ast$ valamely ~$l$-re. Ez a gráf pontosan akkor 
$k$-színezhetõ, ha van egy kiegészítése legfeljebb $k$ különbözõ sorral. Másrészt, ha $G$ egy gráf $\{1,\ldots,n\}$ élekkel, 
$A$ \textit{szomszédsági mátrixszal},\gyakindex{illeszkedési mátrix = incidence matrix} az $n\times n$-es $X=A+\ast(J-I-A)$ 
mátrixnak van az a tulajdonsága, hogy $i\adj j$ pontosan akkor, ha $\ast\neq x_{il}\neq x_{jl}\neq\ast$ valamely~$l$-re.
{Lásd Sauerhoff\angolnevindex{Sauerhoff, Martin} és Wegener\angolnevindex{Wegener, Ingo Werner} cikkét \cite{Sauerhoff1996}.}
\ujgyak \label{megold7-145}
Legyen $c\gets 0$ és ismételjük a következõ mûveleteket $1\le j\le n$-re: Ha $c=0$, akkor legyen $x\gets a_j$ és $c\gets 1$;
egyébként, ha $x=a_j$, legyen $c\gets c+1$; egyébként legyen $c\gets c-1$. Ekkor $x$ a válasz.

Az ötlet az, hogy tartsuk szemmel a lehetséges $x$ gyakori elemet, amely $c$ alkalommal fordul elõ a nem elhagyott elemek között;
Elhagyjuk az $a_j$-t és egy $x$-et mindannyiszor, ha találunk $x\neq a_j$-t.
{Lásd Wos\angolnevindex{Wos, Larry} cikkét \cite{Wos1991}.} 

{Az összes olyan elem megkeresésének kiterjesztését $O(n\lg k)$ lépésben, amely több, mint $n/k$ alkalommal fordul elõ,
Misra\angolnevindex{Misra@\string\Misra} és Gries\angolnevindex{Gries, David Joseph} cikke tárgyalja \cite{Misra1982}.}
\end{gyak}
}

\bibliography{KnuthMarcius30}
\bibliographystyle{infalg}

\begin{printindex}
\end{printindex}


\begin{printangolnevindex}
\end{printangolnevindex}

\begin{printnevindex}
\addtocontents{toc}{\vspace{21mm}}
\addtocontents{toc}{\hfill A szerzõ különösen hálás az Addison-Wesley Kiadónak

\hfill a türelméért, amiért a szerzõdés aláírásától egy teljes évtizedet várt

\hfill a kéziratra.

\hfill -- FRANK HARARY, \textit{Graph Theory} (1968) \cite{Harary1968}

\vspace{8mm}

\hfill Bitte ein Bit!

\hfill A Bitburger Sörfõzde jelszava (1951)
\protect\expandafter\protect\angolnevindex{Harary, Frank (1921--2005)}
\protect\expandafter\protect\angolnevindex{Bitburger Brauerei}
}
\end{printnevindex}

\end{document}
