Enajsta lekcija: Eulerjevi in hamiltonovi graﬁ

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Enajsta lekcija: Eulerjevi in hamiltonovi graﬁ

Avtor: Primož Potočnik

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega sklada za regionalni razvoj in Ministrstva za visoko šolstvo, znanost in tehnologijo. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Društvo matematikov, fizikov in astronomov Slovenije ter DMFA-založništvo.

10.1 Eulerjevi grafi

Sprehod v grafu (ali multigrafu) je enostaven, če vsebuje vsako povezavo grafa največ enkrat. Enostaven sprehod, je eulerjev, če vsebuje vse povezave grafa (vsako natanko enkrat). Multigraf je eulerjev, če vsebuje eulerjev obhod, torej sklenjen sprehod, ki vsebuje vsako povezavo multigrafa natanko enkrat. Eulerjevih multigrafov ni težko prepoznati.

Izrek 10.1
Multigraf $\Gamma$ brez izoliranih točk je eulerjev, če in samo če je povezan in so vse njegove točke sode stopnje.

Dokaz

Naj bo $\Gamma$ graf brez izoliranih točk. Denimo, da je $\Gamma$ eulerjev. Tedaj je očitno povezan, saj vsaka točka leži na eulerjevem sprehodu. (Tu smo uporabili dejstvo, da $\Gamma$ nima izoliranih točk.) Vsakič, ko eulerjev sprehod obišče kako točko, porabi dve povezavi – eno za vstop v točko, drugo za izhod iz nje. Ker eulerjev obhod pri vsaki točki porabi vse povezave, mora biti stopnja vsake točke soda.
Denimo sedaj, da je $\Gamma$ povezan, vsaka njegova točka pa ima sodo stopnjo. Naj bo $W$ najdaljši med enostavnimi obhodi v $\Gamma$ in naj bo $\Gamma'$ multigraf, ki ga dobimo iz $\Gamma$ , če odstranimo vse povezave obhoda $W$ . Če $\Gamma$ ni eulerjev, potem $\Gamma'$ premore kakšno povezavo. Po drugi strani ima vsaka točka multigrafa $\Gamma'$ sodo stopnjo, saj smo stopnjo točke z odstranjevanjem povezavav iz $W$ zmanjšali za sodo število. To pomeni, da $\Gamma'$ premore vsaj en cikel(spomnimo se karakterizacije dreves). Če ta cikel “vrinemo” v sprehod $W$ , dobimo enostaven obhod grafa $\Gamma$ , ki je daljši od $W$ . To pa je protislovje.

10.2 Hamiltonovi grafi

Pot $P$ v grafu $\Gamma$ je hamiltonova, če velja $V(P) = V(\Gamma)$ . Cikel $C$ v grafu $\Gamma$ je hamiltonov, če velja $V(C) = V(\Gamma)$ . Hamiltonova pot in cikel sta torej vpeta pot oziroma vpet cikel. Graf je hamiltonov, če ima hamiltonov cikel.
Znan ni noben preprost, hitro preverljiv potreben in hkrati zadosten pogoj za hamiltonost grafa. Preprost potreben pogoj je podan v naslednji trditvi. Pri njej je uporabljena oznaka $\Omega(\Delta)$ za število povezanih komponent grafa $\Delta$ .

Trditev 10.2
Naj bo $S \subset V(\Gamma)$ neprazna množica točk grafa $\Gamma$ . Če je $\Omega(\Gamma - S) > \mid S \mid$ , potem $\Gamma$ nima hamiltonovega cikla.

Dokaz

Zgornji potrebni pogoj za hamiltonost grafa žal ni tudi zadostni, kot kaže primer Petersenovega grafa. V Petersenovem grafu Pet za vsako neprazno množico $S \subseteq V(Pet)$ velja $\Omega(\Gamma - S) \le \mid S \mid$ , vendar graf vseeno ni hamiltonov.

