1476 lines
87 KiB
Org Mode
1476 lines
87 KiB
Org Mode
#+TITLE: Bevezetés a számelméletbe 2 Spellbook
|
||
#+AUTHOR: Toldi Balázs Ádám
|
||
#+LaTeX_HEADER: \include{template}
|
||
#+LaTeX_HEADER: \usepackage{bbm}
|
||
* Kombinatorikus leszámlálási alapfeladatok
|
||
** Permutáció
|
||
*** Ismétlés nélküli permutáció
|
||
$k$ különbőző dolog sorrenjeinek száma, ismétlés nélkül.
|
||
Kiszámítása: $k!$
|
||
*** Ismétléses permutáció
|
||
$k$ különbőző dolog sorrenjeinek száma, ismétléssel.
|
||
Kiszámítása: $\frac{(k_1+k_2+..+k_r)!}{k_1!k_2!...k_R!}$
|
||
** Variáció
|
||
*** Ismétlés nélküli variáció
|
||
$n$ különbőző dologból választunk $k$ különbözőt és számít a sorrend.
|
||
Kiszámítása:$\frac{n!}{(n-k)!}$
|
||
*** Ismétléses variáció
|
||
$n$ különbőző dolog közül választunk $k$ darab, nem feltétlenül különböző dolgot és számít hogy milyen sorrendben.
|
||
Kitszámítása: $n^k$
|
||
** Kombináció
|
||
*** Ismétlés nélküli kombináció
|
||
$n$ különböző dolog közül kiválasztunk $k$ darab különbőző dolgot sorrendtől függetlenül.
|
||
Kiszámítása:
|
||
\begin{equation*}
|
||
\begin{pmatrix}
|
||
n\\
|
||
k
|
||
\end{pmatrix}
|
||
=\frac{n!}{(n-k)!k!}
|
||
\end{equation*}
|
||
\subsubsection*{Megjegyzés}
|
||
A $\bigl( \begin{smallmatrix} n\\k \end{smallmatrix}\bigl)$ számokat binominális együtthatónak nevezzük.
|
||
*** Ismétléses kombináció
|
||
$n$ kükönböző dologból kiválasztunk $k$ darab, nem feltétlen különböző dolgot és a sorrend nem számít.
|
||
Kiszámítása:
|
||
\begin{equation*}
|
||
\begin{pmatrix}
|
||
(n-1)+k\\
|
||
k
|
||
\end{pmatrix}
|
||
\end{equation*}
|
||
*** Fontos tudnivaló a binomiális együtthatókról
|
||
\begin{equation*}
|
||
\begin{pmatrix}
|
||
n\\
|
||
k
|
||
\end{pmatrix}
|
||
=
|
||
\begin{pmatrix}
|
||
n\\
|
||
n-k
|
||
\end{pmatrix}
|
||
\end{equation*}
|
||
** Pascal-háromszög
|
||
| $n=0$ | | | | | | | | 1 | | | | | | | |
|
||
| $n=1$ | | | | | | | 1 | | 1 | | | | | | |
|
||
| $n=2$ | | | | | | 1 | | 2 | | 1 | | | | | |
|
||
| $n=3$ | | | | | 1 | | 3 | | 3 | | 1 | | | | |
|
||
| $n=4$ | | | | 1 | | 4 | | 6 | | 4 | | 1 | | | |
|
||
| $n=5$ | | | 1 | | 5 | | 10 | | 10 | | 5 | | 1 | | |
|
||
| $n=6$ | | 1 | | 6 | | 15 | | 20 | | 15 | | 6 | | 1 | |
|
||
|
||
*** Pascal-háromszög elemei
|
||
Minden $n$ sor, $k$. eleme megegyezik $\begin{pmatrix}n\\k\end{pmatrix}$ -val.
|
||
**** Bizonyítás
|
||
Azt kell belátnunk,hogy
|
||
$\begin{pmatrix}n\\k\end{pmatrix}= \begin{pmatrix}n-1\\k\end{pmatrix}+\begin{pmatrix}n-1\\k-1\end{pmatrix}$
|
||
, hiszen ezzel a szabállyal készült a háromszög, és
|
||
$\begin{pmatrix}n\\0\end{pmatrix}=\begin{pmatrix}n\\n\end{pmatrix}=1$(''legszélső
|
||
elemek'').
|
||
|
||
Tegyük fel, hogy van $n$ darab emberünk,közülük egy a király. Ki a karunk
|
||
választani közülük $k$ darabot, ez $\begin{pmatrix}n\\k\end{pmatrix}$ lenne. De
|
||
a lehetséges kiválasztásokat úgy is számolhatjuk,hogy vesszük azokat,amiben
|
||
kiválasztottuk a királyt (Ez $\begin{pmatrix}n-1\\k-1\end{pmatrix}$,hiszen ilyenkor
|
||
a maradék $n-1\text{-ből}$ kell választani $k-1\text{-et}$) és amikor nem választottuk
|
||
ki(Ez pedig $\begin{pmatrix}n-\\k\end{pmatrix}$,mivel a maradék $n-1\text{-ből}$ kell $k$
|
||
darabot). Ez pontosan az amit be akartunk látni.
|
||
|
||
*** Binomiális tétel
|
||
\begin{align}
|
||
(a+b)^n=\sum_{i=0}^{n}a^i\cdot
|
||
b^{n-i}\cdot \begin{pmatrix}n \\ i \end{pmatrix}
|
||
\end{align}
|
||
**** Bizonyítás
|
||
\begin{align}
|
||
(a+b)^n&=(a+b)\cdot(a+b)\cdot\ldots\cdot(a+b)
|
||
\end{align}
|
||
Mivel minden szorzatban az $(a+b)$ egy-egy elemet ki kell választani,így minden
|
||
tagban lesz valamennyi $a$ és valamennyi $b$,de a kitevőjük összege mindig $n$
|
||
lesz. Ebből az következik,hogy minden $a^jb^{n-j}$ éppen annyiszor fordul elő,
|
||
ahány féle képpen ki tudunk választani az $a\text{-ból}$ $j$ darabot:
|
||
$\begin{pmatrix} n \\ j\end{pmatrix}$,ezzel beláttuk a tételt.
|
||
*** Tétel
|
||
A Pascal-háromszög minden $n$. sorának elemeinek összege $2^n$.
|
||
**** Bizonyítás
|
||
\begin{align}
|
||
(1+1)^n=2^n=\sum_{i=0}^{n}1^i\cdot 1^{n-i}\cdot \begin{pmatrix} n \\ i\end{pmatrix} =\sum_{i=0}^{n} \begin{pmatrix} n \\ i \end{pmatrix}
|
||
\end{align}
|
||
Korábban már láttuk(Lásd [[*Pascal-háromszög elemei]] tétel),hogy $\begin{pmatrix} n \\ k \end{pmatrix}$ pont az $n$. sor
|
||
$k$. elem,így az állítás valóban igaz.
|
||
* Gráfelméleti alapfogalmak
|
||
** Gráf
|
||
Egy gráf egy rendezett pár, $G=(V,E)$,ahol $V$ nem-üres halmaz elemeit pontoknak
|
||
vagy csűcsoknak, E elemeit pedig éleknek nevezzük.
|
||
** Egyszerű gráfok
|
||
Olyan gráf,amely nem tartalmaz hurok- és párhuzamos éleket.
|
||
** Részgráf
|
||
$G'(V',G')$ gráf részgráfja $G(V,E)$ -nek,ha $V'\leq V$,$E'\leq E$ és minedn $E'$ -beli él végpontja $V'$ elemei.
|
||
** Feszített részgráf
|
||
$G'(V',E')$ feszített részgráfja $G(V,E)\text{-nek}$, ha $V'\leq V$ és $E'$ az
|
||
összes $E\text{-beli}$ él,ami a $V'\text{-beli}$ csúcsok között fut.
|
||
** Állítás
|
||
A fokok összege az élek számának kétszerese.
|
||
*** Bizonyítás
|
||
Amikor a fokok számát öszegezzük,minden pontra megszámoljuk a hozzá illeszkedő
|
||
éleket. Mivel minden élnek két végpontja van, így minden élet pontosan kétszer számolunk.
|
||
** Teljes gráf
|
||
Bármely két különböző csúcs össze van kötve.
|
||
** Komplementer gráf
|
||
Ugyanazon pontokból áll, teljes gráf $-$ gráf élei
|
||
** Izomorf gráf
|
||
Két gráfot akkor nevezünk izomorfnak, ha pontjaik és éleik kölcsönösen egyértelműen és illeszkedéstartóan megfeleltethetők egymásnak.
|
||
** Élsorozat
|
||
Egy $(v_0,e_1,v_1,e_2,v_2,\dots,e_n,v_n)$ sorozatot élsorozatnak nevezzük,ha
|
||
minden $e_i$ a $v_{i-1}$ és $v_i$ csúcsot összekötő él.
|
||
** Út
|
||
Olyan élsorozat,amelyben minden csúcs különböző
|
||
** Kör
|
||
Olyan út,amelynek kezdőpontja és végpontja megegyezik
|
||
** Összefüggő gráfok
|
||
Két gráf akkor összefüggő ha bármely két csúcsa közt létezik élsorozat/út
|
||
** Komponens
|
||
Összefüggő feszített részgráf,amelyből nem emgy ki él.Nem bővíthető tovább összefüggő pontal.
|
||
** Állítás
|
||
Ha $G$ egy $n$ csúcsú összefüggő gráf, akkor minimum $n-1$ éle van.
|
||
*** Bizonyítás
|
||
Legyen kezdetben $n$ izolált pont($n$ komponens). Kössünk össze kettőt csúcsot egy
|
||
éllel, ekkor $n-1$ komponensből fog állni. Folytatjuk a különböző komponensek
|
||
összekötését addig,amíg 1 összefüggő gráfunk nem lesz. Ez az algoritmus $n-1$
|
||
lépés után megáll,tehát $n-1$ élt húzott be,ezzel bizonyítva az állítást.
|
||
** Fa
|
||
Az összefüggő, körmentes gráfokat fának nevezzük.
|
||
** Tétel
|
||
Minen legalább 2 pontú fában van legalább két első fokú pont.
|
||
*** Bizonyítás
|
||
Legyen a fában a leghoszabb út a $v_1,v_2,\dots,v_k$ csúcsokból álló. Belátjuk,
|
||
hogy mindkét végpont elsőfokú.
|
||
|
||
Tegyük fel hogy $v_k$ nem elsőfokú ,azaz vezet belőle egy él a fa valamely
|
||
pontjába. Az út többi pontjába nem vezethet,hiszen akkor kört alkotna. Ha pedig
|
||
egy új $v_{k+1}$ pontba vezet az él, akkor az eredeti út nem a leghoszabb lenne,
|
||
ez pedig ellentmondás.
|
||
** Tétel
|
||
Minden $n$ csúcsú fának pont $n-1$ éle van.
|
||
*** Bizonyítás
|
||
Tudjuk hogy minden $n$ csúcsú összefüggő gráfnak minimum $n-1$ éle van,tehát azt
|
||
kell belátnunk,hogy fák esetén ennél nem nagyobb.Ehhez egy lemmát vezetünk
|
||
be.
|
||
*** Lemma
|
||
$G$ körmentes, $n$ csúcsú gráf. Ekkor legfeljebb $n-1$ éle van $G$ -nek.
|
||
*** Lemma bizonyítása
|
||
Legyen kezdetben $n$ darab izolált pontunk. Ha egy komponensen belül rajzolnánk
|
||
be éleket,akkor kört alkotnának. Ha két különböző komponenst kötünk össze,akkor
|
||
egyel kevesebb komponensünk lesz. Ezt az eljárást folytatva maximum $n-1$ lépés
|
||
után megáll.
|
||
** Állítás
|
||
Minden legalább $2$ csúcsú fának van levele.
|
||
** Feszítőfa
|
||
$G$ -nek $F$ feszítőfája, ha $F$ fa és $F$ részgráfja G-nek,$F$ minden csúcsot
|
||
tartalmaz.
|
||
** Tétel
|
||
Minden összefüggő gráf tartalmaz feszítőfát.
|
||
*** Bizonyítás
|
||
Ha $G\text{-ben}$ van kör,akkor hagyjuk el a kör egy tetszőleges élét.Ha a
|
||
maradék gráfban még mindig van kör,akkor ismét hagyjunk el egy élet belőle. Az
|
||
eljárást folytassuk amíg van benne kör. Az eljárás végeztével, egy összefüggő
|
||
(hiszen mindig egy kör egyik élét hagytuk el) körmentes gráfot kapunk,ami fa.
|
||
* Gráfok bejárása $\protect \footnote{ \cite{kv} alapján.}$
|
||
** Szélességi bejárás (BFS)
|
||
*** Az algoritmus
|
||
Tegyük fel,hogy az $a$ pontból kiindulva akarjuk ''bejárni'' a gráfot. Először
|
||
járjuk be sorba $a$ összes szomszédját. Utána járjuk be $a$ első szomszédjának
|
||
szomszédait,ahol még nem jártunk, majd $a$ második szomszédjának összes
|
||
szomszédját, és így tovább. Ha már bejártuk $a$ összes szomszédjának összes
|
||
szomszédját,akkor mehetünk abba a pontba,ahol legrégebben jártunk azok közül,
|
||
amelyeknek még nem néztük végig a szomszédait. Ezt az eljárást folytatjuk, amíg
|
||
tudjuk.
|
||
*** Állítás
|
||
A BFS-fában, az $i\text{-edik}$ szint csúcsai $i$ távolságra vannak a kezdőponttól.
|
||
** Minimális összsúlyú feszítőfák(feszítőerdő)
|
||
Rendeljünk egy $G$ gráf éleihez súlyokat,nemnegatív valós számokat. Jelöljük
|
||
$s(e)\text{-vel}$ az $e\text{-hez}$ rendelt súlyt. Ha $X\subseteq E(G)$, akkor
|
||
$X$ súlya $\sum_{e\in X} s(e)$.
|
||
|
||
Ha $F$ feszítőfája $G\text{-nek}$, és $F$ súlya minimális,akkor $F$ minimális
|
||
összsúlyú feszítőfa. Ha $G$ nem összefüggő,akkor feszítő erdői vannak.
|
||
** Kruskal algoritmusa
|
||
*** Az algoritmus
|
||
Az éleket egyesével választjuk ki az éleket a következőek szerint. A legkisebb
|
||
súlyú élekkel kezdjük. A további választásokkor azokat az élek
|
||
választjuk,amelynek a legkisebb a súlya és nem alkot kört az eddig kiválasztott
|
||
élekkel. Az eljárást addig folytatjuk,amíg találunk ilyen éleket, ha nincs
|
||
akkor megállunk.
|
||
|
||
A Kruskal algoritmus egy ún. mohó algoritmus,mivel minden lépésében az éppen
|
||
legjobbnak tűnő lehetőséget választja.
|
||
*** Tétel
|
||
A Kruskal algoritmus $G$ minimális súlyú feszítőerdőjét adja.
|
||
*** Bizonyítás
|
||
Nyilvánvaló hogy az algoritmus végén a kiválasztott élek egy $F$ feszítőerdőt
|
||
alkotnak.
|
||
|
||
Tegyük fel indirekten,hogy $F_0$ minimális súlyú feszítőerdő, és
|
||
$s(F_0)<s(F)$. Ha több ilyen ellenpélda van,akkor válasszuk ki azt,amelyiknek a
|
||
legtöbb közös éle van $F\text{-el}$.
|
||
|
||
Legyen $e_0\in E(F_0)$, de $e_0\notin E(F)$. Ha hozzávesszük $e_0\text{-t}$
|
||
$F\text{-hez}$,akkor egy $C$ kört kapunk. Ha valamely $e\in E(C)-e_0$ élre
|
||
$s(e)>s(e_0)$,akkor az algoritmus $e$ helyett $e_0\text{-t}$ választotta
|
||
volna. Így $s(e)\leq s(e_0)$,minden $e\in E(C)\text{-re}$. Mivel $F_0-e_0$ két
|
||
komponensből áll, kell lennie egy $e_1\in E(C)-{e_0}\subseteq E(F)$ élnek,amely
|
||
két végpontja $F_0-e_0$ két különböző komponenséhez tartozik. Nyilvánvaló,hogy
|
||
$F_1=(F_0-e_0)\cup{e_1}$ is feszítő fa, és tudjuk,hogy
|
||
$s(e_1)\leq(e_0)$. $s(e_1)<(e_0)$ azonban nem lehet,hiszen akkor $F_0$ nem lenne
|
||
minimális,tehát csak $s(e_1)=(e_0)$ lehet igaz. Ekkor viszont $F_1$ egy olyan
|
||
ellenpélda lenne,melynek egyel több közös éle van,mint $F\text{-el}$,mint
|
||
$F_0\text{-nak}$. Ez pedig ellentmond a feltevésnek.
|
||
* Gráfok síkbarajzolhatósága $\protect \footnote{ \cite{kv} alapján.}$
|
||
** Definíció
|
||
Ha egy gráf lerajzolható a síkba úgy, hogy az élei ne messék egymást, akkor a
|
||
gráf síkbarajzolható. A síkbarajzolt gráf a síkot tartományokra
|
||
osztja. Hasonlóan definiáljuk a gömbre rajzolható gráfot.
|
||
** Tétel
|
||
Egy $G$ gráf pontosan akkor síkbarajzolható, gömbre rajzolható.
|
||
*** Bizonyítás
|
||
Egy síkban levő gráf leképezhető egy gömbfelületre oly módon,
|
||
hogy ezt a gömbfelületet valamelyik pontjával a síkra helyezzük, az érintkezési pon-
|
||
tot tekintjük a gömbfelület déli pólusaként, és az északi pólusból, mint vetítési pont-
|
||
ból oly egyenes vonalakat húzunk, amelyek a síkban levő gráf minden egyes pontját
|
||
összekötik az északi pólussal. Ezeknek a vonalaknak egy-egy további metszéspontja
|
||
van a gömbfelülettel, ezek szolgáltatják a kívánt vetítést. Ez az ún. sztereografikus
|
||
projekció. Ez az eljárás megfordítható, ha az északi pólus nem pontja a gráfnak és
|
||
nem halad át rajta él, így a gömbre rajzolt gráfok is leképezhetők a síkba.
|
||
** Euler Tétel(Euler formula)
|
||
Ha egy összefüggő síkbeli gráfnak $n$ csúcsa, $e$ éle és $t$ tartománya van
|
||
(beleértve a külső, nem korlátos tartományt is), akkor eleget tesz az
|
||
Euler-formulának: $n-e+t = 2$.
|
||
*** Bizonyítás
|
||
Tekintsük a gráf egy $C$ körét és ennek egy $a$ élét. A $C$ kör síkot két
|
||
tartományra bontja. Ezeket más élek további tartományokra bonthatják,de mindkét
|
||
részben van egy-egy olyan tartomány,amely $a$ határa. Ha $a\text{-t}$ elhagyjuk
|
||
a két tartomány egyesül,azaz a tartományok száma egyel csökken. Ezzel $n-e+t$
|
||
értéke nem változik ($n-(e-1)+(t-1)=n-e+1+t-1=n-e+t$). Ezt az eljárást addig
|
||
folytatjuk amíg van a gráfban kör. Ezzel egy feszítőfát kapunk. Ezzel viszont
|
||
az állítás triviális,hiszen $t=1 \text{ és } e=n-1 \implies n-(n-1)+1=2
|
||
\Rightarrow 2=2$.
|
||
** Becslés az élek számára egyszerű gráfban
|
||
Ha $G$ egyszerű, síkbarajzolható gráf és pontjainak száma legalább 3, akkor az
|
||
előbbi jelölésekkel $e\leq3n-6$.
|
||
*** Bizonyítás
|
||
Vegyük $G$ egy tetszőleges síkbarajzolását, és a tartományokat határoló élek
|
||
számát jelöljük $c_1,c_2,c_3,\dotsc,c_t\text{-el}$. Mivel a gráf egyszerű így
|
||
minden $c_i\text{-re}$ teljesül,hogy $c_i\geq 3$. Nyilvánvaló, hogy egy él
|
||
legfeljebb két tartomání határához tartozik,tehát ha összegezzük a határoló élek
|
||
számát akkor legfeljebb egy élet kétszer számolunk. Így az alábbi egyenletet
|
||
írhatjuk fel:
|
||
\begin{align}
|
||
3t\leq c_1 + c_2 + c_3 + \dots c_t &\leq 2e \\
|
||
\text{Az Euler-formulát felhasználva} \\
|
||
3(e-n+2)&\leq 2e \\
|
||
e\leq 3(n-2)&= 3n-6
|
||
\end{align}
|
||
** Becslés az élek számára háromszögmentes gráfban
|
||
Ha $G$ egyszerű, síkbarajzolható gráf, minden körének a hossza legalább 4 és
|
||
pontjainak száma legalább 4, akkor az előbbi jelölésekkel $e\leq 2n-4$.
|
||
*** Bizonyítás
|
||
Az [[*Becslés az élek számára egyszerű gráfban][elző tételhez]] hasonlóan bizonyítható,de itt minden tartományt legalább 4 él
|
||
határol. Így $4t\leq2e \implies e \leq 2n-4$
|
||
** Definíció
|
||
A $G$ és $H$ gráfok topologikusan izomorfak, ha a következő transzformációk
|
||
ismételt alkalmazásával izomorf gráfokba traszformálhatóak:
|
||
- Egy élet egy 2 fokú csúcs felvételével kettő részre bontunk
|
||
- Egy 2 fokú csúcsra illeszkedő éleket egybeolvasztunk
|
||
** Kuatowski Tétel
|
||
Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot,
|
||
amely topologikusan izomorf $K_{3,3}\text{-mal}$ vagy $K_5\text{-tel}$.
|
||
*** Bizonyítás
|
||
Ezt a tételt csak egy irányban bizonyítjuk, bemutatjuk hogy a $K_{3,3}$ és a
|
||
$K_5$ nem rajzolhatóak síkba,így ha egy gráf tartalmaz ilyet(vagyis tartalmaz
|
||
egy velük topologikusan izomorf részgráfot),akkor az sem síkbarajzolható.
|
||
|
||
Ha a $K_5$ síkbarajzolható lenne,akkor teljesülne rá az [[*Becslés az élek számára
|
||
egyszerű gráfban]] tétel.5 csúcsa és 10 éle van: $10>3\cdot5-6=9$,ami
|
||
ellentmondás,így a $K_5$ nem rajzolható síkba.
|
||
|
||
A $K_{3,3}$ nem tartalmaz 3 hosszú utat, így alkalmazható a [[*Becslés az élek
|
||
számára háromszögmentes gráfban]] tétel.A $K_{3,3}\text{-nak}$ 6 csúcsa és 9 éle
|
||
van: $9>2\cdot6-4=8$,ez ellentmondás,azaz a $K_{3,3}$ sem rajzolható síkba.
|
||
** Síkbabarjzolható gráfok dualitása
|
||
Minden síkbarajzolható $G$ gráfból, létrehozhatunk egy $G^*$ gráfot a következő eljárás alapján:
|
||
- $G$ minden tartományához,rendelünk egy $G^*\text{-beli}$ csúcsot
|
||
- Két csúcsot akkor kötünk össze,ha a megfelelő tartományoknak,van közös
|
||
határéle
|
||
$G$ és $G^*$ egymás *duálisai*,hiszen ugyanezzel az eljárással egymásba alakíthatóak.
|
||
* Euler- és Hamilton körök $\protect \footnote{ \cite{kv} alapján.}$
|
||
** Definíció
|
||
A $G$ gráf Euler-körének nevezünk egy zárt élsorozatot, ha az élsorozat pontosan
|
||
egyszer tartalmazza $G$ összes élét. Ha az élsorozat nem feltétlenül
|
||
zárt\footnote{tehát nem ugyanaz a kezdő- és végpontja}, akkor Euler-utat kapunk.
|
||
|
||
** Tétel
|
||
Egy összefüggő $G$ gráfban akkor és csak akkor van Euler-kör, ha $G$ minden
|
||
pontjának fokszáma páros.
|
||
*** Bizonyítás
|
||
Először belátjuk,hogy ha egy gráfban van Euler-kör,akkor minden pont foka
|
||
páros. Induljunk ki először egy tetszőleges csúcsból és járjuk be az Euler-köre
|
||
mentén. Vegyük észre,hogy minden csúcsba, annyiszor ''megyünk be'', ahányszor
|
||
''kimegyünk'' belőle,így a ''kilépések'' és a ''belépések'' számának összege éppen a
|
||
csúcs fokszáma. Ez így pedig biztosan páros.
|
||
|
||
A másik irányt(ha minden csúcs foka páros,akkor van Euler-kör) indukcióval
|
||
bizonyítjuk. Tegyük fel,hogy minden $k<n\text{-re}$ teljesül az állítás,és $G$
|
||
legyen egy $n$ csúcsú gráf. Induljunk ki egy tetszőleges pontból, és haladjuk az
|
||
éleken úgy, hogy minden élen csak egyszer mehetünk át. Ha egy pontba
|
||
érünk,amiből nem vezet ki ilyen él,akkor ez csak kiinduló pont lehet,mivel
|
||
minden pont foka páros. Így tehát egy zárt élsorozatot kapunk. Legyen a $H$ egy
|
||
olyan zárt élsorozata $G\text{-nek}$,amelyben az előforduló élek száma
|
||
maximális. Indirekt módon tegyük fel,hogy $H$ nem egy Euler-köre
|
||
$G\text{-nek}$. Vizsgáljuk meg a $G'$ gráfot,amit úgy kapunk,hogy $G\text{-ből}$
|
||
elhagyjuk a $H$ kör éleit. $G'$ nem feltétlenül összefüggő,viszont összesen
|
||
$n\text{-nél}$ kevesebb pontja,van hiszen a kiinduló pont nincs benne. Az
|
||
indukciós feltétel alapján, $G'$ minden komponensében van Euler-kör. Mivel $G$
|
||
összefüggő , $G'$ valamelyik komponensének van olyan pontja,amelyik
|
||
$H\text{-ban}$ szerepel. Nevezzük az ebben a komponensben található Euler-kört
|
||
$H'\text{-nek}$. Tehát ha elindulunk az előbb talált közös pontból, és bejárjuk
|
||
$H\text{-t}$,majd $H'\text{-t}$,akkor egy $H$ élszámánál nagyobb számú zárt
|
||
élsorozatot találtunk,ami ellentmond a feltevésnek. Vagyis $H$ Euler-kör.
|
||
** Tétel
|
||
Egy összefüggő $G$ gráfban akkor és csak akkor van Euler-út, ha $G$ -ben a
|
||
páratlan fokú pontok száma $0$ vagy $2$.
|
||
*** Bizonyítás
|
||
Az előző tételhez hasonlóan belátható,hogy ha $G\text{-ben}$ van Euler-út,akkor
|
||
az Euler út két végpontja kivételével minden pont foka páros.
|
||
|
||
A másik irány bizonyításához is felhasználhatjuk az előző tételt. Ha nincs
|
||
páratlan fokú csúcs,akkor készen vagyunk. Ha 2 darab páratlan fokú csúcs van,
|
||
akkor kössük össze ezeket egy új $e$ éllel. A keletkező $G'$ gráfban minden pont
|
||
foka páros lesz,így van benne Euler-kör,ami tartalmazza az $e$ élt is. Hagyjuk el
|
||
ezt az élet az Euler-körből,így egy Euler-utat kapunk $G$ gráfban.
|
||
** Definíció
|
||
Egy $G$ gráfban Hamilton-körnek nevezünk egy $H$ kört, ha $G$ minden pontját
|
||
(pontosan egyszer) tartalmazza. Egy utat pedig Hamilton-útnak nevezünk, ha $G$
|
||
minden pontját pontosan egyszer tartalmazza.
|
||
|
||
** Tétel
|
||
Ha a G gráfban létezik $k$ olyan pont, amelyeket elhagyva a gráf több mint $k$
|
||
komponensre esik, akkor nem létezik a gráfban Hamilton-kör. Ha létezik $k$ olyan
|
||
pont, amelyeket elhagyva a gráf több mint $k + 1$ komponensre esik, akkor nem
|
||
létezik a gráfban Hamilton-út.
|
||
*** Bizonyítás
|
||
Indirekten tegyük fel,hogy van a gráfban Hamilton-kör, legyen ez
|
||
$(v_1,v_2,\dots,v_n)$ és legyen $v_{i_1},v_{i_2},\dots,v_{i_k}$ az a $k$
|
||
pont,amelyet elhagyva a gráf több mint $k$ komponensre esik. Vegyük észre,hogy
|
||
az elhagyott pontok között összefüggő komponensek maradnak,hiszen két szomszédos
|
||
pontjai között az eredeti Hamilton-kör élei vannak.
|
||
|
||
Ugyanígy beláthatjuk a Hamulton-útra vonatkozó feltevést is. Ha egy
|
||
Hamilton-útból elhagyunk $k$ pontot, legfeljebb $k+1$ összefüggő marad.
|
||
** Tétel(Ore)
|
||
Ha az $n$ pontú $G$ gráfban minden olyan $x, y \in V (G)$ pontpárra, amelyre
|
||
$\{x, y\} \notin E(G)$ \footnote{Tehát szomszédosak} teljesül az is, hogy $d(x) + d(y) \geq
|
||
n$, akkor a gráfban van Hamilton-kör.
|
||
*** Bizonyítás
|
||
Indirekten tegyük fel,hogy a gráf kielégíti a feltételt,de nincs benne
|
||
Hamilton-kör. Vegyünk hozzá a gráfhoz éleket,úgy hogy
|
||
továbbra se legyen benne Hamilton-kör. Ezt egészen addig csináljuk,amíg már nem
|
||
tudunk több ilyen élet hozzávenni. Az így kapott $G'$ gráfra továbbra is
|
||
teljesül a kezdeti feltétel.Ekkor biztosan van benne két olyan pont,hogy
|
||
$\{x,y\} \notin
|
||
E(G')$ és $G'+{x,y}$ gráfban már van egy Hamilton-kör, és Hamilton-út
|
||
is. Legyen ez $P=(z_1,z_2,\dots,z_n)$,ahol $z_1=x$ és $z_n=y$.
|
||
|
||
Ha $x$ szomszédos a $P$ út valamely $z_k$ csúcsával,akkor $y$ nem lehet
|
||
összekötve $z_{k-1}$ csúccsal,hiszen akkor
|
||
$(z_1,\dots,z_{k-1},z_n,z_{n-1},\dots,z_k,z_1)$ egy Hamilton-kört alkotna. Így
|
||
tehát $y$ nem lehet szomszédos legalább $d(x)$ darab csúccsal, ezért
|
||
\begin{align}
|
||
d(y)&\leq n-1-d(x)
|
||
\end{align}
|
||
ami viszont ellentmondás,mert $\{x,y\}\notin E(G)$.
|
||
** Tétel(Dirac)
|
||
Ha egy n pontú G gráfban minden pont foka legalább $n/2$, akkor a gráfban
|
||
létezik Hamilton–kör.
|
||
*** Bizonyítás
|
||
Az [[*Tétel(Ore)]] tételből következik,hiszen ha minden csúcs foka legalább
|
||
$\frac{n}{2}$, akkor teljesül az Ore tétel feltétele,mivel bármely $x,y$
|
||
pontpárra $d(x)+d(y)\geq n$
|
||
* Gráfok színezése $\protect \footnote{ \cite{hj} alapján.}$
|
||
** Definíció
|
||
Legyen $G$ egy gráf és $k\geq1$ egész szám. A $G$ gráf $k$ színnel színezhető,
|
||
ha a $G$ minden csúcsa kiszínezhető $k$ adott (tetszőleges) színnel úgy, hogy
|
||
$G$ bármely két szomszédos csúcsának a színe különböző. A $G$ kromatikus száma
|
||
$k$, ha $G$ $k$ színnel színezhető, de $(k - 1)$ -gyel már nem. $G$ kromatikus
|
||
számának a jele: $\chi(G)$.
|
||
** Definíció
|
||
A $G$ gráf klikkszáma $k$, ha $G$ -ben található $k$ darab csúcs úgy, hogy ezek közül bármely kettő szomszédos, de $k + 1$ ilyen csúcs már nem található.
|
||
$G$ klikkszámának a jele: $\omega(G)$.
|
||
** Állítás
|
||
Minden (hurokélmentes) $G$ gráfra $\omega(G) \leq \chi(G)$ teljesül.
|
||
*** Bizonyítás
|
||
$G$ gráfban található $\omega(G)$ darab csúcs,amelyek közül bármelyik kettő
|
||
szomszédos. Ezeket a csúcsokat tehát $G$ tetszőleges színezésében csupa
|
||
különböző színt kell kapnia.Így legalább $\omega(G)$ színt használ,tehát az
|
||
állítás valóban igaz.
|
||
** Tétel(Zykov konstrukciója)
|
||
Minden $k\geq2$ esetén létezik olyan $G_k$ gráf, amire $\omega(G_k ) = 2$ és
|
||
$\chi(G_k ) = k$.
|
||
*** Bizonyítás
|
||
- $G_2$,azaz $k=2\text{-re}$ elég a $K_2$ gráfot megvizsgálni
|
||
- A továbbiakban $G_k$ megadásához rekurziót használunk:
|
||
* Induljunk ki pl $G_3$ (egy 5 hosszú) ebből megkaphatjuk $G_$k\text{-t}$
|
||
tetszőleges $k\text{-ra}$ (természetesen $k \geq 3$)
|
||
* Tegyük fel,hogy $G_k=(V,E)$ gráfban már adott,hogy $\omega(G_k)=2$ és $\chi(G_k)=k$.
|
||
* Vegyük $G_k\text{-nak}$ $k$ darab diszjunkt példányát,azaz ''másoljuk le'' a
|
||
$V$ csúcshalmazt $k\text{-szor}$
|
||
* Az így kapott csúcshalmazokat $V_1,V_2,\ldots,V_k$ jelöli.
|
||
* Minden $V_i$ halmazban,azokat a csúcsokat kössük,össze mint amik eredetileg is
|
||
össze voltak kötve
|
||
* Ezen kívül $V_1,V_2,\ldots,V_k$ csúcshalmazok közül, válasszuk ki egyet-egyet
|
||
az összes lehetséges módon. Ezekhez vegyünk fel egy új csúcsot, és kössük
|
||
össze a kiválasztott csúcsokkal
|
||
* Az így kapott gráfot jelöljük $G_{k+1}\text{-el}$
|
||
- Jelölje a $V-i\text{-kből}$ kiválasztott $\text{csúcs-}k\text{-asokból}$
|
||
létrejött $G_{k+1}\text{-beli}$ csúcsok halmazát $Z$
|
||
- Megmutatjuk hogy $\omega(G_k)=2$
|
||
* Tudjuk hogy $\omega(G_k)=2$, és minden $V_i$ halmaz $G_k\text{-val}$
|
||
izomorfak. Ebben tehát biztosan nincs háromszög.
|
||
* $Z\text{-beli}$ csúcsok sem alkothatnak háromszöget,hiszen különböző
|
||
$V_i\text{-kbeli}$ csúcsokkal van összekötve
|
||
- Belátjuk,hogy $G_{k+1}$ kiszínezhető $k+1$ színnel
|
||
* Tudjuk,hogy $G_k$ legalább $k$ színnel színezhető csak ki és $\forall V_i$
|
||
izomorf $G_k\text{-val}$
|
||
* Színezzük ki tehát $V_i\text{-ket}$ ugyanazzal a $k$ színnel
|
||
* A $Z\text{-beli}$ csúcsokat színezzük ki $(k+1)\text{-edik}$ színnel.
|
||
* Mivel $Z$ csúcsai között nem futnak élek így ez egy helyes színezés
|
||
- Meg kell mutatnunk,hogy $G_{k+1}$ nem színezhető ki $k$ színnel
|
||
* Válasszuk $V_1\text{-ből}$ egy $1$. színű $v_1$ csúcsot, $V_2\text{-ből}$
|
||
egy $2$. színű csúcsot, stb.
|
||
* Most vegyük az ezekkel összekötött $z \in Z$ csúcsot. Ez nem színezhető ki
|
||
$k$ szín egyikével sem,hiszen minden $k$ színnel szomszédos
|
||
* Ekkor $z$ csak egy $(k+1)\text{-edik}$ színnel színezhető ki
|
||
|
||
** Állítás
|
||
Legyen $G$ (hurokélmentes) gráf és jelölje $\Delta(G)$ a $G$ -beli maximális
|
||
fokszámot (vagyis a $G$ -beli csúcsok fokszámai közül a legnagyobbat). Ekkor a
|
||
mohó színezést a csúcsok tetszőleges sorrendjében végrehajtva az legföljebb
|
||
$\Delta(G) + 1$ színt használ.
|
||
*** Bizonyítás
|
||
Tegyük fel, hogy a mohó színezés, már elérte a $C=\Delta(G)+1$ értéket és a soron
|
||
következő csúcs a $v_i$. Mivel $d(v_i)\leq\Delta(G)$, így legfeljebb $\Delta(G)$
|
||
olyan szín létezhet, amelyet a $v_i$ csúcs nem kaphat meg. Mivel tehát
|
||
$C>\Delta(G)$, ezért kell létezzen egy olyan $t\in{1,\dots,C}$ szín,amit a mohó
|
||
eljárás $v_i\text{-nek}$ adhat.
|
||
*** Következmény
|
||
Minden (hurokélmentes) $G$ gráfra $\chi(G)\leq\Delta(G) + 1$.
|
||
*** Következmény bizonyítása
|
||
Mivel a mohó eljárás $\Delta(G)+1$ színnel kiszínezi $G\text{-t}$,ezért $\chi(G)$ értéke
|
||
nem lehet nagyobb ennél.
|
||
** Definíció
|
||
A $G$ egyszerű gráfot akkor nevezzük intervallumgráfnak, ha léteznek a
|
||
számegyenesen olyan $I_1 , I_2 ,\dots, I_n \subseteq \mathbb{R}$ (korlátos és
|
||
zárt) intervallumok, hogy $G$ ezekből megkapható a következő módon: $G$ csúcsai
|
||
megfelelnek az intervallumoknak és két különböző csúcs pontosan akkor szomszédos
|
||
$G$ -ben, ha a két megfelelő intervallumnak van közös pontja. Ilyenkor azt
|
||
mondjuk, hogy az $\{I_1,I_2 ,\dots, I_n \}$
|
||
|
||
** Tétel
|
||
Legyen $G$ intervallumgráf és tegyük fel, hogy $G$ -t az $\{I_1 , I_2 ,\dots, I_n \}$
|
||
intervallumrendszer reprezentálja. Ekkor ha az $\{I_1 ,I_2,\dots, I_n \}$
|
||
intervallumokat a baloldali végpontjuk szerinti növekvő sorrendbe rendezzük és
|
||
$G$ csúcsainak erre a sorrendjére hajtjuk végre a mohó színezést, akkor az
|
||
eljárás $G$ -t optimális számú, $\chi(G)$ színnel színezi meg.
|
||
*** Bizonyítás
|
||
Jelölje a mohó színezés által használt színek számát $k$. Ekkor a következő
|
||
igaz lesz rá:
|
||
\begin{align}
|
||
k\leq\omega(G)\leq&\underbrace{\chi(G)\leq k}_\text{$k$ szín elég volt}
|
||
\end{align}
|
||
Megmutatjuk hogy a legnagyobb klikk($\omega(G)$) ilyenkor pontosan $k$. Nézzük
|
||
az első olyan $I_j$ intervallumot,amely a $k.$ színt kapta az eljárásban. Ekkor
|
||
bal végpontja benne van a korábbi $I_t,I_{t+1},\dots, I_{t+k-1}$
|
||
intervallumokban. Ezek az $I_j$ intervallummal egy $k$ csúcsú klikket
|
||
alkotnak,azaz $\omega(G)=k=\chi(G)$.
|
||
*** Következmény
|
||
Ha $G$ intervallumgráf, akkor rá $\omega(G) = \chi(G)$ teljesül.
|
||
*** Következmény bizonyítása
|
||
Minden intervallumgráfhoz tartozik $k$ darab szín,amivel már kiszínezhető. Az
|
||
előző tételből pedig láttuk,hogy $k=\omega(G)$. Így adódik a következő:
|
||
\begin{align}
|
||
k\leq\omega(G)\leq&\chi(G)\leq k
|
||
\end{align}
|
||
** Definíció
|
||
A $G$ gráfot páros gráfnak nevezzük, ha a $V(G)$ csúcshalmaza felbontható az $A$
|
||
és $B$ diszjunkt halmazok egyesítésére úgy, hogy a $G$ minden éle egy $A$ -beli
|
||
csúcsot köt össze egy $B$ -belivel. Ilyenkor a szokásos $G = (V ; E)$ jelölés
|
||
helyett a $G = (A, B; E)$ jelölést is használjuk.
|
||
|
||
** Tétel
|
||
A $G$ gráf akkor és csak akkor páros gráf, ha nem tartalmaz páratlan
|
||
hosszú kört.
|
||
|
||
*** Bizonyítás
|
||
Ha $G$ páros gráf, és $C$ egy kör $G\text{-ben}$,akkor $C$ pontjai felváltva
|
||
vannak $A\text{-ban}$ és $B\text{-ben}$,így $V(C)$ nyilván páros. Ha $G$ minden
|
||
köre páros,akkor megadhatunk egy $A$ és $B$ halmazt. Választunk egy tetszőleges
|
||
pontot. Ez lesz az $A$ halmaz első pontja. A szomszédjait $B$ halmazba
|
||
tesszük. A $B$ halmazbeliek szomszédait $A$ halmazba tesszük,és ezeket a
|
||
lépéseket addig ismételjük, amíg az össze pont bekerült az egyik halmazba. Ez
|
||
biztosan jó elosztás lesz,hiszen ha például $A$ halmazban lenne két
|
||
szomszédos,akkor lenne benne páratlan kör,így ellentmondásra jutnánk.
|
||
** Állítás
|
||
Minden $k \geq 1$ egész esetén létezik olyan ($2k$ csúcsú) $G$ gráf és a $G$ csúcsainak egy olyan sorrendje, hogy $\chi(G) = 2$, de a mohó színezést a $G$ -re a
|
||
csúcsoknak ebben a sorrendjében futtatva az eljárás $k$ színt használ.
|
||
* Független/Lefogó pont-/élhalmaz $\protect\footnote{\cite{hj} alapján.}$
|
||
** Definíció
|
||
A $G$ gráfban az $M\subseteq E(G)$ élhalmazt párosításnak vagy független
|
||
élhalmaznak nevezzük, ha ($M$ nem tartalmaz hurokélt és) $M$ semelyik két élének
|
||
nincs közös végpontja. Az $M$ maximális párosítás, ha $G$ -nek nincs $|M|$ -nél nagyobb
|
||
méretű párosítása; a $G$ -beli maximális párosítások méretét $\nu(G)$ jelöli. Az
|
||
M független élhalmaz teljes párosítás, ha $G$ minden csúcsára illeszkedik $M$
|
||
-beli él.
|
||
|
||
** Definíció
|
||
A $G$ gráf csúcsainak egy $X\subseteq V(G)$ halmazát lefogó ponthalmaznak
|
||
nevezzük, ha $G$ minden élének legalább az egyik végpontja $X$ -beli. Az $X$
|
||
minimális lefogó ponthalmaz, ha $G$ -ben nincs $|X|$ -nél kisebb lefogó
|
||
ponthalmaz. A $G$ -beli minimális lefogó ponthalmazok méretét $\tau(G)$ jelöli.
|
||
|
||
** Állítás
|
||
Minden $G$ gráfra $\nu(G)\leq\tau(G)$ teljesül.
|
||
*** Bizonyítás
|
||
Legyen $|M|=\nu(G)$ és $|X|=\tau(G)$.$X$ minden élnek legalább az egyik végpontját
|
||
tartalmazza,így nyilván $M$ éleire is teljesül. Azonban ugyanaz az
|
||
$X\text{-beli}$ csúcs nem illeszkedhet két $M-\text{-beli}$ élre is,mert $M$
|
||
/párosítás/. Tehát, minden $M\text{-beli}$ élre $X\text{-beli}$ csúcsnak kell
|
||
illeszkedni,így $|M|\leq |X|$
|
||
** Definíció
|
||
A $G$ gráf csúcsainak egy $Y\subseteq V(G)$ halmazát független ponthalmaznak nevezzük, ha $Y$ -nak semelyik két tagja nem szomszédos $G$ -ben (és $Y$ -beli csúcsra hurokél sem illeszkedik). A $G$ -beli független ponthalmazok közül a maximálisaknak a méretét $\alpha(G)$ jelöli.
|
||
** Definíció
|
||
Az izolált pontot nem tartalmazó $G$ gráf éleinek egy $Z\subseteq E(G)$
|
||
halmazát lefogó élhalmaznak nevezzük, ha a $G$ -nek minden csúcsára illeszkedik
|
||
legalább egy $Z$ -beli él. A $G$ -beli lefogó élhalmazok közül a minimálisaknak a méretét $\rho(G)$ jelöli.
|
||
** Állítás
|
||
Minden (izolált pontot nem tartalmazó) $G$ gráfra $\alpha(G)\leq\rho(G)$
|
||
teljesül.
|
||
*** Bizonyítás
|
||
Legyen $Y$ egy maximális független ponthalmaz és $Z$ egy minimális lefogó
|
||
élhalmaz. Mivel $Z$ lefogó élhalmaz,minden csúcsra illeszkedik $Z\text{-beli}$
|
||
él,de két $Y\text{-beli}$ csúcsot nem köthet össze egy $Z-\text{-beli}$. Így
|
||
$|Y|\leq |Z|$ és így tehát $\alpha(G)\leq\rho(G)$
|
||
** Állítás
|
||
Legyen $G$ tetszőleges gráf, $X\subseteq V(G)$ csúcshalmaz és $Y = V (G) / X$
|
||
az $X$ komplementere. Ekkor az $X$ pontosan akkor minimális lefogó ponthalmaz
|
||
$G$ -ben, ha $Y$ maximális független ponthalmaz $G$ -ben.
|
||
*** Bizonyítás
|
||
Legyen $H\subseteq V(G)\text{ és } \overline{H}=V(G)/H$
|
||
csúcshalmazok. Megmutatjuk hogy $H$ pontosan akkor lefogó ponthalmaz,ha
|
||
$\overline{H}$ független ponthalmaz. Az,hogy $H$ lefogó ponthalmaz, az azt
|
||
jelenti,hogy $G$ gráfnak minden $\{u,v\}$ élére $u\in H$ és/vagy $v\in H$
|
||
teljesül. Tehát, nincs olyan $\{u,v\}$ él,hogy $u\in \overline{H}$ és $v\in
|
||
\overline{H}$. Ez pedig pontosan azt jelenti,hogy $\overline{H}$ független
|
||
ponthalmaz.
|
||
|
||
Tegyük fel,hogy $X$ minimális lefogó ponthalmaz,ebből következik hogy
|
||
$Y=\overline{X}$ független ponthalmaz. Ha nem volna az,akkor létezne egy
|
||
másik,maximális független $Y_1$ ponthalmaz(tehát $|Y_1|>|Y|$). Ekkor viszont
|
||
létezne $X\text{-nél}$ kisebb lefogó ponthalmaz,ami ellentmond a feltevésnek.
|
||
|
||
Hasonlóan belátható a másik irányba is.
|
||
** Lemma
|
||
Legyen $G$ egy $n$ csúcsú, izolált pontot nem tartalmazó gráf, $k$ pedig tetszőleges nemnegatív egész. Ekkor:
|
||
|
||
- ha $G$ -ben van $k$ élű párosítás, akkor $G$ -ben van legföljebb $n-k$ élű lefogó élhalmaz;
|
||
- ha $G$ -ben van $k$ élű lefogó élhalmaz, akkor $G$ -ben van legalább $n-k$ élű
|
||
párosítás.
|
||
*** Bizonyítás
|
||
Legyen $M$ egy $k$ élű párosítás. Minden olyan $v$ csúcsot esetén,amit $M$ nem fed le,
|
||
válasszunk egy tetszőleges $v\text{-re}$ illeszkedő élt és egészítsük ki
|
||
$M\text{-et}$; a kapott élhalmazt jelölje $Z$. Mivel $M$ összesen $2k$ végpontja
|
||
van, így $n-2k$ élt nem fed le. Így $|Z|\leq k+(n-2k)=n-k$
|
||
|
||
Legyen $Z$ egy $k$ élű lefogó halmaz $G\text{-ben}$ és $H=(V(G),Z)$
|
||
gráf. Ha van $H$ gráfban izolált pont, akkor azokhoz rendeljünk egy hurokélt.
|
||
Jelölje $c$ a $H$ legalább két csúcsból álló komponenseinek számát. Mivel
|
||
a komponensek nyilván összefüggő,így legalább $n_i-1$ éle van. Ezért a legalább
|
||
két csúcsú komponensek együttes élszáma legalább $n-c$. Ezekből $l\geq
|
||
n-c\implies c\geq n-k$
|
||
|
||
Most vegyük $H$ minden legalább két csúcsú komponenséből egy-egy tetszőleges
|
||
élt(amin nem hurokél). A kapott élhalmazt jelölje $M$. Ekkor $|M|=c\geq
|
||
n-k$,valamint $M$ nyilván párosítás,hiszen különböző komponensekből vett éleknek
|
||
nem lehet közös végpontja.
|
||
** Gallai tétele
|
||
Minden $n$ csúcsú $G$ gráfra fennállnak az alábbiak:
|
||
- $\alpha(G)+\tau(G) =n$
|
||
- $\nu(G)+\rho(G)=n$,ha G-nek nincs izolált pontja.
|
||
*** Bizonyítás
|
||
Ha $X$ egy minimális lefogó ponthalmaz, akkor $Y=V(G)/X$ maximális független
|
||
ponthalmaz. Mivel $|X|=\tau(G)$ és $|Y|=\alpha(G)$, valamint $|X|+|Y|=n$,így /(i)/
|
||
állítás tényleg igaz.
|
||
|
||
Legyen $M$ egy maximális, $\nu(G)$ élű párosítás. Ekkor az előző tétel alapján:
|
||
\begin{align}
|
||
\rho(G)&\leq n-\nu(G)\\
|
||
\rho(G)+\nu(G)&\leq n
|
||
\end{align}
|
||
|
||
Most legyen $Z$ egy minimális,$\rho(G)$ élű párosítás. Ekkor az előző tétel
|
||
alapján:
|
||
\begin{align}
|
||
\nu(G)&\geq n-\rho(G) \\
|
||
\nu(G)+\rho(G)&\geq n
|
||
\end{align}
|
||
|
||
A kettőt összevetve pont a /(ii)/ állítást kapjuk.
|
||
** Összefoglaló táblázat
|
||
| | Maximális független | Minimális lefogó | Összeg |
|
||
| pont | $\alpha$ | $\tau$ | $n$ |
|
||
| él | $\nu$ | $\rho$ | $n$ |
|
||
** Tutte tétele
|
||
A $G$ gráfban akkor és csak akkor létezik teljes párosítás, ha a csúcsok minden
|
||
$X\subseteq V(G)$ részhalmazára $c_p (G - X) \leq |X|$ teljesül.
|
||
|
||
|
||
Más szóval: pontosan akkor létezik teljes párosítás $G$ gráfban,ha
|
||
$G\text{-ből}$ bárhogyan $k$ darab csúcsot elhagyva a kapott gráfban páratlan
|
||
sok csúcsú komponenseinek száma legfeljebb $k$.
|
||
*** Jelölések
|
||
**** $G-X$: Az a gráf,amelyet $G\text{-ből}$ az $X$ csúcsai és arra illeszkedő élei elhagyásával kapunk.
|
||
**** $c_p(H)$: $H$ páratlan sok csúcsot tartalmazó komponenseinek száma
|
||
*** Bizonyítás
|
||
- Tegyük fel,hogy $G\text{-ben}$ $\exists$ teljes párosítás.
|
||
- Megmutatjuk,hogy $c_p (G - X) \leq |X|$ ekkor teljesül
|
||
- Rögzítsünk $G\text{-ben}$ egy $M$ teljes párosítást
|
||
- Vegyünk egy tetszőleges $X \subseteq V(G)$ részhalmazt, és hagyjuk el $G\text{-ből}$
|
||
- Tegyük fel, hogy ez után $l$ darab páratlan komponens jön létre: $C_1,C_2,\ldots,C_l$
|
||
- Válasszunk ki egy $C_i$ páratlan komponenst $G\text{-ben}$
|
||
- Figyeljük meg,hogy $C_i$ minden csúcsához tartozik egy $M\text{-beli}$
|
||
él,hiszen $M$ teljes párosítás.
|
||
- Mivel $C_i$ páratlan kell legyen legalább egy $C_i\text{-n}$ beli csúcs,amit egy
|
||
$M\text{-beli}$ él $C_i\text{-n}$ kívüli ponttal köt össze
|
||
- Minden $C_i\text{-hez}$ válasszunk egy ilyet, és jelöljük $v_i\text{-vel}$
|
||
- Ekkor minden $v_i \in X$,hiszen $C_i$ külön komponenst alkot $X$ elhagyása
|
||
után, és mivel $M$ teljes párosítás, így minden $v_i$ különböző
|
||
- Ezzel beláttuk,hogy $X\text{-nek}$ legalább $c_p(G-X)=l$ csúcsa van.($|X|$
|
||
tartalmazhat ennél több pontot is,csak azok nem hoznak létre több páratlan
|
||
csúcsú komponenst)
|
||
|
||
* Párosítások $\protect\footnote{\cite{hj} alapján.}$
|
||
** Párosítások páros gráfokban
|
||
Legyen $G = (A, B; E)$ páros gráf és $M$ egy párosítás $G\text{-ben}$. Ekkor
|
||
egy $G\text{-beli}$ $P$ út javítóút $M\text{-re}$ nézve, ha rá az alábbiak teljesülnek:
|
||
|
||
(1) $P$ egy $M$ által nem fedett $A\text{-beli}$ csúcsból indul;
|
||
|
||
(2) $P$ egy $M$ által nem fedett $B\text{-beli}$ csúcsban ér véget;
|
||
|
||
(3) $P$ -nek minden páros sorszámú éle (tehát a második, negyedik stb.) $M$
|
||
-beli.
|
||
** Alteráló út
|
||
Legyen $G = (A, B; E)$ páros gráf és $M$ egy párosítás $G\text{-ben}$. A
|
||
$G$ -beli $P$ utat alternáló útnak hívjuk, ha rá a [[*Párosítások páros gráfokban]]. Definíció (1) és
|
||
(3) követelményei teljesülnek (de a (2) nem feltétlenül). Más szóval: alternáló
|
||
útnak az olyan utakat nevezzük, amelyek párosítás által nem fedett $A$ -beli
|
||
csúcsból indulnak és minden második élük $M$ -beli.
|
||
|
||
** Lemma
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: lemma1
|
||
:END:
|
||
Tegyük fel, hogy a $G = (A, B; E)$ páros gráf $M$ párosítására nézve nincs
|
||
javítóút $G$ -ben. Vezessük be az alábbi jelöléseket:
|
||
|
||
1. Jelölje $A_1$ , illetve $B_1$ az $M$ által nem fedett $A$, illetve
|
||
$B\text{-beli}$ csúcsok halmazát;
|
||
2. Jelölje $A_2$ azoknak az ($M$ által fedett) $A$ -beli csúcsoknak a
|
||
halmazát, amelyekbe vezet alternáló út;
|
||
3. Jelölje $A_3$ a maradék $A\text{-beli}$ csúcsoknak a halmazát (amelyek tehát $M$
|
||
által lefedettek, de nem vezet hozzájuk alternáló út).
|
||
4. Jelölje $B_2$ , illetve $B_3$ az $A_2$, illetve $A_3$ csúcsainak $M$
|
||
szerinti párjaiból álló $B\text{-beli}$ csúcsok halmazait.
|
||
|
||
Ekkor $G$ -nek nincs olyan éle, amely $A_1 \cup A_2$ és $B_1 \cup B_3$ között
|
||
vezet.
|
||
*** Bizonyítás
|
||
Indirekt módon feltesszük, hogy mégiscsak létezik olyan $\{a,b\}$ él,hogy $a\in
|
||
A_1\cup A_2$ és $b\in B_1\cup B_3$. Ez összesen négy esetet jelent.
|
||
|
||
Ha $a \in A_1$ és $b\in B_1$, az azt jelentené,hogy létezne egy javítóút
|
||
$a\text{-ból}$ $b\text{-be}$, ez viszont ellentmondás.
|
||
|
||
Ha $a \in A_1$ és $b\in B_3$, ekkor $a\text{-ból}$ eljuthatnánk $b\text{-be}$,
|
||
ahonnan a $b\text{-re}$ illeszkedő $M\text{-beli}$ élen át egy $A_3\text{-beli}$
|
||
csúcsba jutnánk egy kétélű alteráló úton. Ez lehetetlen, hiszen $A_3\text{-be}$
|
||
nem vezethet alteráló út.
|
||
|
||
Ha $a \in A_2$ és $b\in B_1$, ekkor $a$ pontba vezet egy $P$ alteráló
|
||
út. $b\text{-el}$ kiegészítve a $P$ utat,egy javító utat kapnánk,ami
|
||
ellentmondás.
|
||
|
||
Ha $a \in A_2$ és $b\in B_3$, akkor létezik egy $P$ alteráló út $a\text{-ba}$. Ha
|
||
ezt kiegészítjük az $\{a,b\}$ éllel és a $b\text{-re}$ illeszkedő $M\text{-beli}$
|
||
éllel, akkor a $P\text{-nél}$ kettővel hosszabb $P'$ alteráló utat kapunk. Ez
|
||
ellentmondás,hiszen $A_3\text{-be}$ nem vezethet alteráló út.
|
||
** Tétel
|
||
Ha a $G = (A, B; E)$ páros gráf $M$ párosítására nézve nincs javítóút,
|
||
akkor $M$ maximális párosítás $G$ -ben.
|
||
*** Bizonyítás
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: t_biz1
|
||
:END:
|
||
Jelölje $M$ élszámát $|M|=k$. Megmutatjuk hogy $G\text{-ben}$ létezik $k$ pontú
|
||
lefogó ponthalmaz,mert ebből következni fog, hogy $M$ maximális. Mivel létezik
|
||
$k$ elemű párosítás,így $\nu(G)\geq k$. A $k$ pontú lefogó halmaz létezéséből
|
||
$\tau(G)\leq k$. A kettőt összerakva: $k \leq\nu(G)\leq\tau(G)\leq k \Rightarrow
|
||
\nu(G)=k$,így $M$ tényleg maximális párosítás.
|
||
|
||
Azt állítjuk hogy a [[#lemma1]] jelölései szerint $X=A_3\cup B_2$ lefogó
|
||
ponthalmaz $G\text{-ben}$. Legyen $e=\{a,b\}$ egy tetszőleges él,ahol $a\in A$ és
|
||
$b\in B$. Ha $a\in A_3$,akkor $e$ egyik végpontja $X\text{beli}$, ha viszont
|
||
$a\in A_2\cup A_3$,akkor a [[#lemma1]] lemma szerint $b\in B_2$,így $X$ ebben az
|
||
esetben is lefogja $e\text{-t}$
|
||
|
||
Most megmutatjuk,hogy $|X|=k$. Mivel $|M|=k$ és $X$ minden $M\text{-beli}$ él egy végpontját
|
||
tartalmazza, így $|X|=k$. ( $A_2$ és $B_2$ között futóknak az
|
||
$A\text{-beli}$ végpontját, az $A_3$ és $B_3$ között futóknak a $B\text{-beli}$
|
||
végpontját.)
|
||
*** Következmény (Kőnig tétele)
|
||
Minden $G$ páros gráfra $\nu(G) = \tau(G)$ teljesül.
|
||
*** Kőnig tétel bizonyítása
|
||
Az [[#t_biz1][előző bizonyításban]] már láttuk,hogy $k \leq\nu(G)\leq\tau(G)\leq k$, ebből
|
||
valóban következik az állítás.
|
||
*** Következmény
|
||
Ha a $G$ páros gráf nem tartalmaz izolált pontot, akkor rá $\alpha(G) = \rho(G)$
|
||
teljesül.
|
||
*** Következmény bizonyítása
|
||
[[*Következmény (Kőnig tétele)][Kőnig tételéből]] tudjuk,hogy $\nu(G)=\tau(G)$,valamint [[*Gallai tétele][Gallai tételőből]]
|
||
tudjuk,hogy $\alpha(G)+\tau(G)=n$ és $\nu(G)+\rho(G)=n$ igazak. Ezekből tehát
|
||
$\alpha(G)=n-\tau(G)=n-\nu(G)=\rho(G)$ valóban következik.
|
||
** Definíció
|
||
Legyen $G = (A, B; E)$ páros gráf és $X\subseteq A$ egy tetszőleges részhalmaza
|
||
$A$ -nak. Ekkor az $X$ szomszédságának nevezzük és $N(X)$ -szel jelöljük a $B$
|
||
-nek azt a részhalmazát, amely azokból a $B$ -beli csúcsokból áll, amelyeknek
|
||
van (legalább egy) szomszédja $X$ -ben. Képletben:
|
||
$$N(X) = \{b\in B : \exists a \in X, \{a, b\} \in E(G) \}$$
|
||
** Tétel(Hall tétele)
|
||
A $G = (A, B; E)$ páros gráfban akkor és csak akkor létezik $A\text{-t}$ lefedő
|
||
párosítás, ha minden $X\subseteq A$ részhalmazra $|N(X)| \geq |X|$ teljesül.
|
||
*** Bizonyítás
|
||
A szükségesség nyilvánvaló,hiszen ha nem így volna, akkor nem jutna minden
|
||
$A\text{-beli}$ csúcshoz pár.
|
||
|
||
Most megmutatjuk,hogy ha $|N(X)|\geq |X|$ $\forall X\subseteq A$ esetén,akkor
|
||
$\exists A\text{-t}$ lefedő párosítás. Tegyük fel indirekt módon.Futtassuk le a
|
||
javító utas algoritmust végig. Ekkor nem létezik $A\text{-t}$ fedő párosítás,
|
||
így $A_1\neq\varnothing$.Ezért $N(A_1\cup A_2)=B_2$ lemma miatt. Ha viszont ez
|
||
$X=A_1\cup A_2$,akkor $|X|>N(X)=B_2$ (Hiszen $|B_2|=|A_2|$ és $A_1\neq\varnothing$),ami ellentmondás.
|
||
*** Következmény (Frobenius tétele)
|
||
A $G = (A, B; E)$ páros gráfban akkor és csak akkor létezik teljes párosítás, ha
|
||
$|A| = |B|$ és minden $X \subseteq A$ részhalmazra $|N(X)| \geq |X|$ teljesül.
|
||
*** Frobenius tételének bizonyítása
|
||
A szükségesség itt is nyilvánvaló,hiszen minden $A\text{-beli}$ csúcshoz egy
|
||
$B\text{-beli}$ csúcsot akarunk rendelni.
|
||
|
||
A Hall tételben már láttuk az elégségességét,és mivel $|A|=|B|$,így a szerepük felcserélhető
|
||
* Gráfok élszínezése $\protect\footnote{\cite{hj} alapján.}$
|
||
** Teljes párosítás reguláris gráfban
|
||
Ha a $G = (A, B; E)$ páros gráf $d\text{-reguláris}$, ahol $d \geq 1$ tetszőleges egész,
|
||
akkor $G$ -ben van teljes párosítás.
|
||
*** Bizonyítás
|
||
Mivel $G$ $d\text{-reguláris}$, ezért $|E|=d\cdot|A|$ és $|E|=d\cdot|B|$. Ezek
|
||
miatt $|A|=|B|$ adódik.
|
||
|
||
Legyen $X\subseteq A$ tetszőleges csúcshalmaz, és jelölje $E_X$ az $X\text{-re}$
|
||
illeszkedő élek halmazát. Mivel minden $X\text{-beli}$ csúcsra $d$ darab
|
||
$E_X\text{-beli}$ él illeszkedik,így $|E_X|=d\cdot|X|$. $N(X)$ csúcsokra nem
|
||
csak $E_X\text{beli}$ élek illeszkedhetnek,de az elmondható,hogy legfeljebb $d$
|
||
darab illeszkedik, így $|E_X|\leq d\cdot|N(X)|$. Így adódik,hogy $|X|<|N(X)|$,
|
||
ezzel beláttuk a tételt.
|
||
** Definíció
|
||
Legyen $G$ egy gráf és $k \geq 1$ egész szám. A $G$ gráf $k$ színnel
|
||
élszínezhető, ha a $G$ minden éle kiszínezhető $k$ adott (tetszőleges) színnel
|
||
úgy, hogy $G$ bármely két szomszédos (vagyis közös csúcsra illeszkedő) élének a
|
||
színe különböző. A $G$ élkromatikus száma $k$, ha $G$ $k$ színnel élszínezhető,
|
||
de $(k - 1)$ -gyel már nem. G élkromatikus számának a jele: $\chi_e(G)$.
|
||
|
||
** Állítás
|
||
Minden (hurokélmentes) $G$ gráfra $\Delta(G) \leq\chi_e(G)$ teljesül.
|
||
*** Bizonyítás
|
||
Legyen $v$ egys $\Delta(G)$ fokú csúcs. Ekkor a $v\text{-re}$ illeszkedő éleket
|
||
csak $\Delta(G)$ darab különböző színnel színezhető ki. Így $G$ minden élszínezése
|
||
legalább $\Delta(G)$ színből áll.
|
||
** Vizing tétele
|
||
Minden G *egyszerű* gráfra $\chi_e(G) \leq \Delta(G) + 1$ teljesül.
|
||
** Kőnig élszínezési tétele
|
||
Minden $G = (A, B; E)$ páros gráfra $\chi_e(G) = \Delta(G)$ teljesül.
|
||
*** Bizonyítás
|
||
Tegyük fel,hogy a $G$ gráf $k\text{-reguláris}$ reguláris.Ha $k=0$ akkor készen
|
||
vagyunk. Ha $k\geq1\implies\exists$ teljes párosítás: $P_1$. Színezzük ki a $P_1$ élei
|
||
$1\text{-es}$ színnel, majd hagyjuk el őket a gráfból. Az így kapott
|
||
$G_1$ gráf pont $(k-1)\text{-reguláris}$,így létezik benne egy $P_2$ teljes
|
||
párosítás. Legyenek $P_2$ élei $2\text{-es}$ színnel kiszínezve, majd hagyjuk el
|
||
őket a gráfból Ezt az eljárást addig folytatjuk,amíg $k>0$.Ezzel $k$ darab
|
||
teljes párosításunk lesz $\implies\chi_e(G)=k=\Delta(G)$.\\
|
||
Nem reguláris $G$ gráf esetén: Kiegészítjük $k\text{-regulárissá}$
|
||
- Ha $|A|\neq |B|$,akkor $A$ és $B$ közül a kisebbiket kiegészítjük annyi
|
||
pontal, hogy egyenlőek legyenek
|
||
- Ezután kiegészítjük új élekkel addig,amíg minden csúcsa $k$ fokú nem
|
||
lesz,ahol $k=\Delta(G)$.
|
||
- Ez minden esetben lehetséges lesz,hiszen $|A|=|B|$ és A csúcsainak fokának összege
|
||
mindig egyenlő $B$ csúcsainak fokának összgével
|
||
- Az így kapott $G'$ gráf kiszínezhető $k$ darab színnel (hiszen
|
||
$k\text{-reguláris}$)
|
||
- $G$ a gráf $G'$ gráf részgráfja, így a kapott színezés $G$ gráfra is jó.
|
||
|
||
* A maximális folyam $\protect\footnote{\cite{hj} alapján.}$
|
||
** Definíció
|
||
Legyen adott a $G = (V, E)$ irányított gráf, annak az $s,t\in V(G)$
|
||
egymástól különböző csúcsai és a $c : E \rightarrow \mathbb{R}^+$ kapacitás
|
||
függvény (ami tehát minden $e\in E$ élhez egy nemnegatív $c(e)$ kapacitás
|
||
értéket rendel). Ekkor a $(G, s,t, c)$ négyest hálózatnak nevezzük.
|
||
|
||
** Definíció
|
||
Egy adott $(G, s,t, c)$ hálózat esetén folyamnak nevezzük az $f : E \rightarrow
|
||
\mathbb{R}^+$ függvényt, ha rá az alábbi feltételek teljesülnek:
|
||
|
||
1. $0 \leq f (e) \leq c(e)$ minden $e \in E(G)$ él esetén;
|
||
|
||
2.
|
||
\begin{equation}
|
||
\sum_{e:v\rightarrow}^{} f(e)=\sum_{e:v\leftarrow}^{} f(e) \text{ minden } v\in V,v\ne s,t \text{ csúcs esetén}
|
||
\end{equation}
|
||
** Definíció
|
||
A $(G, s,t, c)$ hálózatban adott $f$ folyam $m_f$ -fel jelölt értéke:
|
||
\begin{equation}
|
||
m_f=\sum_{e:
|
||
s\rightarrow}^{} f(e)-\sum_{e:s\leftarrow}^{} f(e)
|
||
\end{equation}
|
||
** Definíció
|
||
Legyen $f$ folyam a $(G, s,t, c)$ hálózatban. Ekkor az $f$ -hez tartozó $H_f$
|
||
segédgráfot a következő képpen definiáljuk. $H_f$ irányított gráf, amelyre $V
|
||
(H_f ) = V (G)$, vagyis $H_f$ csúcsainak halmaza azonos $G$
|
||
csúcshalmazával. Továbbá $H_f$ élhalmazába kétféle típusú él kerül:
|
||
|
||
- Ha $e = (u, v)$ olyan éle $G$ -nek, amelyre $f (e) < c(e)$, akkor $e=(u,v)$
|
||
a $H_f$ élhalmazába is bekerül; az ilyen élek neve előreél.
|
||
|
||
- Ha $e = (u, v)$ olyan éle $G$ -nek, amelyre $f (e) > 0$, akkor $e$
|
||
megfordítása, az $e' = (v, u)$ él kerül be $H_f$ élhalmazába; az ilyen élek
|
||
neve pedig visszaél.
|
||
|
||
** Definíció
|
||
Legyen $f$ folyam a $(G, s,t, c)$ hálózatban. Ekkor a $H_f$ -beli, $s$ -ből
|
||
$t$ -be vezető irányított utakat javítóútnak nevezzük $f$ -re nézve.
|
||
|
||
** Definíció
|
||
A $(G, s,t, c)$ hálózatban $s-t$ -vágásnak nevezzük az $X\subseteq V(G)$
|
||
csúcshalmazt, ha rá $s\in X$ és $t\notin X$ teljesül. Ha a szövegkörnyezetből
|
||
$s$ és $t$ szerepe egyértelmű, akkor $st$ -vágás helyett $X$ -et röviden
|
||
vágásnak is hívjuk.
|
||
|
||
** Állítás
|
||
Ha $f$ tetszőleges folyam, $X$ pedig tetszőleges vágás a $(G, s,t, c)$ hálózatban, akkor
|
||
$$m_f=\sum \{f(e)\text{: kilép } X\text{-ből}\}-\sum \{f(e)\text{: belép }
|
||
X\text{-be}\} $$
|
||
*** Bizonyítás
|
||
$X$ minden csúcsára felírunk egy egyenletet:
|
||
\begin{align}
|
||
s-re:&& m_f&=\sum_{e:s\rightarrow}^{} f(e)-\sum_{e:s\leftarrow}^{} f(e)\\
|
||
\text{minden } x\in X,x\neq s \text{ csúcsra}:&& 0&=\sum_{e:x\rightarrow}^{} f(e)-\sum_{e:x\leftarrow}^{} f(e)
|
||
\end{align}
|
||
Ezek definícióból adódnak.
|
||
|
||
Most adjuk össze ezt az $|X|$ darab egyenletet. A bal oldalon $m_f$ fog állni. A
|
||
jobb oldalon meg kell vizsgálnunk minden $e$ élre,hogy hányszor és milyen
|
||
előjellel jelennek meg. Ehhez válasszunk ki egy tetszőleges $e=\{u,v\}$ élt. Mivel
|
||
$u$ és $v$ lehet $X\text{-beli}$ vagy $X\text{-en}$ kívüli így 4 esetet kell
|
||
vizsgálnunk:
|
||
|
||
1. Ha $u\in X$ és $v\in X$, az összegben kétszer jelenik meg $f(e)$, egyszer
|
||
pozitív előjellel(belép) és egyszer negatív előjellel(kilép), így nem számít bele.
|
||
2. Ha $u\in X$ és $v\notin X$, Az összegben egyszer jelenik meg,pozitív
|
||
előjellel, hiszen $e$ kilép $u\text{-ból}$
|
||
3. Ha $u\notin X$ és $v\in X$, Az összegben egyszer jelenik meg,de itt negatív
|
||
előjellel, hiszen $e$ belép $v\text{-be}$
|
||
4. Ha $u\notin X$ és $v\notin X$, egyáltalán nem jelenik meg az összegben
|
||
|
||
Ezzel a felírt $|X|$ darab egyenlet összege éppen az állításban felírt.
|
||
** Definíció
|
||
A $(G, s,t, c)$ hálózatban az $X$ $st$ -vágás $c(X)$ -szel jelölt kapacitása a
|
||
$$c(X)=\sum \{f(e):e\text{ kilép } X\text{-ből}\}$$
|
||
összeg (ahol a fentieknek megfelelően $e = (u, v)$ az $X$ -ből kilépő él, ha $u\in X$ és
|
||
$v\notin X$). A vágás kapacitását a vágás értékének is szokták nevezni.
|
||
** Állítás
|
||
Ha $f$ tetszőleges folyam, $X$ pedig tetszőleges vágás a $(G, s,t, c)$
|
||
hálózatban, akkor $m_f \leq c(X)$.
|
||
*** Bizonyítás
|
||
\begin{align}
|
||
m_f=\sum \{f(e): e\text{ kilép } X\text{-ből}\}-\sum \{f(e): e\text{ belép } \leq \\
|
||
\leq \sum_{}^{} \{ f(e): e \text{ kilép } X\text{-ből} \}-0=c(X)
|
||
\end{align}
|
||
Definícióból: $f(e)\leq c(e)$ felső becslést, illetve $f(e)\geq0$ alkalmaztuk.
|
||
** Tétel
|
||
Ha a $(G, s,t, c)$ hálózatban az $f$ folyamra nézve nincs javítóút, akkor
|
||
$f$ maximális folyam (vagyis nincs $m_f$ -nél nagyobb értékű folyam).
|
||
*** Bizonyítás
|
||
Álljon $X$ vágás azokból a $v$ csúcsokból,melyekből létezik $s\text{-ből}$
|
||
$v\text{-be}$ vezető út a $H_f$ segédgráfban. Mivel nem létezik javítóút,így $X$
|
||
tényleg $st$ vágás lesz.
|
||
|
||
Azt mondjuk,hogy bármely $X\text{-ből}$ kilépő élre igaz lesz, hogy
|
||
$f(e)=c(e)$. Ha ez nem így volna, akkor $f(e)<c(e)$ miatt bekerült volna $H_f$
|
||
élhalmazába, ez viszont ellentmondás, hiszen nincs benne.
|
||
|
||
Minden $e=(u,v)$ $X\text{-be}$ belépő élre igaz,hogy $f(e)=0$. Ha nem így
|
||
volna,akkor $e'(v,u)$, az $e$ megfordítása, bekerül volna $H_f\text{-be}$
|
||
visszaélként. Így $s\text{-ből}$ $u\text{-ba}$ irányított utat kapnánk, ez
|
||
viszont ellentmond annak hogy $u\notin X$.
|
||
|
||
Ebből és az előző állításból következik hogy $m_f=c(X)$,amivel a bizonyítás teljes.
|
||
** Tétel(Edmonds-Karp tétel)
|
||
Ha a $G$ gráf $n$ csúcsú és $m$ élű és a $(G, s,t, c)$ hálózatban a maximális
|
||
folyam keresésére szolgáló javítóutas algoritmus futása során $H_f$ -ben mindig az
|
||
egyik legrövidebb (vagyis legkevesebb élű) $s$ -ből $t$ -be vezető irányított utat választjuk
|
||
javítóútnak, akkor az eljárás legföljebb $n\cdot m$ javító lépés után megáll.
|
||
** Ford-Fulkerson Tétel
|
||
Bármely $(G,s,t,c)$ hálózatra
|
||
$$\text{max}\{m_f:f\text{ folyam}\} = \text{min} \{ c(X):X\text{ }st\text{ vágás},$$
|
||
vagyis a hálózatbeli maximális folyam értéke megegyezik az $st$ -vágások
|
||
kapacításának minimumával.
|
||
*** Bizonyítás
|
||
Futassuk le a javítóutas algoritmust és a kapott folyamot jelölje $f$. Legyen a
|
||
$H_f$ segédgráfban $s\text{-ből}$ elérhető csúcsok alkotta $X$ vágás. Erre
|
||
teljesül,hogy $m_f=c(X)$,jelöljük ezt $d\text{-vel}$.Mivel $\exists$ $d$ értékű
|
||
folyam,így $d\leq \max\{m_f:f\text{ folyam}\}$, a $d$ kapacitású vágás
|
||
létezéséből következik,hogy $\min\{c(X):X\>st\text{-vágás}\}\leq
|
||
d$. Összevetve a következőt kapjuk:
|
||
\begin{align}
|
||
d\leq \max\{m_f:f\text{ folyam}\}\leq \min\{c(X):X\>st\text{-vágás}\}\leq
|
||
d
|
||
\end{align}
|
||
|
||
Ebből már egyértelműen adódik,hogy $\max\{m_f:f\text{ folyam}\}= d =\min\{c(X):X\>st\text{ folyam}\}$
|
||
** Egészértékűségi lemma
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: egér
|
||
:END:
|
||
Tegyük fel, hogy a $(G, s,t, c)$ hálózatban minden $e\in E(G)$ élre $c(e)\in\mathbb{Z}$. Ekkor
|
||
|
||
1. Létezik olyan $f$ maximális folyam a hálózatban, amelyre $f (e)\in\mathbb{Z}$ minden
|
||
$e\in E(G)$ élre és
|
||
2. Ilyen egészértékű maximális folyam a javítóutas algoritmussal található.
|
||
*** Bizonyítás
|
||
Indítsuk el a javítóutas algoritmust egy tetszőleges egészértékű $f$
|
||
folyamtól. Mivel végig egész $\delta$ számok(Hiszen $c(e)-f(e)$ is egész minden
|
||
élre) minimumát vesszük, ezért az algoritmus leállásakor is egészértékű marad,
|
||
és már tudjuk,hogy ez az algoritmus tényleg maximális folyamot ad.
|
||
* Diszjunkt utak $\protect\footnote{\cite{hj} alapján.}$
|
||
** Lemma
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: dilemma
|
||
:END:
|
||
Legyen $f$ olyan, $m_f = d$ értékű folyam a $G$ irányított gráfban az $s$
|
||
termelőből a $t$ fogyasztóba, amire $f (e) = 0$ vagy $f (e) = 1$ minden $e$ élre. Ekkor
|
||
$G\text{-ben}$ létezik $d$ olyan éldiszjunkt irányított út $s\text{-ből}$ $t\text{-be}$, amiknek minden $e$ élére
|
||
$f (e) = 1$.
|
||
*** Bizonyítás
|
||
- Ha $d=0$,akkor az állítás egyértelműen igaz.
|
||
- Tegyük fel tehát,hogy $d\geq1$.
|
||
- Kell lennie olyan $e$ élnek,amire $f(e)=1$
|
||
- Ha egy ilyen él ''bemegy'' egy $a_1$ csúcsba,akkor onnan ki is kell
|
||
menni,hiszen csak akkor lehet folyam
|
||
- Egy élet csak egyszer használhatunk fel,hiszen a $\forall e \text{ élre } c(e)=1$
|
||
- Ezeknek addig kell mennie amíg $t\text{-be}$ nem érnek,hiszen csak ott tud
|
||
''megállni''.
|
||
- Mivel véges sok él van, így az eljárás tényleg le fog állni
|
||
- Ezután elhagyjuk ezt az utat, az így kapott folyamra igaz lesz,hogy $m_f=d-1$
|
||
- Ha $d>0$,akkor megismételjük
|
||
Ezzel beláttuk az állítást.
|
||
** Definíció
|
||
A $G$ irányított gráfban a $Z \subseteq E(G)$ élhalmaz lefogja az $s\text{-ből}$ $t\text{-be}$
|
||
vezető irányított utakat (ahol $s,t \in V (G)$ a gráf két különböző csúcsa), ha minden
|
||
$s\text{-ből}$ $t\text{-be}$ vezető, $G$ -beli irányított út tartalmaz $Z$ -beli élt. Hasonlóan értelmezzük
|
||
ezt a fogalmat irányítatlan $G$ gráfokra is: a $Z \subseteq E(G)$ élhalmaz
|
||
lefogja az $s\text{-ből}$ $t\text{-be}$ vezető irányítatlan utakat, ha minden $s$ és $t$
|
||
végpontú, $G$ -beli irányítatlan út tartalmaz $Z$ -beli élt.
|
||
** Tétel
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: dis_tetel
|
||
:END:
|
||
Legyen adott a $G$ irányított gráf, annak az $s,t \in V (G)$ különböző csúcsai
|
||
és a $k \geq1$ egész. Ekkor az alábbi állítások ekvivalensek:
|
||
1. Létezik $G\text{-ben}$ $k$ éldiszjunkt irányított út $s$ -ből $t$ -be.
|
||
2. Nem létezik $G\text{-ben}$ legföljebb $k - 1$ élű, az $s\rightarrow t$ utakat
|
||
lefogó élhalmaz.
|
||
3. A $(G, s,t, 1)$ hálózatban a maximális folyam értéke $\geq k$
|
||
*** Bizonyítás
|
||
Megmutatjuk,hogy $1.\implies2.,2.\implies3,\text{ majd } 3.\implies1$.
|
||
|
||
**** $1.\implies2$.
|
||
- Tegyük fel,hogy $G\text{-ben}$ $\exists$ $k$ darab $s \rightarrow t$
|
||
éldiszjunkt út: $P_1,P_2,\ldots,P_k$
|
||
- Legyen $Z$ tetszőleges $s \rightarrow t$ utakat lefogó élhalmaz.
|
||
- $Z$ minden útból tartalmaz élt,így minden $P_i\text{-ből}$ is($1\leq i \leq
|
||
k$) tartalmaz egy $e_i \in Z$ élt.
|
||
- Minden $e_i$ különböző,hisz különböző éldiszjunkt utak tartalmazzák
|
||
- Mivel $Z$ tartalmaz $k$ különböző élt,így $|Z|\geq k$, ezzel a $2$. állítást beláttuk
|
||
**** $2.\implies3$.
|
||
- Vegyünk egy tetszőleges $X$ vágást
|
||
- Azt állítjuk,hogy $c(X)\geq k \Longleftrightarrow X\text{-ből kimenő élek
|
||
száma}\geq k$
|
||
- Ez igaz,hiszen különben létezne $\leq k-1$ élű lefogó élhalmaz([[*Ford-Fulkerson Tétel][Ford-Fulkerson tétel alapján]]).
|
||
**** $3.\implies1$.
|
||
- Az [[*Egészértékűségi lemma][egészértékűségi lemma]] miatt $\exists$ olyan maximális folyam,amiy $\forall
|
||
e \text{ élre } f(e)=0\lor f(e)=1\implies d\geq k$
|
||
- A [[#dilemma]] lemma miatt $d=k$
|
||
|
||
** Tétel
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: eldis_tet
|
||
:END:
|
||
Legyen adott a $G$ irányítatlan gráf, annak az $s,t \in V (G)$ különböző
|
||
csúcsai és a $k \geq 1$ egész. Ekkor az alábbi állítások ekvivalensek:
|
||
1. Létezik $G$ -ben $k$ éldiszjunkt irányítatlan út $s$ -ből $t$ -be.
|
||
2. Nem létezik $G$ -ben legföljebb $k - 1$ élű, az $s$ -ből $t$ -be vezető
|
||
irányítatlan utakat lefogó élhalmaz.
|
||
3. A $(H, s,t, 1)$ hálózatban a maximális folyam értéke legalább $k$, ahol a $H$
|
||
irányított gráf úgy készül $G$ -ből, hogy annak minden $\{u, v\}$ élét
|
||
helyettesítjük az $(u, v)$ és $(v, u)$ irányított élekkel
|
||
*** Bizonyítás
|
||
Hasonlóan bizonyítjuk,mint [[#dis_tetel][az előző tételt.]] $1.\implies2.,2.\implies3$. így
|
||
adódik.
|
||
**** $3.\implies1$.:
|
||
- Az [[*Egészértékűségi lemma][egészértékűségi lemma]] miatt $\exists$ olyan maximális folyam,amiy $d$
|
||
értékű és $\forall e \text{ élre } f(e)=0\lor f(e)=1$
|
||
- [[#dilemma]] lemma alapján $\exists d$ darab éldiszjunkt út.
|
||
*** Következmény (Menger tétele éldiszjunkt utakra)
|
||
Minden $G$ (irányított vagy irányítatlan) gráfra és annak az $s,t \in V (G)$,
|
||
$s\neq t$ csúcsaira $\lambda_G (s,t) = \lambda_G' (s,t)$ teljesül.
|
||
|
||
**** $\lambda_G (s,t):=$ $s$ és $t$ közötti éldiszjunkt utak maximális száma $G\text{-ben}$
|
||
**** $\lambda_G' (s,t):=$ A $G\text{-ben}$ $s\rightarrow t$ utakat lefogó pontok minimális száma
|
||
*** Következmény bizonyítása
|
||
A tétel 1. pontjából következik,hogy $\lambda_G(s,t)\geq k$. A 2. pontjából pedig
|
||
az következik hogy $\lambda_G'(s,t)\geq k$. Mivel a 1. és 2. ekvivalensek,így
|
||
$\lambda_G(s,t)=\lambda_G'(s,t)$. Figyeljük meg,hogy ezzel nem vagyunk
|
||
készen,hiszen attól hogy egy $P$ út éldiszjunkt $H\text{-ban}$,nem jelenti
|
||
azt,hogy $G\text{-ben}$ is éldiszjunkt. Ez úgy oldható meg,hogy ha egy $e=\{u,v\}$
|
||
élből készült $e_1=(u,v)$ és $e_2=(v,u)$ élekre fennáll az,hogy
|
||
$f(e_1)=f(e_2)=1$, akkor mindkét értéket változtassuk meg nullára. Ezzel egy
|
||
$f$ folyamot kaptunk,ahol $m_f$ maximális. Ezzel beláttuk a tételt.
|
||
** Definíció
|
||
A $G$ irányított gráfban az $Y \subseteq V (G)$ csúcshalmaz lefogja az $s$ -ből
|
||
$t$ -be vezető irányított utakat (ahol $s,t \in V (G)$ a gráf két különböző
|
||
csúcsa), ha $s \notin Y, t \notin Y$ és minden $s$ -ből $t$ -be vezető, $G$
|
||
-beli irányított út tartalmaz $Y$ -beli csúcsot. Illetve hasonlóan irányítatlan
|
||
G gráfok esetében is: az $Y \subseteq V (G)$ csúcshalmaz lefogja az $s$ -ből $t$
|
||
-be vezető irányítatlan utakat, ha $s\notin Y, t\notin Y$ és minden $s$ és
|
||
$t$ végpontú, $G$ -beli irányítatlan út tartalmaz $Y$ -beli csúcsot.
|
||
** Tétel
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: pdt
|
||
:END:
|
||
Legyen adott a $G$ irányított gráf, az $s,t \in V (G)$ különböző csúcsok,
|
||
amelyekre $(s,t)\notin E(G)$ és a $k \geq 1$ egész. Ekkor az alábbi állítások ekvivalensek:
|
||
1. Létezik $G$ -ben $k$ pontdiszjunkt irányított út $s$ -ből $t$ -be.
|
||
2. Nem létezik $G$ -ben legföljebb $k - 1$ csúcsú, az $s$ -ből $t$ -be vezető irányított
|
||
utakat lefogó csúcshalmaz.
|
||
3. A $(H, s,t, 1)$ hálózatban a maximális folyam értéke legalább $k$, ahol a $H$
|
||
irányított gráf úgy készül $G$ -ből, hogy annak minden, $s$ -től és $t$ -től különböző
|
||
$v$ csúcsát széthúzzuk a $(v_1, v_2 )$ éllé
|
||
*** Bizonyítás
|
||
**** $1.\implies2$.:
|
||
- Legyenek $P_1,P_2,\ldots,P_k$ $s\rightarrow t$ pontdiszjunkt utak,továbbá
|
||
legyen $Y$ egy tetszőleges $s\rightarrow t$ utakat lefogó csúcshalmaz.
|
||
- Válasszunk $1\leq i \leq k$ esetén $P_i\text{-ből}$ egy olyan $v_i$ csúcsot,
|
||
amire $v_i\in Y$.
|
||
- Választhatunk így $k$ különböző $v_1,v_2,\ldots,v_k$ csúcsot, és mivel
|
||
$v_i\neq s$ és $v_i\neq t$, így $|Y|\geq k$
|
||
**** $2.\implies3$.:
|
||
- Vegyünk egy tetszőleges $X\subseteq V(H)$ vágást,amire $c(X)=p$
|
||
- Mivel $H$ minden $e$ élére $c(e)=1$,vagyis $X\text{-ből}$ $p$ darab él lép ki
|
||
- Ezek közül válasszunk ki egy tetszőleges $e$ élt. Ekkor $e$ lehet:
|
||
- Egy $v\neq s,t$ csúcs széthúzásával keletkező él
|
||
- Egy eredeti $G\text{-beli}$ él
|
||
- Ha eredeti él,azaz $e=(v_2,u_1)$ alakú, akkor kettő műveletet végezhetünk rajta:
|
||
1) Ha $v_2\neq s$,akkor $v_2\text{-t}$ dobjuk ki $X\text{-ből}$
|
||
2) Ha $u_1\neq t$,akkor $u_1\text{-et}$ bevesszük $X\text{be}$
|
||
- Ezek közül legalább egy végrehajtható,hiszen $(s,t)\notin E(G)$
|
||
- A keletkezett vágást jelölje $X'$
|
||
- Ez lefogja az irányított utakat $H\text{-ban}$, ezek az utak
|
||
megfeleltethetők $G\text{-beli}$ utakkal
|
||
- Így $X'$ vágásból $k$ él lép ki,tehát $k\leq p=c(X)$ adódik
|
||
- [[*Ford-Fulkerson Tétel][Ford-Fulkerson tételből]] következik,hogy
|
||
$max\{m_f:f\>\text{folyam}\}\geq k$ teljesül, így a 3. pontot beláttuk
|
||
**** $3.\implies1$.
|
||
- A [[#egér]] lemma miatt következik, hogy $m_f=d\geq k$ értékű folyam
|
||
- Ebből [[#dilemma]] lemmát alkalmazva, azt kapjuk,hogy $\exists P_1,P_2,\ldots,P_d$
|
||
éldiszjunkt irányított utak $s \rightarrow t$
|
||
- Az előzőek szerint minden $P_i$ megfeleltethető egy $G\text{-beli}$ $P'_i$
|
||
éldiszjunkt útnak.
|
||
- $P'_1,P'_2,\ldots,P'_d$ utak pedig pontdiszjunktak,hiszen ha $P'_i$ és $P'_j$
|
||
is tartalmazná $v \neq s,t$ csúcsot $G\text{-ben}$, akkor $P_i$ és $P_j$ is
|
||
tartalmazná a $(v_1,v_2)$ élt $H\text{-ban}$.
|
||
** Tétel
|
||
Legyen adott a $G$ *irányítatlan* gráf, az $s,t \in V (G)$ különböző csúcsok,
|
||
amelyekre $\{s,t\} \notin E(G)$ és a $k \geq 1$ egész. Ekkor az alábbi állítások ekvivalensek:
|
||
1. Létezik $G$ -ben $k$ pontdiszjunkt irányítatlan út $s$ -ből $t$ -be.
|
||
2. Nem létezik $G$ -ben legföljebb $k - 1$ csúcsú, az $s$ -ből $t$ -be vezető
|
||
irányítatlan utakat lefogó csúcshalmaz.
|
||
3. A $(H, s,t, 1)$ hálózatban a maximális folyam értéke legalább $k$, ahol a $H$
|
||
irányított gráf úgy készül $G$ -ből, hogy először $G$ minden $\{u, v\}$ élét
|
||
helyettesítjük az $(u, v)$ és $(v, u)$ irányított élekkel, majd a kapott gráf
|
||
minden, $s$ -től és $t$ -től különböző $v$ csúcsát széthúzzuk a $(v_1 , v_2 )$ éllé
|
||
|
||
*** Bizonyítás
|
||
**** $1.\implies2$.: azonos az [[#pdt][előző tétel]] bizonyításával
|
||
**** $2.\implies3$.:
|
||
- $G$ éleit helyettesítsük irányított élekkel, legyen ez a $G'$ gráf. Ekkor [[#pdt][az
|
||
előző tétel]] szerint legalább $k$ a maximális folyam értéke,abban a
|
||
gráfban,amit $G'$ széthúzásával kapunk. Ez éppen a 3. állítása.
|
||
**** $3.\implies1$.:
|
||
Az előző bekezdés és az [[#pdt][előző tétel]] bizonyításával belátható.
|
||
*** Következmény(Menger tétele pontdiszjunkt utakra)
|
||
Ha a $G$ (irányított vagy irányítatlan) gráfra és annak az $s,t \in V (G)$,
|
||
$s\neq t$ csúcsaira $(s,t)\notin E(G)$, illetve $\{s,t\} \notin E(G)$ teljesül (az
|
||
irányított, illetve az irányítatlan esetben), akkor$ $\kappa_G (s,t) = \kappa'_G (s,t)$.
|
||
**** $\kappa_G (s,t):=$ $s$ és $t$ közötti pontdiszjunkt utak maximális száma $G\text{-ben}$
|
||
**** $\kappa' (s,t):=$ A $G\text{-ben}$ $s\rightarrow t$ utakat lefogó pontok minimális száma
|
||
|
||
** Definíció
|
||
Legyen $G$ (irányítatlan) gráf és $k \geq 1$ tetszőleges egész. A $G$ gráfot
|
||
$k$ -szorosan élösszefüggőnek mondjuk, ha az élei közül bárhogyan legföljebb
|
||
$(k - 1)$ -et elhagyva mindig összefüggő gráfot kapunk. Továbbá $G$ -t $k$ -szorosan
|
||
pontösszefüggőnek (vagy röviden $k$ -szorosan összefüggőnek) mondjuk, ha
|
||
legalább $k + 1$ csúcsa van és a csúcsai közül bárhogyan legföljebb $(k - 1)$
|
||
-et (az azokra illeszkedő élekkel együtt) elhagyva mindig összefüggő gráfot
|
||
kapunk.
|
||
|
||
** Definíció
|
||
A G gráfra $\lambda(G)$, illetve $\kappa(G)$ jelöli a legnagyobb olyan $k$ egészt,
|
||
amire $G$ $k$ -szorosan élösszefüggő, illetve k-szorosan pontösszefüggő.
|
||
|
||
** Tétel (Menger tétele többszörös összefüggőségre)
|
||
Legyen $G$ (irányítatlan) gráf és $k \geq 1$ egész szám. Ekkor
|
||
1. $G$ akkor és csak akkor $k\text{-szorosan}$ élösszefüggő, ha bármely két különböző
|
||
csúcsa között létezik $k$ éldiszjunkt út;
|
||
2. $G$ akkor és csak akkor $k\text{-szorosan}$ pontösszefüggő, ha legalább $k + 1$
|
||
csúcsú és bármely két különböző csúcsa között létezik $k$ pontdiszjunkt út.
|
||
*** Bizonyítás
|
||
**** 1. pont bizonyítása
|
||
- Tegyük fel,hogy $G$ bármely két különböző csúcsa között létezik $k$
|
||
éldiszjunkt út. Ezekből hagyjuk el legfeljebb $k-1$ darabot, és a kapott gráfot jelölje $G'$.
|
||
- Mivel nem hagytuk el az összes éldiszjunkt utat,így legalább egy $P_i$ út még
|
||
benne van $G'$ gráfban
|
||
- Ez definíció szerint azt jelenti,hogy $G'$ összefüggő, $G$ pedig
|
||
$k\text{szorosan összefüggő}$, ezzel az elégségességet beláttuk
|
||
**** 1. pont szükségessége
|
||
- Tegyük fel hogy $G$ $k\text{-szorosan}$ összefüggő és legyen $s,t\in V(G),s
|
||
\neq t$ tetszőleges csúcsok.
|
||
- Ha nem létezne $k$ éldiszjunkt út, akkor a [[#eldis_tet]] tétel szerint az $s
|
||
\rightarrow t$ utakat lefogó $Z$ élhalmaz legfeljebb $k-1$ élű.
|
||
- Ez azonban ellentmondás,hisz a $Z$ elhagyásával a kapott $G'$ gráf nem lenne összefüggő, mert nem volna $s$
|
||
és $t$ között út.
|
||
**** 2. pont bizonyítása
|
||
- Tegyük fel,hogy $G$ bármely két csúcsa között létezik $k$ pontdiszjunkt
|
||
út. Ezek közül hagyjunk el legföljebb $k-1$ darabot és a kapott gráfot jelölje $G'$
|
||
- Mivel minden $s,t\in V(G'),s \neq t$ között létezik út.,így $G'$ definíció
|
||
szerint összefüggő,tehát $G$ $k\text{-szorosan}$ összefüggő
|
||
**** 2. pont szükségessége
|
||
- Tegyük fel, hogy $G$ $k\text{-szorosan}$ összefüggő és legyen $s,t \in V(G), s
|
||
\neq t$
|
||
***** Ha $s$ és $t$ nem szomszédosak:
|
||
Ha nem létezne $k$ pontdiszjunkt út,akkor [[#pdt]]
|
||
tétel szerint létező, az $s$ és $t$ közötti utakat lefogó, legföljebb $k-1$
|
||
csúcs elhagyásával a kapott $G'$ gráf, nem volna összefüggő,ami ellentmondás
|
||
***** Ha szomszédosak
|
||
- Az előbb alkalmazott tétek itt nem használható fel
|
||
- Hagyjuk el az összes $s$ és $t$ közti élt, jelölje ezt a $H$ gráf
|
||
- Tegyük fel indirekt,hogy nem létezik $H\text{-ban}$ $k-1$ pontdiszjunkt $s
|
||
\rightarrow t$ út.
|
||
- Alkalmazhatjuk a [[#pdt]] tételt, eszerint létezik $k-2$ elemű $Y$
|
||
csúcshalmaz,aminek elhagyásával a kapott $H'$ gráf nem összefüggő
|
||
- Emiatt $s$ és $t$ különböző komponensekhez tartoznak.
|
||
- Mivel $G$ $k\text{-szorosan}$ összefüggő,így legföljebb $(k-2)$ csúcsot
|
||
hagytunk el
|
||
- Ekkor találhatunk egy $v \in V(H'),s \neq v \neq t$ csúcsot,ami nyilván csak
|
||
az egyik komponensébe tartozhat. Tegyük fel,hogy $v$ nincs az $s$ komponensében.
|
||
- Most hagyjuk el $G\text{-ből}$ $Y \cup {t}$ csúcshalmazt, és jelöljük a kapott gráfot $G'\text{-vel}$.
|
||
- Ezzel elhagyjuk az $s \rightarrow t$ éleket is,ezért $G'$ minden éle benne van
|
||
$H'\text{-gráfban}$. Így $v$ és $s$ $G'\text{-ben}$ ,vagyis $G'$ nem összefüggő
|
||
- Ez ellentmondás,hiszen $G$ $k\text{-szorosan}$ összefüggő.
|
||
|
||
*** Következmény
|
||
Ha a G gráf $k\text{-szorosan}$ pontösszefüggő, akkor $k\text{-szorosan}$
|
||
élösszefüggő is.
|
||
|
||
*** Következmény bizonyítása
|
||
Ha $G$ $k\text{-szorosan}$ összefüggő, akkor a [[*Tétel (Menger tétele többszörös
|
||
összefüggőségre)]] 2. állítása szerint bármely két csúcsa között létezik $k$
|
||
éldiszjunkt út. Mivel a pontdiszjunkt utak éldiszjunktak is egyben,így a [[Tétel
|
||
(Menger tétele többszörös összefüggőségre)]] tétel 1. állítása alapján $G$ tényleg
|
||
$k\text{-szorosan}$ élösszefüggő.
|
||
* Aciklikus irányított gráfok(DAG) $\protect\footnote{\cite{hj} alapján.}$
|
||
** Fogalma
|
||
Egy irányított $G$ gráfot akkor nevezünk *aciklikusnak*,ha nem tartalmaz
|
||
irányított kört. Angolul Directed Acyclic
|
||
Graph, röviden DAG.
|
||
** Definíció
|
||
Legyen $G = (V, E)$ irányított gráf és $(v_1, v_2,\dots, v_n)$ a $G$ csúcsainak
|
||
egy felsorolása. A $(v_1 , v_2 ,\ldots, v_n )$ sorozatot topologikus rendezésnek
|
||
(vagy topologikus sorrendnek) nevezzük, ha $G$ minden $(x, y)$ élére x előbb van
|
||
a sorozatban, mint $y$ (vagyis ha $x = v_i$ és $y = v_j$ , akkor $i < j$).
|
||
** Tétel
|
||
A $G$ irányított gráfnak akkor és csak akkor van topologikus rendezése, ha
|
||
aciklikus.
|
||
*** Bizonyítás
|
||
- Az szükségessége magától értetődő.
|
||
- Az elégségesség bizonyításához először be kell látnunk,hogy tartalmaz /nyelőt/
|
||
(Olyan csúcsot,amelyből nem indul ki él). Ez szerencsére könnyen található:
|
||
vegyük a gráf leghosszabb $P$ útját, ekkor a $P$ út $v$ végpontja nyelő.
|
||
|
||
- Válasszunk tehát egy nyelő,legyen ez $v_n$,majd hagyjuk el $G\text{-ből}$.
|
||
- A kapott $G'$ gráfban,szintén lesz egy $v_{n-1}$ nyelő, ezt is hagyjuk el.
|
||
- Folytassuk az eljárást amíg lehet
|
||
- A kapott $v_1,v_2,\ldots,v_n$ sorozat nyilván topologikus rendezés.
|
||
** Algoritmus legrövidebb és leghosszabb utak meghatározására aciklikus irányított gráfban.
|
||
Irányított aciklikus gráfokban a legrövidebb és a leghosszabb utat lineáris
|
||
időben meg lehet találni egy egyszerű algoritmussal.
|
||
|
||
Fontos megjegyezni,hogy ebben az esetben minden él rendelkezik egy súllyal,ami
|
||
az út ''hosszát'' jelenit.
|
||
|
||
Keressük meg a $s \rightarrow v$ legrövidebb utat!
|
||
- Ha $s$ a topologikus sorrendben hátrébb szerepel,akkor $\nexists$ ilyen út
|
||
- Különben végig megyünk a csúcsokon $s\text{-től}$ $v\text{-ig}$ a topologikus
|
||
sorrendben. Minden csúcsra adok egy legrövidebb utat,úgy hogy megnézzük milyen
|
||
utak mennek bele,amelyek elérhetőek $s\text{-ből}$ és ezek közül kiválasztjuk
|
||
a legkisebb súlyút.
|
||
Ez az algoritmus leghosszabb út keresésére is alkalmazható.
|
||
* Mélységi keresés $\protect\footnote{\cite{hj} alapján.}$
|
||
** Az algoritmus
|
||
Vegyünk egy tetszőleges $G$ gráfot, és válasszunk ki egy tetszőleges $s$
|
||
csúcsot. Az algoritmus futtatásakor három változót is fenntartunk: A mélységi
|
||
számát(hány csúcsban járt már;Jele: $d(v)$), befejezési szám(hány csúcs lett
|
||
befejezve;Jele: $f(v)$) és az legutóbb bejárt csúcsot(Jele: $m(v)$). A
|
||
kiválasztott $s$ csúcsból kiindulva véletlenszerűen választunk a gráfból egy élt(ami olyan
|
||
csúcsba vezet,ahol még nem jártunk),amerre mehetünk. Ezt addig folytatjuk,amíg
|
||
lehetséges. Minden egyes csúcsbalépéskor növeljük a mélységi számot. Ha az
|
||
algoritmus eljut egy olyan csúcsig,amiből nem vezet több út,akkor egyel
|
||
visszalép,és növeli a befejezési számot. Ha a gráf nem összefüggő és az
|
||
algoritmus az adott komponensben már nem tud tovább lépni, akkor az eddig nem
|
||
bejárt csúcsok közül választ egy tetszőlegest.
|
||
** DFS erdő
|
||
A DFS által bejárt élek egy erdőt alkotnak.
|
||
** Definíció
|
||
Tegyük fel, hogy az $s$ csúcsból indítva lefuttattuk a DFS algoritmust
|
||
a $G$ irányított gráfban. Jelölje a futáshoz tartozó DFS-erdőt $F$. Legyen $e = (u, v)$
|
||
a $G\text{-nek}$ egy tetszőleges éle. Ekkor
|
||
1. $e\text{-t}$ faélnek nevezzük, ha $e \in E(F)$;
|
||
2. $e\text{-t}$ előreélnek nevezzük, ha nem faél, de $F\text{-ben}$ van $u\text{-ból}$ $v\text{-be}$ irányított út
|
||
(vagyis $v$ ''leszármazottja'' $u$ -nak);
|
||
3. $e\text{-t}$ visszaélnek nevezzük, ha $F$ -ben van $v\text{-ből}$ $u\text{-ba}$ irányított út (vagyis $v$
|
||
''őse'' $u\text{-nak}$ );
|
||
4. $e\text{-t}$ keresztélnek nevezzük, ha $F$ -ben sem $u\text{-ból}$
|
||
$v\text{-be}$, sem $v\text{-ből}$ $u\text{-ba}$ nincs irányított út
|
||
(vagyis $u$ és $v$ között nincs ''egyenes ági
|
||
leszármazási viszony'').
|
||
** Tétel
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: dfs
|
||
:END:
|
||
Tegyük fel, hogy a $G$ irányított gráfra a DFS algoritmust futtatva az
|
||
éppen az $e = (a, v)$ élen próbál továbblépni (így az aktív csúcs jelenleg $a$). Ekkor
|
||
$e$ erre a DFS bejárásra vonatkozóan akkor és csak akkor lesz
|
||
1. Faél, ha $d(v) = *$;
|
||
2. Előreél, ha $d(v) > d(a)$;
|
||
3. Visszaél, ha $d(v) < d(a)$ és $f(v) = *$;
|
||
4. Keresztél, ha $d(v) < d(a)$ és $f(v) \neq *$.
|
||
*** Bizonyítás
|
||
- Ha $d(v)=*$,akkor $m(v)=a$,tehát $e$ valóban faél.
|
||
- Egészítsük ki az algoritmust egy $T$ változóval, ami az eltelt időt
|
||
jelenti. Ezzel minden $v$ csúcshoz hozzárendelhetünk egy $kezd(v)$ kezdési
|
||
időt,és egy $bef(v)$ befejezési időt. A kettő közti intervallumot
|
||
$I(v)\text{-tel}$ jelöljük
|
||
- Az eljárás során, $T$ változót mindig növeljük meg, ha belépünk egy új csúcsba.
|
||
- Először vegyük észre,hogy ha veszünk egy $I(v)$ időintervallumot, akkor ehhez
|
||
megfeleltethetünk egy $F_v$ fát,amit ez alatt jár be. Ez egy részgráf lesz
|
||
$F\text{-nek}$.
|
||
- Tegyük fel hogy az $(a,v)$ élen a $T$ pillanatban próbál továbblépni. Ekkor
|
||
$kezd(a)\leq T \leq bef(a)$.
|
||
- Ha $d(v)>d(a)$, akkor $kezd(a)$ pillanatban $d(v)=*$ volt,így $v \in F_a$,azaz
|
||
$e$ egy előreél
|
||
- Ha $d(v)<d(a)$, akkor $kezd(v)$ pillanatban $d(a)=*$ volt. Ha emellett
|
||
$f(v)=*$ is igaz,akkor $kezd(v)<kezd(a)<\leq T < bef(v)$. Ezért $a \in F_v$,
|
||
így $e$ valóban visszaél.
|
||
- Ha $d(v)<d(a)$ és $f(v) \neq *$,akkor $kezd(a)$ pillanatban $I(v)$ már véget
|
||
ért. Így $a \notin F_v$ és $v \notin F_a$,így nincs irányított út
|
||
$F\text{-ben}$ $a \rightarrow v$ irányított út,vagyis $e$ keresztél
|
||
|
||
Mivel minden lehetőséget lefedtünk,így definíció szerint az állításokat beláttuk.
|
||
** Tétel
|
||
Futtassuk le a DFS algoritmust a $G$ irányított gráfban az $s$ csúcsból
|
||
indítva. $G$ akkor és csak akkor aciklikus, ha az eljárás során nem keletkezik
|
||
visszaél és ebben az esetben a befejezési számozás szerinti fordított sorrendben
|
||
felsorolva $G$ csúcsait topologikus rendezést kapunk.
|
||
*** Bizonyítás
|
||
- Ha keletkezik egy $e=(a,v)$ visszaél,akor $G$ nyilván tartalmaz irányított
|
||
kört: $F$ DFS-erdő tartalmaz $v \rightarrow a$ utat,ha ezt kiegészítjük
|
||
$e\text{-vel}$ akkor egy kört kapunk.
|
||
- Tegyük fel, hogy nem keletkezett visszaél,így $G $minden $e=(a,v)$ éle
|
||
faél,előreél vagy keresztél. Ekkor be kell látnunk,hogy $f(v)<f(a)$,mert ezzel
|
||
a második állítás is igaz
|
||
- Használjuk fel a [[#dfs]] tétel bizonyításában használt elveke.
|
||
- Ha $e$ faél vagy előreél, akkor $kezd(v)$ $I(a)\text{-be}$ tartozik,így $F_a$
|
||
részgráfja $F_$v\text{-nek}, azaz $f(a)<f(a)$
|
||
- Ha $e$ keresztél, akkor $T$ pillanatban már $f(v) \ne *$,viszont $f(a)=*$, így
|
||
valóban $f(v)<f(a)$
|
||
* Legrövidebb utak meghatározása adott csúcsból $\protect\footnote{\cite{hj} alapján.}$
|
||
** Definíció
|
||
A $G = (V, E)$ irányított gráf élein a $w : E \rightarrow \mathbb{R}$ függvényt
|
||
konzervatívnak nevezzük, ha $G$ minden (hurokéltől különböző, vagyis legalább két
|
||
élű) irányított körének éleire a $w(e)$ értékek összege nemnegatív.
|
||
** Állítás
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: kort
|
||
:END:
|
||
Legyen adott a $G = (V, E)$ irányított gráf, az $s, v \in V (G)$, $s \neq v$ csúcsok
|
||
és $G$ élein a $w : E\rightarrow\mathbb{R}$ konzervatív hosszfüggvény. Ekkor ha létezik $s\text{-ből}$ $v\text{-be}$ egy
|
||
$t$ összhosszúságú, $k$ élből álló $Q$ élsorozat, akkor létezik $s\text{-ből}$ $v\text{-be}$ egy legföljebb $t$
|
||
összhosszúságú és legföljebb $k$ élű $P$ út is.
|
||
*** Bizonyítás
|
||
- Ha $Q$ nem irányított út,akkor van olyan csúcs,amit többször érint
|
||
- Keressük meg az ilyen ismétlődő pontpárok közül azt,amelyik között a
|
||
legkevesebb él van (Q-ban): legyen ez $u$
|
||
- Ekkor létezik egy $C$ irányított élsorozat $u\text{-ból}$
|
||
$u\text{-ba}$. $C\text{-nek}$ körnek kell lennie,hiszen $u$ választása
|
||
miatt,nem létezhet benne ismétlődő csúcspár (mert akkor azok között kevesebb
|
||
él lenne)
|
||
- Vágjuk ki $Q\text{-ból}$ a $C$ irányított kört, a kapott élsorozat legyen
|
||
$Q_1$.
|
||
- Ekkor $Q_1$ is $s\text{-ből}$ $v\text{-be}$,aminek élszáma $k\text{-vál}$
|
||
kisebb és összhossza legfeljebb $t$ (mivel $w$ konzervatív,így $C$ összhossza
|
||
nemnegatív)
|
||
- Ha $Q_1$ nem irányított út,akkor $Q_1$ is tartalmaz ismétlődő csúcsokat
|
||
- A fentieket ismételjük,addig amíg van ismétlődő csúcs,akkor a kapott amíg
|
||
$Q_n$ egy irányított út lesz.
|
||
- Mivel az eljárás során az összhosz nem nőhet,így az állítást beláttuk
|
||
*** Következmény
|
||
Legyen adott a $G = (V, E)$ irányított gráf, az $s, v \in V (G)$
|
||
csúcsok és $G$ élein a $w : E \rightarrow\mathbb{R}$ konzervatív hosszfüggvény. Ha az $s\text{-ből}$ $v\text{-be}$ vezető
|
||
$P$ legrövidebb út áthalad az $u$ csúcson, akkor $P\text{-nek}$ az $s\text{-től}$ $u\text{-ig}$ tartó $P$ $u$ szakasza
|
||
egy $s\text{-ből}$ $u\text{-ba}$ vezető legrövidebb út.
|
||
*** Következmény bizonyítása
|
||
- Tegyük fel indirekten,hogy $exists s \rightarrow u$ egy $P_u\text{-nál}$
|
||
rövidebb $P'$ út.
|
||
- Ekkor $P'$ mentén haladva eljutunk $s\text{-ből}$ $u\text{-ba}$,majd onnan $P$
|
||
mentén eljutunk $u\text{-ból}$ $v\text{-be}$. Legyen ez a $Q$ élsorozat.
|
||
- Ekkor azonban $Q$ rövidebb $s \rightarrow v$ út $P\text{-nél}$,ami ellentmond
|
||
annak, hogy $P$ legrövidebb út
|
||
** A Bellman-Ford algoritmus
|
||
*** Definíció
|
||
Jelölje $\forall v \in V (G)$ csúcsra és $k \geq 0$ egészre $t_k (v)$ a
|
||
legrövidebb olyan $s\text{-ből}$ $v\text{-be}$ vezető irányított út hosszát, ami
|
||
legföljebb $k$ élből áll; ha pedig ilyen út nincs, akkor legyen $t_k (v) = \infty$.
|
||
*** Állítás
|
||
:PROPERTIES:
|
||
:CUSTOM_ID: kupal
|
||
:END:
|
||
Legyen adott a $G = (V, E)$ irányított gráf, az $s, v \in V (G)$, $v \neq s$ csúcsok
|
||
és $G$ élein a $w : E \rightarrow \mathbb{R}$ konzervatív hosszfüggvény. Ekkor minden $k \geq 1$ esetén
|
||
\begin{align}
|
||
t_k (v) = \min{\{\{t_{k-1}(v)\} \cup \{t_{k-1} (u) + w(e) : e = (u, v), e \in E(G)\}\}}
|
||
\end{align}
|
||
**** Bizonyítás
|
||
- Jelölje $H$ az egyenlet jobb oldalán lévő halmazt.Így azt kell belátnunk hogy
|
||
$t_k(v)$ a $H$ minimuma
|
||
- Ha $t_k(v) = \infty$,akkor persze $t_{k_1}(v) = \infty$ is igaz.
|
||
- Továbbá $e=(u,v)$ élekre is $t_{k-1}(u)= \infty$, hiszen ha nem így volna,akkor
|
||
létezne $s\text{-ből}$ $u\text{-ba}$ egy legföljebb $k-1$ élű út, és ezt
|
||
$e\text{-vel}$ kiegészítve $v\text{-be}$ vezető,legfeljebb $k$ élű utat kapnánk.
|
||
- Tegyük fel tehát,hogy $t_k \neq \infty$
|
||
- Ekkor $t_k(v) \leq t_{k-1}(v)$ nyilván igaz,hiszen legföljebb $k-1$ élű utak
|
||
egyben legföljebb $k$ élű utak
|
||
- Legyen $e=(u,v)$ él. Ekkor $s\text{-ből}$ $u\text{-ba}$ vezető legföljebb $k-1$
|
||
élű és $t_{k-1}(u)$ hosszúságú $P$ utat megtoldunk $e\text{-vel}$
|
||
- Így egy legfeljebb $k$ élű és $t_{k-1}+w(e)$ hosszúságú $Q$ élsorozatot kapunk
|
||
- $Q$, nemfeltétlen út,de [[#kort]] állítás alapján tudjuk,hogy $t_k\leq t_{k-1}+w(e)$
|
||
- Beláttuk hogy $t_k\leq \min{H}$,most megmutatjuk,hogy $H\text{-nak}$ van
|
||
$t_k\text{-val}$ egyenlő eleme
|
||
- Legyen $P$ egy $s\text{-ből}$ $v\text{-be}$ vezető $t_k(v)$ hosszú és
|
||
legfeljebb $k$ élű út.
|
||
- Ha $P$ legfeljebb $k-1$ élű,akkor nyilván legrövidebb a legföljebb $k -
|
||
1$ élű, v-be vezető utak között is, így $t_k= t_{k-1}$
|
||
- Ha $P$ pontosan $k$ élű,akkor jelölje az utolsó élét $e=(u,v)$ és $P$
|
||
$s\text{-től}$ $u\text{-ig}$ vett szakaszát $P_u$
|
||
- Ekkor $P_u$ $t_{k-1}$ hosszú,mivel ha lenne rövidebb és legföljebb $k-1$ élű
|
||
út $u\text{-ba}$ akkor, $e\text{-vel}$ kiegészítve egy $P\text{-nél}$ rövidebb
|
||
utat kapnánk,ami lehetetlen.
|
||
- Így ebben az esetben $t_k(v)=t_{k-1}+w(e)$ tényleg fennáll.
|
||
*** Az algoritmus
|
||
Tegyük fel,hogy $G$ gráf $s$ csúcsából akarunk legrövidebb utakat keresni. Az
|
||
eljárás során mindenegyes csúcshoz hozzárendelhetünk egy számot,ami azt
|
||
jelzi,hogy az eddig megtalált legrövidebb út összhossza mekkora. Ezt az értéket
|
||
minden csúcsra inicializáljuk $\infty\text{-re}$ (kivéve $s\text{-hez}$,hozzá
|
||
nullát rendelünk)
|
||
|
||
Az eljárás során minden ciklusban végigmegyünk $G$ összes csúcsán. Minden
|
||
csúcsban megvizsgáljuk,hogy a belőle kivezető élek rövidebb utat alkotnak-e az
|
||
él végpontjába, mint az eddig megtalált. Ezt ismétli $(n-1)\text{-szer}$.
|
||
*** Állítás
|
||
Tegyük fel, hogy lefuttattuk a Bellman-Ford algoritmust az $n$ csúcsú
|
||
$G = (V, E)$ irányított gráfból, a $w : E \rightarrow \mathbb{R}$ hosszfüggvényből és az $s \in V$ csúcsból
|
||
álló bemenetre. Jelölje $G_s$ az $s\text{-ből}$ $G\text{-beli}$ irányított úton
|
||
elérhető csúcsok és a köztük vezető élek által alkotott részgráfot. Ekkor $w$
|
||
akkor és csak akkor konzervatív $G_s\text{-en}$, ha $G_s$ minden $e = (u, v)$
|
||
élére $t_{n-1} (v) \leq t_{n-1} (u) + w(e)$ teljesül.
|
||
|
||
**** Bizonyítás
|
||
1) Szükségesség:
|
||
- Ha $w$ konzervatív,akkor a [[#kupal]] állításból következően minden $v \in
|
||
V(G_s)$ csúcsra a $t_{n-1}$ értékek helyesek,másrészt $t_n(v)\leq
|
||
t_{n-1}(u)+w(e)$ $G_s$ minden $e=(u,v)$ élére teljesül
|
||
- Mivel $t_n(v)=t_{n-1}(v)$,így $t_{n-1}(v) \leq t_{n-1}(v) + w(e)$
|
||
2) Elégségesség:
|
||
- Tegyük fel,hogy $t_{n-1}(v) \leq t_{n-1}(v) + w(e)$ fennáll
|
||
- Legyen $C$ egy tetszőleges irányított kör $G_s\text{-ben}$
|
||
- Ekkor $C$ $\forall e=(u,v)$ élre a következő egyenlőtlenséget kapjuk:
|
||
\begin{align}
|
||
w(e) \geq t_{n-1}(v) - t_{n-1}(v)=0
|
||
\end{align}
|
||
** Dijkstra algoritmusa
|
||
*** Állítás
|
||
Legyen adott a $G = (V, E)$ irányított gráf, az $s \in V (G)$ csúcs és a
|
||
$w : E \rightarrow \mathbb{R}^+ \cup \{0\}$ nemnegatív hosszfüggvény.
|
||
- Jelölje továbbra is minden $v \in V (G)$ csúcsra $t(v)$ az $s\text{-ből}$ $v\text{-be}$ vezető
|
||
legrövidebb út hosszát.
|
||
- Legyen $K \subseteq V$ egy tetszőleges olyan csúcshalmaz, amire $s \in K$ és $K \neq V$
|
||
- Minden olyan $v \notin K$ csúcsra, amibe vezet él $K\text{-beli}$ csúcsból,
|
||
legyen $t'(v) = \min{\{t(u) + w(e) : e = (u, v), u \in K\}}$.
|
||
- Ha a $v \notin K$ csúcsba nem vezet él $K\text{-beli}$ csúcsból, akkor legyen $t'(v) = \infty$.
|
||
- Legyen $a \notin K$ olyan csúcs, amire $t'(a) = \min\{t'(v) : v \notin K\}$.
|
||
|
||
Ekkor $t\notin (a) = t(a)$.
|
||
*** Az algoritmus
|
||
Tegyük fel,hogy $G$ gráf $s$ csúcsából akarunk legrövidebb utakat keresni. Az
|
||
eljárás során mindenegyes csúcshoz hozzárendelhetünk egy számot,ami azt
|
||
jelzi,hogy az eddig megtalált legrövidebb út összhossza mekkora. Ezt az értéket
|
||
minden csúcsra inicializáljuk $\infty\text{-re}$ (kivéve $s\text{-hez}$,hozzá
|
||
nullát rendelünk)
|
||
|
||
Induljunk ki tehát $s\text{-ből}$ és a belőle kiinduló élek alapján frissítsük
|
||
az egyes csúcsokhoz tartozó legrövidebb utakat. Ezután zárjuk le $s$
|
||
csúcsot,majd folytassuk az eljárást az $s\text{-ből}$ legrövidebb úttal elérhető
|
||
csúccsal. Az eljárást addig futtatjuk,ameddig minden csúcsa le nem lesz zárva.
|
||
|
||
\clearpage
|
||
\begin{thebibliography}{99}
|
||
|
||
\bibitem[1]{kv}
|
||
\bibentry{Katona Gyula – Recski András – Szabó Csaba, }{(2002)}{A számítástudomány alapjai, }{Budapest, }{Typotex Kiadó}{}{}
|
||
|
||
\bibitem[2]{hj}
|
||
\bibentry{Szeszlér Dávid, }{(2019)}{Bevezetés a Számításelméletbe 2 - Ideiglenes egyetemi jegyzet a koronavírus járvány idején zajló távoktatáshoz, }{Budapest, }{\url{http://cs.bme.hu/bsz2/bsz2_jegyzet.pdf}}{}{}
|
||
\end{thebibliography}
|