PETERSENOV GRAF NI HAMILTONOV

Dobrih zadostnih pogojev za hamiltonost grafa ni enostavno najti. Navedimo jih nekaj.

Trditev 10.3
Naj bosta $u$ in $v$ takšnji nesosednji točki grafa $\Gamma$ , da velja $deg(u)+deg(v) \ge \mid V(\Gamma) \mid$ . Če je graf $\Gamma + uv$ hamiltonov, potem je hamiltonov tudi graf $\Gamma$ .

Dokaz

Izrek 10.4 (Dirac)
Če ima graf $\Gamma$ vsaj $3$ točke in velja $\delta(\Gamma) \ge \frac{\mid V(\Gamma) \mid}{2}$ , potem je graf $G$ hamiltonov.

Izrek 10.5 (Ore)
Če za vsak par nesosednjih točk $u$ , $v$ grafa $\Gamma$ velja $deg(u)+ deg(v) \ge \mid V(\Gamma) \mid$ , potem je graf $\Gamma$ hamiltonov.

Dokaz

Naj bodo $\Gamma_1,...,\Gamma_k$ povezane komponente grafa $\Gamma - S$ in naj bo $C = v_0v_2...v_{n-1}v_0$ hamiltonov cikel grafa $\Gamma$ . Dokazati moramo, da je $\mid S \mid \ge k$ . Brez škode za splošnost lahko privzamemo, da $v_{n-1} \in S$ .
Za $i = 1,...,k$ naj bo $n_i$ največji indeks, za katerega je $v_{n_i} \in V(\Gamma_i)$ . Točka $v_{n_i}$ je torej zadnja točka na ciklu $C$ , ki še leži v komponenti $\Gamma_i$ . Naslednja točka, $v_{i+1}$ , je element množice $S$ . Točke $v_{n_1+1},v_{n_2+1},...,v_{n_k+1}$ so torej (paroma različni) elementi množice $S$ , in zato $\mid S \mid \ge k$ .

Dokaz

Naj bo $n = \mid V(\Gamma) \mid$ . Denimo, da je graf $\Gamma + uv$ hamiltonov. Potem obstaja hamiltonova pot $uv_1v_2...v_{n-2}v$ v grafu $\Gamma$ . Naj bo $U$ množica indeksov sosed točke $u$ ter $V$ množica indeksov sosed točke $v$ v grafu $\Gamma$ . Če je za kak $i \in U$ velja $i-1 \in V$ , tedaj je

$v_0v_1...v_{i-1}v_{n-1}v_{n-2}...v_iv_0$

hamiltonov cikel v grafu $\Gamma$ . Predpostavimo torej lahko, da takšnega indeksa $i$ ni. Z drugimi besedami, $V \subseteq \{0,1,...,n-2\} \setminus (U -1)$ , kjer smo z $U -1$ označili množico $\{i-1 : i \in U\}$ . Od tod sledi neenakost $deg(v) = \mid V \mid \le n-1 - \mid U \mid = n-1-deg(u)$ , kar je v prostislovju z našo predpostavko o vsoti stopenj točk $u$ in $v$ .

11 Povezanost in Mengerjev izrek

Točka $v$ grafa $\Gamma$ je prerezna točka, če ima graf $\Gamma - v$ več komponent kot graf $\Gamma$ . Podobno je povezava $e \in E(\Gamma)$ prerezna povezava, če ima graf $\Gamma - e$ več komponent kot graf $\Gamma$ . Prerezni povezavi pravimo tudi most.
Graf $\Gamma$ je $k$ -povezan, če ima vsaj $k + 1$ točk, za vsako množico točk $U \subset V(\Gamma)$ , ki ima manj kot $k$ točk, pa je graf $G - U$ povezan. Če je graf $\Gamma$ $k$ -povezan, je tudi $\ell$ -povezan za vsako število $\ell \le k$ . Največje število $k$ , za katero je graf $\Gamma$ $k$ -povezan, imenujemo povezanost grafa $\Gamma$ in ga označimo s $\kappa(\Gamma)$ .

$\kappa (C_n) = 2$ ,
$\kappa (K_n) = n-1$
$\kappa (K_{m,n}) = min\{m,n\}$ .
Za vsak graf $\Gamma$ je $\kappa(\Gamma) \le \delta (G)$ .

11.1 Mengerjev izrek

Vzemimo $A,B \subseteq V(\Gamma)$ . Poti v grafu $\Gamma$ , ki se začne v točki iz $A$ in konča v točki iz $B$ , pravimo $(A,B)$ -pot. Množica $S \subseteq V(\Gamma)$ je ( $A,B)$ -prerez v $\Gamma$ , če vsaka $(A,B)$ -pot vsebuje kako točko iz $S$ . Če $(A,B)$ -prerez odstranimo iz grafa $\Gamma$ , se preostanek množice $A$ (če ga je kaj) znajde v drugi povezani komponenti kot preostanek množice $B$ . Vsak $(A,B)$ -prerez vsebuje vse točke iz $A \cap B$ .

Izrek 11.1 (Menger)
Naj bo $\Gamma$ graf in $A,B \subseteq V(\Gamma)$ . Največje število disjunktnih $(A,B)$ -poti v $\Gamma$ je enako najmanjši moči $(A,B)$ -prereza v $\Gamma$ .

Množica $S$ loči točki $u,v \in V(\Gamma)$ , če $u$ in $v$ ležita v različnih komponentah grafa $\Gamma - S$ . Velikokrat srečamo Mengerjev izrek v naslednji obliki:

Posledica 11.2
Naj bosta $u,v \in V(\Gamma)$ , $u \ne v$ , nesosednji točki grafa $\Gamma$ . Potem je največje število notranje disjunktnih $(u,v)$ -poti v $\Gamma$ enako najmanjši moči množice, ki loči točki $u$ in $v$ .

Mengerjev izrek nam omogoča tudi drugačen pogled na $k$ -povezanost.

Posledica 11.3 (Opis $k$ -povezanih grafov)
Naj bo $\Gamma$ graf z vsaj $k + 1$ točkami. Graf $\Gamma$ je $k$ -povezan natanko tedaj, ko za vsak par različnih točk $u,v \in V(\Gamma)$ obstaja vsaj $k$ notranje disjunktnih $(u,v)$ -poti.

11.2 $2$ -povezani grafi in bloki

Blok grafa $\Gamma$ je maksimalen povezan podgraf brez prereznih točk (t.j.povezan podgraf brez prereznih točk, ki ni vsebovan v nobenem večjem takšnem podgrafu). Blok grafa je bodisi izolirana točka bodisi prerezna povezava (skupaj s krajiščema) bodisi maksimalen $2$ -povezan podgraf.

Trditev 11.4 (Opis $2$ -povezanih grafov)
Naj bo $\Gamma$ graf z vsaj tremi točkami. Naslednje trditve so enakovredne:

$\Gamma$ je $2$ -povezan.
$\Gamma$ ima en sam blok.
Vsak par točk grafa $\Gamma$ leži na skupnem ciklu (oziroma med vsakim parom točk grafa $\Gamma$ obstaja par notranje disjunktnih poti).
$\delta(\Gamma) \ge 1$ in vsak par povezav grafa $\Gamma$ leži na skupnem ciklu.

Različna bloka grafa imata skupno največ eno točko, ki mora biti prerezna točka grafa. Različni povezavi $e_1,e_2$ grafa pripadata istemu bloku natanko tedaj, ko ležita na skupnem ciklu.
Grafu $\Gamma$ priredimo graf blokov $B(\Gamma)$ takole: Naj bodo $B_1,...,B_k$ bloki grafa $\Gamma$ in $v_1,...,v_p$ prerezne točke v $\Gamma$ . Potem vzamemo