Matematika Diskretua/Grafoak

5. Gaia: Grafoak

5.1 Sarrera

XVIII. mendean Königsberg (gaur Kaliningrado, Errusia) hiritik Pregel ibaia igarotzen zen, eta bi irla osatzen zituen. Ibaiaren ertzak eta irlak zazpi zubiz zeuden loturik. Biztanleek ibilbideak egiten zituzten etxetik atera, zubietatik behin bakarrik pasatu eta etxera bueltatzen saiatzen; baina ez zuten lortzen.

Istorio hura Leonhard Euler-en (1707-1783) eskuetara heldu zen, eta 1736an eman zion soluzioa artikulu batean: ezinezkoa zen.

Euler konturatu zen problemaren soluzioa ez zegoela distantziaren menpe. Orduan, problema aztertzeko, lur-eremu bakoitzari puntu bat eta zubi bakoitzari lerro bat egokitu zien. Hortik aurrera Eulerrek Grafo-Teoriaren oinarrizko kontzeptuak landu zituen. Horrela jaio zen Grafo-Teoria.

Grafo-Teoria elementu-kopuru finitua duten problemak islatzeko erabili da. Lehendabizi, problema grafo baten bidez adierazten da; gero, grafoaren propietateak aztertzen dira; azkenik, problemaren soluzioa ondorioztatzen da.

Grafo-Teoriaren aplikazio asko aurki ditzakegu Informatikan: datuen adierazpena, sareen diseinua, zirkuitu integratuen diseinua...

5.2 Definizioak

5.1 Definizioa. ($V$-ren gaineko) grafo zuzendua $(V,E)$ bikote bat da, non $V$ multzo finitu ez-hutsa den, eta $E\subseteq V\times V$.

$V$ multzoaren elementuei erpin edo adabegi deituko diegu, eta $E$ multzoaren elementuei ertz.

5.2 Adibidea. (Grafo zuzendua) Diagrama honekin adieraziko dugu 5 erpin eta 7 ertz dituen grafo zuzendu bat:

$V=\{x_1,x_2,x_3,x_4,x_5\},$ $E=\{(x_1,x_2),(x_1,x_3),(x_2,x_3),(x_3,x_2),(x_3,x_4),(x_4,x_2),(x_4,x_4)\}.$

5.3 Definizioa. $(a,b)$ ertza izanik, kontzeptu hauek erabiliko ditugu:

• ertza intzidentea da $a$ eta $b$ erpinekin.
• $a$ eta $b$ erpinak elkarren auzokideak dira.
• $a$ erpina ertzaren jatorria da.
• $b$ erpina ertzaren amaiera da.

$a=b$ bada, $(a,a)$ ertzari begizta deituko diogu.

$a$ erpin isolatua da ez badu ertz intzidenterik.

5.4 Definizioa. Ertzen noranzkoak ez badu garrantzirik, hau da, $(a,b)\in E⟹(b,a)\in E,$ $G=(V,E)$ grafoa ez-zuzendua dela esango dugu.

Grafo ez-zuzendu batean ertzak ez-zuzenduak dira: $\{a,b\}=\{(a,b),(b,a)\}$.

Eta $a=b$ bada, begizta bat izango dugu: $\{a,a\}=(a,a)$.

Oharra. Ez bada ezer esaten, grafoa ez-zuzendua izango da.

5.5 Adibidea. (Königsbergeko zubien problemaren grafoa) Hona hemen Königsbergeko zubien problemari dagokion grafoa: lau lur-eremuak erpinak dira, eta zubiak ertzak:

Grafoak $7$ ertz ez-zuzendu ditu: $\{A,B\}$, $\{A,B\}$, $\{A,C\}$, $\{A,C\}$, $\{A,D\}$, $\{B,D\}$ eta $\{C,D\}$.

5.6 Definizioa. $G=(V,E)$ grafo zuzendu bat izanik, grafo ez-zuzendu elkartua $G$ grafotik lortzen da, ertzen noranzkoa kontuan izan gabe. Bi erpinekin intzidenteak diren ertz bat baino gehiago lortzen badira, horietako bat bakarrik hartuko dugu kontuan.

5.7 Adibideak. (Grafo ez-zuzendu elkartua)

1. Hona hemen grafo zuzendu bat eta bere grafo ez-zuzendu elkartua.

   

2. Hau da 5.2 Adibideko grafoaren grafo ez-zuzendu elkartua:

   

5.8 Definizioa. $G=(V,E)$ grafoa multigrafoa da, $a,b\in V$ erpinak badaude bi edo ertz intzidente gehiagorekin:

• $(a,b)$ grafo zuzenduetan.
• $\{a,b\}$ grafo ez-zuzenduetan.

$(a,b)$ ($\{a,b\}$) moduko ertzen kopurua $(a,b)$ ($\{a,b\}$) ertzaren anizkoiztasuna da.

Grafo bat $k$-grafoa da bere ertz batek ere ez badu $k$ baino anizkoiztasun handiagoa.

Grafo bat bakuna da ez bada multigrafoa, hots, bere ertz guztiek $1$ anizkoiztasuna badute.

5.9 Adibideak.

1. Hona hemen bi multigraforen adibideak. Lehena $2$-grafo zuzendua da, eta bigarrena $3$-grafo zuzendua.

   

2. Königsbergeko zubien problemaren grafoa $2$-grafo ez-zuzendua da.

3. Grafo ez-zuzendu elkartuaren adibideko grafoak bakunak dira.

5.3 Erpinen graduak

5.10 Definizioa. Izan bedi $G=(V,E)$ grafo zuzendua, eta $a\in V$.

• $a$ erpinaren irteera-gradua $a$-tik ateratzen diren ertzen kopurua da, $d^{+}(a)$ adierazten da: $d^{+}(a)=\text{card}\{b/(a,b)\in E\}.$
• $a$ erpinaren sarrera-gradua $a$-ra iristen diren ertzen kopurua da, $d^{-}(a)$ adierazten da: $d^{-}(a)=\text{card}\{b/(b,a)\in E\}.$

$d^{+}(a)$ eta $d^{-}(a)$ $a$ erpinaren graduerdi deitzen dira, eta $a$ erpinaren graduerdien baturari $a$-ren gradu deituko diogu, $d(a)$ adierazten da: $d(a)=d^{+}(a)+d^{-}(a).$

5.11 Adibidea. Grafo zuzenduaren adibidean, $\begin{array}{ccccc}{d}^{+}(x_1)=2,& d^{+}(x_2)=1,& d^{+}(x_3)=2,& d^{+}(x_4)=2,& d^{+}(x_5)=0.\\ d^{-}(x_1)=0,& d^{-}(x_2)=3,& d^{-}(x_3)=2,& d^{-}(x_4)=2,& d^{-}(x_5)=0.\\ d(x_1)=2,& d(x_2)=4,& d(x_3)=4,& d(x_4)=4,& d(x_5)=0.\end{array}$

5.12 Definizioa. $G=(V,E)$ grafo ez-zuzendua eta $a\in V$ izanik, $a$ erpinaren gradua $a$-rekin intzidenteak diren ertzen kopurua da, eta $d(a)$ adieraziko dugu.

Kasu honetan, $\{a,a\}$ begizta $a$-rekin intzidenteak diren bi ertz bezala kontatzen da.

$a$ erpina zintzilikatua da $d(a)=1$ denean.

5.13 Adibideak.

1. Königsbergeko zubien problemaren grafoan, $d(A)=5,d(B)=d(C)=d(D)=3.$
2. Grafo ez-zuzendu elkartuaren 2. adibideko grafoan, $d(x_1)=2,d(x_2)=d(x_3)=3,d(x_4)=4,d(x_5)=0.$

5.14 Teorema. [2m] Izan bedi $G=(V,E)$ $m$ ertz dituen grafo ez-zuzendua. Orduan, $\sum _{x\in V}d(x)=2m.$

Froga.

(Ideia: $\{a,b\}$ ertz bakoitzak unitate bat eransten dio $d(a)$ graduari, eta beste bat $d(b)$ graduari, eta, hortaz, bi unitate $\sum _{x\in V}d(x)$ baturari, hau da, erpinen graduen batura kalkulatzean, bi aldiz kontatzen ditugu grafoaren ertzak.)

Froga $m$ ertz kopuruaren gaineko indukzioaz egingo dugu.

$m=1$ bada, $G$ grafoak $e=\{a,b\}$ ertz bakarra du.

$a\ne b$ bada, $\{\begin{array}{cc}d(a)=1,& \\ d(b)=1,& \\ d(y)=0,& a\ne y\ne b\text{ bada.}\end{array}$ $$ $a=b$ bada, $\{\begin{array}{cc}d(a)=2,& \\ d(y)=0,& y\ne a\text{ bada.}\end{array}$

Bi kasuetan, $\sum _{x\in V}d(x)=2=2m.$

Demagun, orain, teorema betetzen dela $m=p$ denean, eta har dezagun $m=p+1$.

Izan bedi $G$ grafoaren $e=\{a,b\}\in E$ ertz bat eta izan bedi $G$ grafotik $e$ ertza kentzean geratzen den $G^{\prime }$ grafoa. $G^{\prime }$ grafoaren ertzen kopurua $m^{\prime }$ bada, eta $d^{\prime }(x)$ bada $x$ erpinaren gradua $G^{\prime }$ grafoan, orduan, $m^{\prime }=p$ izango da. Eta, indukzio-hipotesiaren arabera, $\sum _{x\in V}{d}^{\prime }(x)=2m^{\prime }=2p.$

Horrez gain,

$a\ne b$ bada, $\{\begin{array}{cc}d(a)=d^{\prime }(a)+1,& \\ d(b)=d^{\prime }(b)+1,& \\ d(y)=d^{\prime }(y),& a\ne y\ne b\text{ bada.}\end{array}$ $$ Eta $a=b$ bada, $\{\begin{array}{cc}d(a)=d^{\prime }(a)+2,& \\ d(y)=d^{\prime }(y),& y\ne a\text{ bada.}\end{array}$

Bi kasuetan, $\sum _{x\in V}d(x)=\sum _{x\in V}{d}^{\prime }(x)+2=2p+2=2(p+1)=2m.$ $◻$ $◼$ $◻$

5.15 Adibideak.

1. Königsbergeko zubien problemaren grafoan, $n=4$, $m=7$, $d(A)+d(B)+d(C)+d(D)=5+3+3+3=14=2\cdot 7.$
2. Grafo ez-zuzendu elkartuaren 2. adibideko grafoan, $n=5$, $m=6$, $d(x_1)+d(x_2)+d(x_3)+d(x_4)+d(x_5)=2+3+3+4+0=12=2\cdot 6.$

5.16 Korolarioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua. Gradu bakoitiko erpinen kopurua bikoitia da.

Froga.

Izan bedi $V=\{x_1,\dots ,x_n\}$ eta demagun badaudela gradu bikoitiko $p$ erpin eta gradu bakoitiko $q$ erpin ($p+q=n$).

$\begin{array}{cc}d(x_i)=2k_i,& i=1,\dots ,p;\\ d(x_i)=2k_i+1,& i=p+1,\dots ,p+q.\end{array}$

Orduan, $2m=\sum _{x\in V}d(x)=\sum _{i=1}^{p}d(x_i)+\sum _{i=p+1}^{p+q}d(x_i)=\sum _{i=1}^p(2k_i)+\sum _{i=p+1}^{p+q}(2k_i+1)=2\sum _{i=1}^{p+q}{k}_i+q.$

Hortaz, $q=2(m-\sum _{i=1}^{p+q}{k}_i).$ $◻$ $◼$ $◻$

5.17 Adibideak.

1. Königsbergeko zubien problemaren grafoan gradu bakoitiko 4 erpin daude ($A$, $B$, $C$ eta $D$).
2. Grafo ez-zuzendu elkartuaren 2. adibideko grafoan, gradu bakoitiko 2 erpin daude ($x_2$ eta $x_3$).

5.18 Definizioa. Grafo ez-zuzendu bat erregular deitzen da erpin guztiek gradu bera badute; eta $k$-erregular deitzen da erpin guztiek $k$ gradua badute.

5.19 Adibidea. (Grafo 3-erregularra) Grafo hau $3$-erregularra da:

5.4 Ibilaldiak grafo batean

5.20 Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua. $x,y\in V$ bi erpin badira, $x-y$ ibilaldia $x$ erpinean hasi eta $y$ erpinean bukatzen den erpinen eta ertzen segida txandakatu finitu bat da:

$$x=x_0,e_1,x_1,e_2,x_2,e_3,\dots ,e_{p-1},x_{p-1},e_p,x_p=y,$$ $e_i=\{x_{i-1},x_i\}$ ertza izanik, $i=1,\dots ,p$.

Ibilaldiaren luzera ertzen kopurua da, $p$. Eta $p=0$ bada, $x=y$ izango da eta ibilaldi nabaria izango dugu.

$x=y$ eta $p\ge 1$ badira, ibilaldi itxia da; bestela, ibilaldi irekia da.

Oharra. Grafoa bakuna denean, ibilaldia adieraztean ertzak ez ditugu idatziko.

5.21 Adibidea. [ibilaldiak] [elkartua]-2 Adibideko grafoan, $x_1,x_3,x_2$ ibilaldi irekia da, $2$ luzerako $x_1-x_2$ ibilaldia hain zuzen: $x_1,\{x_1,x_3\},x_3,\{x_3,x_2\},x_2.$

Beste hau, ordea, $6$ luzerako ibilaldi itxia da: $x_1,x_3,x_2,x_4,x_3,x_2,x_1.$

5.22 Definizioa. Izan bedi $x-y$ ibilaldi bat $G=(V,E)$ grafo ez-zuzenduan,

• Ertzik ez bada errepikatzen, $x-y$ ibilaldiari kate deituko diogu. Katea itxia denean, $x-x$ ibilaldi itxiari zirkuitu deituko diogu.
• Erpinik ez bada errepikatzen, $x-y$ ibilaldiari bide deituko diogu. Bidea itxia denean, $x-x$ ibilaldi itxiari ziklo deituko diogu.

Hitzarmena. Zirkuituetan, gutxienez ertz bat existitzen dela pentsatuko dugu; eta bat bakarrik dagoenean, zirkuitua begizta izango da. Zikloetan, gutxienez hiru ertz desberdin daudela pentsatuko dugu.

5.23 Adibidea. Grafo ez-zuzendu elkartuaren 2. adibideko grafoan,

$x_1,x_2,x_3$ katea eta bidea da;

$x_1,x_3,x_2,x_4,x_3$ katea da, baina ez da bidea;

$x_1,x_2,x_3,x_1$ zirkuitua eta zikloa da.

Grafo zuzenduetan zuzendu adjektiboa erabiliko dugu: ibilaldi zuzenduak, bide zuzenduak, ziklo zuzenduak, etab.

5.24 Teorema. Izan bedi $G=(V,E)$ grafo ez-zuzendua eta izan bitez $x,y\in V$, $x\ne y$. Orduan,

$x-y$ ibilaldi bat badago baldin eta soilik baldin $x-y$ bide bat badago.

Froga.

Demagun $x-y$ ibilaldiren bat dagoela. $x$ eta $y$-ren arteko ibilaldi guztien artean, har dezagun luzera txikieneko ibilaldia:

$$x=x_0,x_1,\dots ,x_{k-1},x_k=y.$$

Ibilaldi hori ez bada bidea, $\mathrm{\exists }p,q/0\le p<q\le k$ eta $x_p=x_q$. Baina, orduan,

$$x=x_0,x_1,\dots ,x_{p-1},x_q,x_{q+1},\dots ,x_k=y$$

ere $x$ eta $y$-ren arteko beste ibilaldi bat da, eta $k$ baino luzera txikiagokoa da.

Azken ibilaldi hori ez balitz bidea, berdin egingo genuke: errepikatzen den erpinaren bi agerpenen arteko zatia kendu eta luzera txikiagoko ibilaldi berri bat lortuko genuke. Horrela segi daiteke erpinak errepikatzen ez diren arte, hots, bide bat lortu arte.

Elkarrekikoa berehalakoa da; izan ere, bide bat ibilaldi bat da. $◻$ $◼$ $◻$

5.25 Definizioa. $G=(V,E)$ grafo ez-zuzendua konexua da edozein $x$ eta $y$ bi erpin desberdinetarako $x-y$ ibilaldi bat badago.

$G=(V,E)$ grafo zuzendua konexu da grafo ez-zuzendu elkartua konexua bada.

Grafo bat ez bada konexua, diskonexua da.

Aurreko teoremaren arabera, horrek esan nahi du grafo ez-zuzendua konexua dela edozein $x$ eta $y$ bi erpin desberdinetarako $x-y$ bide bat badago.

5.26 Adibidea. Grafo 3-erregularraren adibideko grafoa konexua da.

[elkartua]-1 Adibideko grafoak konexuak dira.

Grafo zuzenduaren adibideko grafoa eta [elkartua]-2 Adibideko grafo elkartua diskonexuak dira, ez dagoelako, esaterako, $x_1-x_5$ biderik.

5.27 Teorema. [baliokidetasuna] Izan bedi $G=(V,E)$ grafo ez-zuzendua; $ℛ$ erlazioa, $xℛy⟺x-y\text{ bide bat badago},$ baliokidetasun-erlazioa da $V$ multzoaren gainean.

Froga.

1. $ℛ$ bihurkorra da. Hau frogatu behar dugu: $(\mathrm{\forall }x\in V)xℛx$.

   $\mathrm{\forall }x\in V$, $x-x$ ibilaldi nabaria dago; hortaz, $xℛx$.

2. $ℛ$ simetrikoa da. Hau frogatu behar dugu: $(\mathrm{\forall }x,y\in V)xℛy⟹yℛx.$

   $x,y\in V$ badira, $$\begin{array}{c}xℛy⟹x=x_0,x_1,\dots ,x_{p-1},x_p=y\text{ ibilaldia badago }⟹\\ ⟹y=x_p,x_{p-1},\dots ,x_1,x_0=x\text{ ibilaldia badago }⟹yℛx.\end{array}$$

3. $ℛ$ iragankorra da. Hau frogatu behar dugu: $(\mathrm{\forall }x,y,z\in V)xℛy\wedge yℛz⟹xℛz.$

   $x,y,z\in V$ badira, $$\begin{array}{c}xℛy\wedge yℛz⟹\\ ⟹x=x_0,\dots ,x_p=y\wedge y=y_0,\dots ,y_q=z\text{ ibilaldiak badadaude }⟹\\ ⟹x=x_0,\dots ,x_p=y=y_0,y_1,\dots ,y_q=z\text{ ibilaldia badago }⟹xℛz.\end{array}$$ $◻$ $◼$ $◻$

5.28 Definizioa. [baliokidetasuna] Teoreman definitutako baliokidetasun-erlazioak erpinen $V$ multzoa $V_1,\dots ,V_q$ baliokidetasun-klasetan banatzen du. $G_1=(V_1,E_1)$, $\dots$, $G_q=(V_q,E_q)$ grafoei, non $E_i$, $i=1,\dots ,q$, $V_i$ multzoaren erpinekin intzidenteak diren ertzen multzoak diren, $G$ grafoaren osagai konexu deituko diegu.

$G$ grafoaren osagai konexuen kopurua $\kappa (G)$ adieraziko dugu.

Ondorioa. $G$ grafoa konexua da baldin eta soilik baldin $\kappa (G)=1$ bada.

5.29 Adibidea. [elkartua]-2 Adibideko grafoak 2 osagai konexu ditu, $\kappa (G)=2$:

$G_1=(V_1,E_1)$, non

$V_1=\{x_1,x_2,x_3,x_4\},E_1=\{\{x_1,x_2\},\{x_1,x_3\},\{x_2,x_3\},\{x_2,x_4\},\{x_3,x_4\},\{x_4,x_4\}\}\text{ diren;}$

eta $G_2=(V_2,E_2)$, non

$V_2=\{x_5\},E_2=\mathrm{\varnothing }\text{ diren}.$

5.5 Grafo baten auzokidetasun-matrizea

5.30 Definizioa. Izan bedi $G=(V,E)$ grafo bakun ez-zuzendua, begiztarik gabea eta $n$ erpinekin, non $V=\{x_1,\dots ,x_n\}$ den. $G$ grafoari dagokion auzokidetasun-matrizea honela definituko dugu: $A=(a_{ij})$, $i,j=1,\mathrm{...},n$

$a_{ij}=\{\begin{array}{cc}1,& x_i,x_j\text{ auzokideak badira,}\\ 0,& x_i,x_j\text{ ez badira auzokideak.}\end{array}$

$A$ matrizea simetrikoa da eta diagonal nagusiko elementu guztiak $0$ dira. $G$ grafoaren egituraren informazio osoa du, eta $G$ adierazteko erabil dezakegu.

$x_i\in V$ erpin bakoitzeko hau betetzen da: $d(x_i)=\sum _{j=1}^n{a}_{ij}=\sum _{j=1}^n{a}_{ji}.$

5.31 Adibideak. [matrizea]

1. [elkartua]-2 Adibideko grafoaren auzokidetasun-matrizea (begizta kenduta) hau da: $A=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 1& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right).$

2. Hona hemen grafo bakun ez-zuzendu bat, begiztarik gabea:

   

   grafoaren auzokidetasun-matrizea (erpinak ordena alfabetikoan hartuta) hau da: $A=\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 0\end{array}\right).$

   Bosgarren errenkadako edo zutabeko elementuen batura 2 da; hau da, $d(e)=2$.

5.32 Teorema. Izan bitez $G=(V,E)$ grafo bakun ez-zuzendua, begiztarik gabea, $V=\{x_1,\dots ,x_n\}$ erpinak eta $A$ $G$ grafoari dagokion auzokidetasun-matrizea. $A^p$ matrizearen $(i,j)$ elementua $p$ luzerako $x_i-x_j$ ibilaldien kopurua da.

Froga.

$p$-ren gaineko indukzioaren bidez frogatuko dugu.

$p=1$ bada, $A^p=A$ izango da; eta $1$ luzerako $x_i-x_j$ ibilaldien kopurua hau da:

$\{\begin{array}{cc}1,& (x_i,x_j)\in E\text{ bada,}\\ 0,& (x_i,x_j)\in ̸E\text{ bada;}\end{array}$

hau da, $A$ matrizearen $(i,j)$ elementua.

Demagun teorema betetzen dela $p=k$ denean, hau da, $A^k$ matrizearen $(i,j)$ elementua $k$ luzerako $x_i-x_j$ ibilaldien kopurua dela; ikus dezagun $p=k+1$ denean ere betetzen dela. Hau da, $A^{k+1}$ matrizearen $(i,j)$ elementua $k+1$ luzerako $x_i-x_j$ ibilaldien kopurua dela frogatu behar dugu.

Izan bitez $A^k=(b_{ij})$ eta $A^{k+1}=(c_{ij})$.

Orduan, $A^{k+1}=A^{k}A$ denez, hau beteko da: $c_{ij}=\sum _{l=1}^n{b}_{il}{a}_{lj}.$

$k+1$ luzerako $x_i-x_j$ ibilaldi bakoitza $k$ luzerako $x_i-x_l$ ibilaldi batek eta, jarraian, $\{x_l,x_j\}$ ertz batek osatuko dute, non $x_l$ erpina ($l\in \{1,\dots ,n\}$) edozein erpin den.

$\{x_l,x_j\}\in E$ bada, $a_{lj}=1$ izango da $A$ matrizean; beraz, $k+1$ luzerako eta $x_i=y_0,y_1,\dots ,y_k=x_l,y_{k+1}=x_j$ itxurako $x_i-x_j$ ibilaldien kopurua $k$ luzerako $x_i-x_l$ ibilaldien kopurua izango da, hots, $b_{il}=b_{il}{a}_{lj}$.

Ordea, $\{x_l,x_j\}\in ̸E$ bada, $a_{lj}=0$ izango da $A$ matrizean; beraz, $k+1$ luzerako eta $x_i=y_0,y_1,\dots ,y_k=x_l,y_{k+1}=x_j$ itxurako ibilaldien kopurua $0=b_{il}{a}_{lj}$ izango da.

Hortaz, $k+1$ luzerako $x_i-x_j$ ibilaldi guztien kopurua hau da: $\sum _{l=1}^n{b}_{il}{a}_{lj}=c_{ij}.$ $◻$ $◼$ $◻$

5.33 Adibidea.

[matrizea]-2 Adibideko grafoaren auzokidetasun-matrizerako hau dugu: $A^3=\left(\begin{array}{ccccc}0& 1& 0& 3& 0\\ 1& 0& 1& 0& 2\\ 0& 1& 0& 3& 0\\ 3& 0& 3& 0& 4\\ 0& 2& 0& 4& 0\end{array}\right)$

Ez dago $3$ luzerako $a-c$ ibilaldirik $a$ eta $c$ artean; badaude $3$ luzerako lau ibilaldi $d$ eta $e$ artean: $d,a,d,e;d,c,d,e;d,e,d,e;\text{ eta }d,e,b,e.$

5.6 Azpigrafoak. Grafo osagarria

5.34 Definizioa. Izan bedi $G=(V,E)$ grafo bat (zuzendua edo ez). $G_1=(V_1,E_1)$ grafoa $G$ grafoaren azpigrafo bat da bi baldintza hauek betetzen baditu:

• $\mathrm{\varnothing }\ne V_1\subseteq V$ eta
• $E_1\subseteq E$ eta $E_1$ multzoaren ertz bakoitzak intzidente izan behar du $V_1$ multzoaren erpinekin soilik.

5.35 Adibidea. [azpigrafoak] [matrizea]-2 Adibideko grafoa izanik, grafo hauek bere azpigrafoak dira:

$G_1$

$G_2$

$G_3$

5.36 Definizioa. $G_1=(V_1,E_1)$ grafoa $G=(V,E)$ grafoaren azpigrafoa bada eta $V_1=V$ bada, $G_1$ grafoa $G$ grafoaren azpigrafo sortzailea dela esango dugu.

Ertzen azpimultzo bakoitzeko azpigrafo sortzaile bat lortuko dugu. Beraz, $G=(V,E)$ grafoan $|E|=m$ bada, $2^m$ azpigrafo sortzaile izango ditu.

5.37 Adibidea. [azpigrafoak] Adibidean, $G$ grafoaren $G_2$ azpigrafo sortzailea da; baina, $G_1$ eta $G_3$ ez dira azpigrafo sortzaileak.

$G$ grafoak $2^4=16$ azpigrafo sortzaile ditu.

5.38 Definizioa. Izan bitez $G=(V,E)$ grafo bat (zuzendua edo ez) eta $\mathrm{\varnothing }\ne U\subset V$ multzo bat. $U$ multzoak induzitutako $G$ grafoaren azpigrafo deituko diogu honela definitutako grafoari:

$U$ multzoak $G$ grafoan honela definitzen duen azpigrafoari azpigrafo induzitu deituko diogu:

• erpinen multzoa $U$ da eta
• ertzen multzoa $E\cap (U\times U)$ da (hots, $U$ multzoaren erpinekin soilik intzidenteak diren $E$ multzoaren ertzak).

Azpigrafo induzitua $<U>$ adieraziko dugu.

5.39 Adibidea. [azpigrafoak] Adibidean, $G_3$ azpigrafo induzitua da, $V_3=\{a,b,c,e\}$ multzoak induzitutakoa hain zuzen. $G_3=<V_3>.$

$G_1$ ez da $V_1=\{a,b,c,d\}$ multzoak induzitutako azpigrafoa, $\{a,d\}$ ertza ez dago eta.

Ikus ditzagun, orain, beste bi azpigrafo mota, erpin bat edo ertz bat kentzean sortutakoak.

5.40 Definizioa. Izan bedi $G=(V,E)$ grafo bat (zuzendua edo ez).

• $x\in V$ izanik, $G-x$ idatziko dugu $G-x=(V_1,E_1)$ azpigrafoa adierazteko, non:

  • $V_1=V\setminus \{x\}$ den eta

  • $E_1$ multzoan $E$ multzoaren ertz guztiak dauden, $x$ erpinarekin intzidenteak direnak izan ezik.

  Hortaz, $G-x=<V_1>$ grafo induzitua dugu.

• $e\in E$ izanik, $G-e$ idatziko dugu $G-e=(V_1,E_1)$ azpigrafoa adierazteko, non:

  • $V_1=V$ den eta

  • $E_1=E\setminus \{e\}$ den.

5.41 Adibidea. [ken] [azpigrafoak] Adibidean, $G_3=G-d$ eta $G_2=G-\{d,e\}$ dira.

Grafo baten grafo osagarria definitu ahal izateko grafo osotuaren kontzeptua behar dugu.

5.42 Definizioa. Izan bedi $V=\{x_1,\dots ,x_n\}$ erpinen multzoa. $V$ multzoaren gaineko grafo osotua grafo bakun, ez-zuzendu eta begiztarik gabea da, non $(\mathrm{\forall }x,y\in V)x\ne y⟹\{x,y\}\text{ ertza ezistitzen den}.$

$n$ erpineko grafo osotua $K_n$ adieraziko dugu.

Ohar gaitezen $K_n$ grafoak $n$ erpin eta $\left(\begin{array}{c}n\\ 2\end{array}\right)$ ertz dituela, eta erpin bakoitzaren gradua $n-1$ dela.

5.43 Adibideak.

$K_4$

$K_5$

5.44 Definizioa. Izan bedi $G=(V,E)$ grafo bakuna, ez-zuzendua, begiztarik gabea eta $n$ erpin dituena, $V=\{x_1,\dots ,x_n\}$ izanik. $G$ grafoaren grafo osagarria $K_n$ grafo osotuaren $\bar{G}=(V,\bar{E})$ azpigrafoa da, non $\bar{E}$ multzoan $E$ multzoan ez dauden $K_n$ grafo osotuaren ertzak dauden.

$G=K_n$ bada, $\bar{G}$ grafoak $n$ erpin eta $0$ ertz izango ditu; grafo nulu deitzen da.

5.45 Adibidea. $G$ grafo hau bada:

$\bar{G}$ grafo osagarria beste hau izango da:

5.46 Definizioa. $G=(V,E)$ zatibiko grafoa da grafo bakuna, ez-zuzendua eta begiztarik gabea bada eta

• $V_1,V_2$ badaude, non $V_1\cup V_2=V$ eta $V_1\cap V_2=\mathrm{\varnothing }$ diren eta
• $G$ grafoaren $\{x,y\}$ ertz bakoitzean $x\in V_1$ eta $y\in V_2$ badira.

Horrez gain,

($\mathrm{\forall }x\in V_1$, $\mathrm{\forall }y\in V_2$) $\{x,y\}$ ertza badago,

$G$ zatibiko grafo osotua da, eta $K_{n_1,n_2}$ idatziko dugu, $|V_1|=n_1$ eta $|V_2|=n_2$ izanik.

5.47 Adibideak.

1. Grafo hau zatibiko grafo da (ez osotua):

   

2. Grafo hau $K_{2,3}$ zatibiko grafo osotua da:

   

5.7 Grafoen arteko isomorfismoak

5.48 Definizioa. Izan bitez $G_1=(V_1,E_1)$ eta $G_2=(V_2,E_2)$ bi grafo ez-zuzendu. Grafoen arteko $f:V_1⟶V_2$ funtzioa isomorfismoa da hau betetzen badu:

• $f$ bijektiboa da eta
• $(\mathrm{\forall }x,y\in V_1)\{x,y\}\in E_1\text{ baldin eta soilik baldin }\{f(x),f(y)\}\in E_2$.

Horrelako funtzio bat badago, $G_1$ eta $G_2$ grafo isomorfoak dira eta $G_1\cong G_2$ idatziko dugu.

Grafoen arteko isomorfiak baliokidetasun-erlazio bat definitzen du grafoen multzoan.

$G_1$ eta $G_2$ grafo isomorfoak badira, funtsean berdinak dira:

• erpinen kopuru bera dute;
• ertzen kopuru bera dute;
• gradu bera duten erpinen kopuru bera dute;
• zikloen kopuru bera dute;
• etab.

5.49 Adibideak. [isomorfismo]

1. Har ditzagun grafo hauek:

   $G_1=(V_1,E_1)G_2=(V_2,E_2)$

   

   
   

   
   

   
   

   
   

   
   

   $f:V_1⟶V_2$ funtzioa, non $f(a)=v,f(b)=y,f(c)=w,f(d)=z,f(e)=x$ diren, isomorfismoa da. Hau da, $G_1\cong G_2$.

   $\begin{array}{c}\{a,c\}\leftrightarrow \{f(a),f(c)\}=\{v,w\}\\ \{c,e\}\leftrightarrow \{f(c),f(e)\}=\{w,x\}\\ \{e,b\}\leftrightarrow \{f(e),f(b)\}=\{x,y\}\\ \{b,d\}\leftrightarrow \{f(b),f(d)\}=\{y,z\}\\ \{d,a\}\leftrightarrow \{f(d),f(a)\}=\{z,v\}\end{array}$

2. Ikus ditzagun, orain, grafo hauek:

   $G_3{G}_4$

   • 

   • 

   Bi grafoek 6na erpin eta 9na ertz dituzte. Baina ez dira isomorfoak.

   $d(a)=d(d)=2,d(b)=d(e)=3,d(c)=d(f)=4,$ $d(u)=d(w)=d(y)=2,d(v)=d(x)=d(z)=4;$ gradu bereko erpinen kopuruak desberdinak dira.

5.8 Kate eta zirkuitu eulertarrak

5.50 Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua eta erpin isolaturik gabea. $G$ grafoaren ertz guztiak erabiltzen dituen zirkuituari zirkuitu eulertar deituko diogu.

$G$ grafoaren ertz guztiak erabiltzen dituen kate irekiari kate eulertar deituko diogu.

$G$ grafoa eulertarra da zirkuitu eulertar bat badauka.

5.51 Adibideak.

1. [isomorfismo]-2 Adibideko $G_4$ grafoan zirkuitu eulertar hau aurki dezakegu: $$u,v,z,x,v,w,x,y,z,u.$$ Zirkuitu eulertarra da, grafoaren ertz guztiak zeharkatzen dituelako, bakoitza behin bakarrik, eta hasitako erpinean amaitzen delako. Beraz, grafo eulertarra da.
2. [isomorfismo]-2 Adibideko $G_3$ grafoan kate eulertar hau aurki dezakegu: $$b,a,f,b,c,d,e,c,f,e.$$ Kate eulertarra da, grafoaren ertz guztiak zeharkatzen dituelako, bakoitza behin bakarrik, eta ez delako hasitako erpinean amaitzen. Ezin da, ordea, zirkuitu eulertar bat ere aurkitu.

5.52 Teorema. [zieul] Izan bedi $G=(V,E)$ grafo ez-zuzendua eta erpin isolaturik gabea. Orduan,

$G$ eulertarra da $⟺$ $G$ konexua bada eta $G$ grafoaren erpin guztiek gradu bikoitia badute.

Froga.

$⟹$: Demagun $G$ eulertarra dela, hots, $C$ zirkuitu eulertar bat duela.

Ikus dezagun $G$ konexua dela: $G$ grafoak erpin isolaturik ez duenez, $V$ multzoaren erpin guztiak behin gutxienez agertuko dira $C$ zirkuituan. $x,y\in V$ bi erpin desberdin izanik, $x$ erpinean hasten den eta $y$ erpinean bukatzen den $C$ zirkuituaren zatia $x-y$ ibilaldi bat da. Beraz, $G$ konexua da.

Ikus dezagun, orain, erpin guztiek gradu bikoitia dutela. Izan bedi $x$ edozein erpin. $C$ zirkuitua $x$ erpinera ertz batetik “heltzen” denean, $x$ erpinetik ertz desberdin batetik “aterako” da. Beraz, $C$ zirkuituak $x$ erpinarekin intzidenteak diren bi ertz desberdin, edo begizta berri bat, erabiltzen ditu. Bi kasuetan, $C$ zirkuitua $x$ erpinetik pasatzen den bakoitzean, bi unitate eransten dio $x$ erpinaren graduari; hortaz, $d(x)$ bikoitia da.

$⟸$: Demagun $G$ konexua dela eta $G$ grafoaren erpin guztiek gradu bikoitia dutela. $G$ eulertarra dela frogatu behar dugu. $G$ grafoaren ertzen $m$ kopuruaren gaineko indukzioz egingo dugu.

$m=1$ bada, $G$ grafoa hau da:

eta zirkuitu eulertarra nabaria da.

Pentsa dezagun, $m<p$ denean, zirkuitu eulertarra eraiki dezakegula. $m=p$ denean, zirkuitu eulertarra eraiki ahal izango dugula frogatuko dugu.

Hasteko, $x\in V$ erpin bat izanik, $x$ erpina duen zirkuitu bat dagoela frogatuko dugu. Izan bedi $$x=y_0,f_1,y_1,\dots ,f_k,y_k$$ $x$ erpinean hasten den ibilaldirik luzeena, $y_i$ erpinak eta $f_i$ ertzak izanik, $i\in \{1,\cdots ,k\}$.

1. $i\in \{1,\cdots ,k\}$ baterako $y_i=x$ bada, $$x=y_0,f_1,\cdots ,f_i,y_i=x$$ $x$ erpina duen ibilaldi itxi bat da.
2. $i\in \{1,\cdots ,k\}$ guztietarako $y_i\ne x$ bada, $y_k$ erpina hartuko dugu.
   • $y_k=y_i$ bada $i\in \{1,\cdots ,k-1\}$ baterako, $y_k$ erpina ibilaldiaren tartean eta amaieran agertuko da. Tartean agertzen den bakoitzean, graduari $2$ erantsiko dio, eta amaieran agertzean $1$ erantsiko dio; beraz, guztira gradu bakoitia emango du. Hipotesiz, erpin guztiek gradu bikoitia dutenez, ibilaldian erabili ez den ertz bat, gutxienez, intzidentea da $y_k$ erpinarekin. Horrek esan nahi du ibilaldia luza dezakegula, esan dugunaren kontra, hau da, ibilaldia luzeena izatearen kontra.
   • $y_k\ne y_i$ bada $i\in \{1,\cdots ,k-1\}$ guztietarako, $y_k$ erpina ibilaldiaren amaieran bakarrik agertuko da. $y_k$ erpinaren gradua bikoitia denez eta $y_k$ erpinarekin intzidentea den ertz bat bakarrik erabili dugunez, ibilaldian ez dagoen beste ertz bat egon behar da. Berriro ere, horrek esan nahi du ibilaldia luzatu ahal genukeela, ibilaldia luzeena izatearen kontra.

Horrela, $x$ erpinetik pasatzen den ibilaldi itxi bat dagoela frogatu dugu. [ibilbide] Teoremaren arabera, ibilaldi bat badago, bide bat dago; beraz, $x$ erpinetik pasatzen den $C$ bide itxi (ziklo) bat dago. Eta ziklo hori $x$ erpinetik pasatzen den zirkuitua da, erpinak ez badira errepikatzen ertzak ere ezin direlako errepikatu.

Zirkuitu horretan grafoaren ertz guztiak badaude, zirkuitu eulertarra da.

$G$ grafoaren ertz guztiak ez badaude, $G$ grafotik $C$ zirkuitua ezabatuko dugu, eta, horrekin batera, isolaturik gera daitezkeen erpinak ere bai. Horrela, $G^{\prime }$ grafo bat lortuko dugu, zeinak $\{G_1,G_2,\dots ,G_l\}$ osagai konexuak izan ditzakeen. Osagai bakoitzak erpin komun bat izango du $C$ zirkuituarekin. Horrez gain, osagai konexu bakoitza $p$ baino ertz gutxiago dituen grafo konexua da, eta erpin guztiek gradu bikoitia izanik; hortaz, indukzio-hipotesiaren arabera, osagai konexu bakoitzerako zirkuitu eulertar bat izango dugu.

$G$ grafoaren zirkuitu eulertarra lortzeko, $C$ zirkuitutik ibiliko gara, edozein erpinetatik hasita. Osagai konexuren batekin komunean duen erpin batera heltzean, $C$ zirkuitutik aterako gara eta osagai konexuaren zirkuitu eulertarra ibiliko dugu erpin komunera itzuli arte; osagaitik atera eta $C$ zirkuitutik segituko dugu. Horrela, osagai konexu guztietatik pasatu eta gero, $C$ zirkuitura itzuliko gara eta hasi garen erpinean bukatuko dugu. Hori izango da $G$ grafoaren zirkuitu eulertarra.

Prozesu honek bukaera izango du, ertzen kopurua finitua delako. $◻$ $◼$ $◻$

5.53 Adibideak.

1. Irudiko grafoan, $b$ erpinetik pasatzen den $C$ zirkuitua hartuko dugu: $C=bcgfb.$ Gero, $G$ grafoari $C$ zirkuituaren ertzak eta isolaturik geratu den $b$ erpina kenduko dizkiogu; $G_1$, $G_2$ eta $G_3$ osagai konexuek osatzen duten $G^{\prime }$ grafoa geratuko zaigu.

   

   $G$ grafoaren zirkuitu eulertarra lortzeko, $b$ erpinetik (esaterako) hasiko gara: $bc{G}_{1}cg{G}_{2}gf{G}_{3}fb;$ edo erpin guztiak idatziz: $bc\underset{\_}{adc}g\underset{\_}{ijg}f\underset{\_}{ehf}b.$

2. Irudiko $G$ graforako, bi graduko $d$ eta $e$ erpinetatik pasatzen den $C$ zirkuitu bat hartuko dugu: $C=dheagd$. Gero, $G$ grafoari $C$ zirkuituaren ertzak eta isolaturik geratu diren $d$ eta $e$ erpinak kenduko dizkiogu; $G^{\prime }$ lortuko dugu. $G^{\prime }$ grafoan, $C^{\prime }=bchfb$ zirkuitua hartuko dugu. Orain, $G^{\prime }$ grafoari $C^{\prime }$ zirkuitua kenduz gero (ez da erpin isolaturik geratzen), $G^{″}$ grafoa lortuko dugu. $G^{″}$ grafoan erpin guztiek bi gradua dute, eta erraz aurki dezakegu zirkuitu eulertar bat: $E^{″}=afcgbha$.

   $G^{\prime }$ grafoaren zirkuitu eulertarra eratuko dugu. $C^{\prime }$ zirkuituaren edozein erpin hartuko dugu, esaterako, $b$. $b$ erpina $G^{″}$ grafoan dagoenez, $G^{″}$ grafoan sartuko gara eta bere zirkuitu eulertarra ibiliko dugu, $b$ erpinean bukatuz. Orain, $C^{\prime }$ zirkuitutik segituko dugu. Horrela zirkuitu eulertar hau lortuko dugu: $E^{\prime }=b\underset{\_}{hafcgb}chfb$.

   $G$ grafoaren $E$ zirkuitu eulertarra eratzeko, $C$ zirkuituaren edozein erpinetan hasiko gara, adibidez, $d$ erpinean. $C$ zirkuitutik ibiliko gara $G^{\prime }$ grafoarekin erpin komun bat aurkitu arte, adibidez, $h$. $h$ erpinetik $G^{\prime }$ grafoan sartuko gara eta $E^{\prime }$ zirkuitu eulertarra berridatziko dugu: $E^{\prime }=hafcgbchfbh$. Horrela, $G^{\prime }$ grafo osoa ibili dugu, eta $C$ zirkuitura aterako gara $h$ erpinetik, eta hortik segituko dugu $d$ erpineraino. Bukaeran zirkuitu eulertar hau osatu dugu: $E=dh\underset{\_}{afcgb\underset{\_}{chfb}h}eagd$.

   

5.54 Korolarioa. Izan bedi $G=(V,E)$ grafo ez-zuzendu eta erpin isolaturik gabe bat. Orduan,

$G$ grafoak kate eulertar bat du $⟺$ $G$ konexua bada eta zehazki bi erpinek gradu bakoitia badute.

Froga.

$⟹$: Demagun $G$ grafoak $R$ kate eulertar bat duela (ez zirkuitua): $a-b$, $a\ne b$ izanik.

Izan bedi $G^{\prime }$ grafoa $G$ grafoari $\{a,b\}$ ertza eranstean sortzen den grafoa. Orduan, $R\cup \{a,b\}$ $G^{\prime }$ grafoaren zirkuitu eulertarra da. [zieul] Teorema $G^{\prime }$ grafoari aplikatuz gero, $G^{\prime }$ grafoaren erpin guztiek gradu bikoitia izango dute. $x\in V$ izanik, $d(x)$ bada $x$ erpinaren gradua $G$ grafoan, eta $d^{\prime }(x)$ bada $x$ erpinaren gradua $G^{\prime }$ grafoan,

$\begin{array}{cc}d(x)=d^{\prime }(x),& x\ne a,x\ne b\text{ bada},\\ d(a)=d^{\prime }(a)-1,\\ d(b)=d^{\prime }(b)-1.\end{array}$

$\mathrm{\forall }x\in V,$ $d^{\prime }(x)$ bikoitia denez, $G$ grafoak gradu bakoitiko bi erpin bakarrik izango ditu, $a$ eta $b$.

$⟸$ : Demagun $G$ konexua dela eta zehazki bi erpinek gradu bakoitia dutela, $a\ne b$.

Izan bedi $G^{\prime }$ grafoa $G$ grafoari $\{a,b\}$ ertza eranstean sortzen den grafoa. $G^{\prime }$ konexua da eta $G^{\prime }$ grafoaren erpin guztiek gradu bikoitia badute. [zieul] Teorema aplikatuz, $G^{\prime }$ grafoak $C$ zirkuitu eulertar bat dauka. $C$ zirkuitutik $\{a,b\}$ ertza ezabatuz, kate eulertar bat lortuko dugu $G$ graforako. Kate eulertar hori gradu bakoitiko erpin batean hasiko da eta bestean bukatuko da. $◻$ $◼$ $◻$

5.55 Adibideak.

1. 

   grafoan, $K=acbadc$ kate eulertar bat da. Ez dago zirkuitu eulertarrik.

2. Königsbergeko zubien problemaren grafoan, lau erpinek gradu bakoitia dute: $$d(A)=5,d(B)=d(C)=d(D)=3;$$ beraz, ezin da kate eulertarrik, ezta zirkuitu eulertarrik ere, osatu. Ondorioz, ezin da halako ibilaldirik egin zubiak behin bakarrik pasatzen.

Aurreko kontzeptuak eta emaitzak grafo zuzenduetara zabal ditzakegu.

5.56 Definizioa. Izan bedi $G=(V,E)$ grafo zuzendu eta erpin isolaturik gabea. $G$ grafoaren ertz guztiak erabiltzen dituen zirkuitu zuzenduari zirkuitu eulertar zuzendu deituko diogu.

$G$ grafoa eulertar zuzendua da zirkuitu eulertar zuzendu bat badauka.

5.57 Teorema. Izan bedi $G=(V,E)$ grafo zuzendu eta erpin isolaturik gabea. Orduan,

$G$ grafoak zirkuitu eulertar zuzendua du $⟺$ $G$ grafo konexua bada eta $x\in V$ erpin guztietarako $d^{+}(x)=d^{-}(x)$ betetzen bada.

5.9 Bide eta ziklo hamiltondarrak

5.58 Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua, $|V|=n\ge 3$ izanik. $G$ grafoaren erpin guztiak dituen ziklo bati ziklo hamiltondar deituko diogu.

$G$ grafoaren erpin guztiak dituen bide ireki bati bide hamiltondar deituko diogu.

$G$ grafoa hamiltondarra da ziklo hamiltondar bat badu.

Oharrak.

1. Ziklo hamiltondar batetik ertz bat ezabatuz gero, bide hamiltondar bat lortuko dugu.
2. Grafo batek bide hamiltondar bat badu, konexua da.
3. Zirkuitu eta kate eulertarrekin ez bezala, ez dago baldintza nahikorik, ezta beharrezkorik ere, ziklo edo bide hamiltondarren bat dagoela ziurtatzeko. Teorema batzuek baldintza beharrezkoak ematen dituzte, eta beste batzuek baldintza nahikoak.

5.59 Adibidea.

$G$ grafoan, $$a,b,c,d,e,f,g,h,i$$

bide hamiltondarra da. Ikus dezagun ea $G$ grafoan ziklo hamiltondarren bat dagoen.

$G$ grafoak bederatzi erpin dituenez, ziklo hamiltondar bat balego, bederatzi ertz izango lituzke. Has gaitezen $b$ erpinean eta saia gaitezen ziklo hamiltondar bat eratzen. Grafoaren simetria kontuan izango dugu. $b$ erpinetik $c$ erpinera joango gara; gero, edo $d$ edo $i$ erpinetara joan gaitezke. $d$ erpinera bagoaz, $\{c,i\}$ ertza ezin da zikloan sartu, ezin garelako itzuli $c$ erpinera. Orain, edo $e$ edo $i$ erpinetara joan gaitezke. $e$ erpinera bagoaz, $\{d,i\}$ ertza ezin da zikloan sartu; beraz, $i$ erpinera heltzen garenean ezin izango dugu segitu. Baina $i$ erpinera bagoaz, $\{e,d\}$ ertza ezin da zikloan sartu; beraz, $e$ erpinera heltzen garenean ezin izango dugu segitu.

Ondorioz, grafo horrek ez du ziklo hamiltondarrik.

Adibide horri begira, iradokizun batzuk eman ditzakegu $G=(V,E)$ grafoan ziklo hamiltondar bat aurkitzeko.

• $G$ hamiltondarra bada, $x\in V$ erpin guztietarako $d(x)\ge 2$ da.
• $a\in V$ eta $d(a)=2$ bada, $a$ erpinarekin intzidenteak diren ertzek $G$ grafoaren edozein ziklo hamiltondarretan agertu behar dute.
• $a\in V$ eta $d(a)>2$ bada, $G$ grafoaren edozein ziklo hamiltondar eraikitzeko, $a$ erpinetik behin pasatu eta gero, $a$ erpinarekin intzidenteak diren eta erabili ez ditugun ertzak baztertuko ditugu.
• $G$ grafoaren edozein ziklo hamiltondar eraikitzean, ezin izango dugu ziklo bat osatu $G$ grafoaren azpigrafo baterako, ez bada $G$ grafoaren erpin guztiak hartzen dituela.

Ikus ditzagun grafo batek bide edo ziklo hamiltondar bat izateko baldintza nahikoak ematen dituzten teorema batzuk.

5.60 Teorema. Izan bedi $G=(V,E)$ grafoa, begiztarik gabea eta $n\ge 3$ erpin dituena, $$\mathrm{\forall }x,y\in V(x\ne y)d(x)+d(y)\ge n-1$$

betetzen badu, $G$ grafoak bide hamiltondarra izango du.

5.61 Korolarioa. Izan bedi $G=(V,E)$ grafoa, begiztarik gabea eta $n\ge 3$ erpin dituena, $$\mathrm{\forall }x\in Vd(x)\ge \frac{n-1}{2}$$

betetzen badu, $G$ grafoak bide hamiltondarra izango du.

5.62 Adibidea. Zazpi azterketa zazpi egunetan antolatu nahi ditugu, irakasle batek bi azterketa jarraian ez ditzan izan. Ezein irakaslek ez du lau baino azterketa gehiago. Ikusiko dugu beti dela posible azterketak antolatzea.

Har dezagun $G$ grafoa, non erpinak azterketak diren; bi erpinen artean ertz bat marraztuko dugu bi azterketak irakasle desberdinenak badira. Orduan, erpin bakoitzaren gradua gutxienez $3$ ($7-4=3$) da.

Horrela definitutako $G$ grafoak $\mathrm{\forall }x\in Vd(x)\ge \frac{7-1}{2}=3$ betetzen du; beraz, bide hamiltondar bat badu.

5.63 Teorema. Izan bedi $G=(V,E)$ grafoa, begiztarik gabe, eta $n\ge 3$ erpin dituena, $$\mathrm{\forall }x,y\in V(x,y\text{ ez-auzokideak})d(x)+d(y)\ge n$$

betetzen badu, $G$ grafo hamiltondarra izango da.

5.64 Korolarioa. Izan bedi $G=(V,E)$ grafoa, begiztarik gabea eta $n\ge 3$ erpin dituena, $$\mathrm{\forall }x\in Vd(x)\ge \frac{n}{2}$$

betetzen badu, $G$ grafo hamiltondarra izango da.

5.65 Adibidea. Hogei laguneko talde batean, bakoitzak gutxienez hamar lagun ezagutzen ditu. Ikus dezagun mahai biribil baten inguruan eser daitezkeela, eta ziurtatu mahaikide bakoitzak bi lagun ezagun izango dituela alde banatan.

$G$ grafoan erpinak lagunak izango dira; eta elkar ezagutzen duten lagunen artean ertzak marraztuko ditugu.

Grafo horretan erpin bakoitzaren gradua $d(x)\ge \frac{20}{2}=10$ izango da. Hortaz, $G$ grafo hamiltondarra izango da.

Baldintza horietan mahaiaren inguruan esertzeko era bakoitza ziklo hamiltondar bat izango da.

Ikus ditzagun grafo batek bide edo ziklo hamiltondar bat izateko baldintza beharrezkoak ematen dituzten teorema batzuk. Lehenengoa zatibiko grafo bati dagokio.

5.66 Teorema. $G=(V,E)$ zatibiko grafoa izanik, non $V=V_1\dot{\cup }{V}_2$ den, $G$ grafoa hamiltondarra bada, $|V_1|=|V_2|$ izango da.

Aurreko teoremak esaten digu, $G=(V,E)$ zatibiko grafoa izanik, non $V=V_1\dot{\cup }{V}_2$ den, $|V_1|\ne |V_2|$ bada, $G$ grafoa ez dela hamiltondarra.

Adibide honek frogabidearen ideia emango digu.

5.67 Adibidea. [zatiziham] Har dezagun $G$ grafo hau:

Grafo hori zatibikoa da. Hori ikusteko erpinak bi multzotan banatuko ditugu honela: $a$ erpina $x$ izendatuko dugu; gero, $x$ erpinarekin auzokide diren erpin guztiak ($b$, $c$ eta $d$) $y$ izendatuko ditugu. Ondoren, $y$ erpinekin auzokide diren eta izendatu gabe dauden erpinak $x$ izendatuko ditugu; eta horrela ondoz ondo eginez gero, grafoa honela geratuko da:

Orain, $x$ erpin guztiak alde batera eta $y$ erpin guztiak beste aldera eramanez gero, grafoa zatibikoa dela nabarmen geratuko da:

$G$ grafoaren erpinak bi multzotan banatuko ditugu: $$V=V_1\dot{\cup }{V}_2,V_1=\{a,e,g,i\},V_2=\{b,c,d,f,h,j\}.$$ $|V_1|\ne |V_2|$ denez, $G$ grafoa ez da hamiltondarra.

Bide hamiltondar bat izanez gero, bidean txandakaturik agertuko lirateke bosna aldiz $x$ eta $y$ letrak; baina, $x$ letra lau aldiz eta $y$ letra sei aldiz dauzkagu. Hortaz, horrelako bide bat osatzea ezinezkoa da. Ondorioz, grafoak ez du bide hamiltondarrik.

Idazkera. $G=(V,E)$ grafoa izanik, eta $V^{\prime }\subset V$ erpinen azpimultzo bat, $G-V^{\prime }$ idatziko dugu $G-V^{\prime }=(V_1,E_1)$ grafoa adierazteko, non $V_1=V\setminus V^{\prime }$ den eta $E_1$ multzoan $E$ multzoaren ertzak dauden, $V^{\prime }$ multzoaren erpinekin intzidenteak direnak izan ezik.

5.68 Teorema. $G=(V,E)$ grafo hamiltondarra bada, edozein $V^{\prime }\subset V$ azpimultzotarako, $\mathrm{\varnothing }\ne V^{\prime }\ne V$ izanik, $$\kappa (G-V^{\prime })\le |V^{\prime }|.$$

5.69 Korolarioa. $G=(V,E)$ grafoa izanik, $V^{\prime }\subset V$ azpimultzo bat badago, $\mathrm{\varnothing }\ne V^{\prime }\ne V$ izanik, non $$\kappa (G-V^{\prime })>|V^{\prime }|$$ betetzen den, $G$ grafoa ez da hamiltondarra izango.

5.70 Adibidea. [zatiziham] Adibideko grafoan, $x$ izendatutako erpinak kenduz gero, $y$ izendatutako erpinak isolaturik geratuko lirateke. Beraz, $\kappa (G-V^{\prime })=6$ eta $|V^{\prime }|=4$ dira. Ondorioz, $G$ grafoa ez da hamiltondarra.

5.10 Zuhaitzak

5.10.1 Sarrera

Zuhaitz bat grafo-mota berezi bat da. Gustav Robert Kirchhoff-ek (1824-1887) erabili zituen lehenengo aldiz elektronikan. Beranduago, Arthur Cayley-k (1821-1895) berriro definitu eta garatu zituen Kimika arloan (1857).

Zuhaitz berezi batzuk oso garrantzitsuak dira datuen egiturak eta ordenamenduak aztertzeko, kodeketa-teorian eta optimizazio-problema batzuen soluzioan.

5.10.2 Definizioak eta propietateak

5.71 Definizioa. Izan bedi $T=(V,E)$ grafo ez-zuzendua eta begiztarik gabea. $T$ grafoa zuhaitza da konexua bada eta ez badu ziklorik.

Grafo baten erpin guztiak dituen eta zuhaitz den edozein azpigrafo sortzaileri zuhaitz sortzaile deituko diogu.

5.72 Adibidea. [zuhaitza]

$G_1$ grafoa $G_2$ grafoaren zuhaitz sortzailea da.

5.73 Teorema. [bidebakarra] $a$ eta $b$ zuhaitz baten bi erpin desberdin badira, $a-b$ bide bakarra egongo da.

Froga.

Izan bitez $T=(V,E)$ zuhaitz bat eta $a,b\in V$, $a\ne b$.

$T$ konexua denez, gutxienez $a-b$ bide bat dago: $C(a=x_0,x_1,\dots ,x_p=b)$.

Demagun beste $a-b$ bide bat dagoela, $C^{\prime }$.

Izan bedi $x_t$ erpina $C^{\prime }$ bidean ez dagoen $C$ bidearen lehen erpina ($1\le t\le p-1$); eta izan bedi $x_s$ erpina bi bideetan dagoen $C$ bidearen hurrengo erpina ($t<s\le p$).

Orduan, $C$ eta $C^{\prime }$ bideen zatiek, $x_{t-1}$ eta $x_s$ erpinen artean, ziklo bat osatuko lukete, $T$ zuhaitza izatearen kontra doana. $◻$ $◼$ $◻$

5.74 Lema. [ertziklo] Izan bedi $G=(V,E)$ grafo ez-zuzendua, begiztarik gabea eta konexua, eta izan bedi $e\in E$ $G$ grafoaren ertz bat. Orduan, $$e\text{ ertza ziklo batean dago}⟺G-e\text{ grafoa konexua bada}.$$

Froga.

Izan bedi $e=\{a,b\}$.

$⟹$: Demagun $e$ ertza $C$ ziklo batean dagoela: $C=a,b,x_1,x_2,\dots ,x_p,a$.

$G-e$ grafoa konexua dela frogatzeko, edozein $x,y\in V$ bi erpin desberdin izanik, $G-e$ grafoan $x-y$ bide bat dagoela frogatu behar dugu.

Izan bitez $x,y\in V$ desberdinak. $G$ grafoa konexua denez, $x-y$ bide bat dago $G$ grafoan ($P$).

$P$ bideak ez badu $e$ ertza, $P$ bidea da $G-e$ grafoan.

$P$ bideak $e$ ertza badu, $P:x,y_1,\dots ,y_t,a,b,z_1,\dots ,z_q,y$ izango da.

Orduan, Orduan, $P$ bidea eta $C$ zikloa $e$ ertzean lotuz eta $e$ ertza bietatik kenduz, $x-y$ bide bat lortuko dugu: $$(P-e)\cup (C-e):x,y_1,\dots ,y_t,a,x_p,\dots ,x_1,b,z_1,\dots ,z_q,y.$$

$x-y$ bide bat da $G-e$ grafoan.

$⟸$: Demagun $G-e$ grafoa konexua dela.

$G-e$ grafoan $a-b$ bide bat dago, $P:a,x_1,\dots ,x_p,b$. Hortaz, $P\cup e:a,x_1,\dots ,x_p,b,a$ ziklo bat da $G$ grafoan. $◻$ $◼$ $◻$

5.75 Teorema. [zuhasor] Izan bedi $G$ grafo ez-zuzendu bat. $$G\text{ konexua da}⟺G\text{ grafoak zuhaitz sortzailea badu}.$$

Froga.

$⟸$: Demagun $G$ grafoak $T$ zuhaitz sortzaile bat duela.

$G$ grafoaren erpinen $x,y$ bikote bakoitzeko $x-y$ bide bat dago $T$ zuhaitzean. $T$ zuhaitzaren ertzak $G$ grafoaren ertzak direnez, bide hori $G$ grafoan egongo da eta, beraz, $G$ grafoa konexua da.

$⟹$: Demagun $G$ konexua dela. Eraiki dezagun zuhaitz sortzaile bat.

$G$ ez bada zuhaitza, begizta guztiak ezabatuko ditugu. Geratzen den $G_1$ azpigrafoa konexua eta begiztarik gabea da eta $G$ grafoaren erpin guztiak ditu. Zuhaitza balitz, $G$ grafoaren zuhaitz sortzailea izango litzateke. Ez bada zuhaitza, gutxienez $C_1$ ziklo bat dauka. Orduan, $C_1$ ziklotik $e_1$ ertz bat ezabatuko dugu; izan bedi $G_2=G_1-e_1$ grafoa. [ertziklo] Lemaren arabera, $G_2$ grafoa konexua eta begiztarik gabea da eta $G$ grafoaren erpin guztiak ditu. Zuhaitza balitz, $G$ grafoaren zuhaitz sortzailea izango litzateke. Ez bada zuhaitza, gutxienez $C_2$ ziklo bat dauka. Orduan, $C_2$ ziklotik $e_2$ ertz bat ezabatuko dugu; izan bedi $G_3=G_2-e_2$ grafoa. Zuhaitza balitz, $G$ grafoaren zuhaitz sortzailea izango litzateke. Ez bada zuhaitza, prozesu horrekin segituko genuke urrats kopuru finitu aldiz, $G$ grafoaren zuhaitz sortzaile bat lortu arte. $◻$ $◼$ $◻$

5.76 Adibidea.[sortzailea]

• 

• 

$G_5$ grafoa $G$ grafoaren zuhaitz sortzaile bat da.

5.77 Lema. [azpizuhaitzak] Izan bedi $T=(V,E)$ zuhaitz bat eta izan bedi $e$ $T$ zuhaitzaren edozein ertz. Orduan, $T-e$ ez-konexua da eta zuhaitzak diren bi osagai konexu ditu.

Froga.

Izan bedi $e=\{a,b\}$.

Demagun $T-e$ konexua dela. Orduan, $T-e$ grafoan $a-b$ bide bat dago: $C$.

Hortaz, $T$ grafoan $a-b$ bi bide daude, $C$ bidea eta $e$ ertza; hori $T$ zuhaitza izatearen kontra doa, zuhaitz batean bi erpin lotzen dituen bide bakarra baitago ([bidebakarra] Teorema).

Hortaz, $T-e$ ez-konexua da eta bi osagai konexu ditu, $$V_1=\{a\}\cup \{x\in V/a-x\text{ bide bat dago }T-e\text{ grafoan}\}$$

eta

$$V_2=\{b\}\cup \{x\in V/b-x\text{ bide bat dago }T-e\text{ grafoan}\}$$ erpinen multzoek induzitutako azpigrafoak hain zuzen.

Osagai konexu horiek zuhaitzak dira, begizta edo ziklo bat izanez gero, $T$ grafoan ere egongo litzatekeelako. $◻$ $◼$ $◻$

5.78 Teorema. [m+1] Izan bedi $T$$n$ erpin eta $m$ ertz dituen zuhaitz bat. Orduan, $n=m+1.$

Froga.

Ertzen $m$ kopuruaren gaineko indukzioz frogatuko dugu.

$m=0$ bada, zuhaitza erpin isolatu batek osatuko du. Kasu horretan, $n=1=m+1$ beteko da.

Demagun teorema betetzen dela $m\le k$ denean, eta izan bedi $m=k+1$.

$T$ zuhaitzetik ertz bat ezabatuz gero, [azpizuhaitzak] Lemaren arabera, $T_1$ eta $T_2$ bi azpizuhaitz lortuko ditugu. Izan bitez $n_1,n_2$ eta $m_1,m_2$ $T_1$ eta $T_2$ azpizuhaitzen erpinen eta ertzen kopuruak, hurrenez hurren.

Orduan, $n=n_1+n_2$ eta $m=m_1+m_2+1=k+1$ izango dira. $0\le m_1\le k$ eta $0\le m_2\le k$ direnez, indukzio-hipotesiaren arabera, $n_1=m_1+1$ eta $n_2=m_2+1$ beteko dira. Hortaz,

$n=n_1+n_2=(m_1+1)+(m_2+1)=(m_1+m_2+1)+1=m+1.$ $◻$ $◼$ $◻$

5.79 Adibidea. [zuhaitza] Adibideko $G_1$ zuhaitzean, $n=6$ eta $m=5$ dira.

5.80 Teorema. Izan bedi $T=(V,E)$ $n$ erpin dituen zuhaitz bat. $n\ge 2$ bada, $T$ zuhaitzak gutxienez bi erpin zintzilikatu izango ditu.

Froga.

Izan bedi $m$ $T$ zuhaitzaren ertzen kopurua. [m+1] Teoremaren arabera, $m=n-1$ beteko da. Hortaz, Hortaz, [2m] Teoremaren arabera, ondoko hau beteko da: $$\sum _{x\in V}d(x)=2(n-1).$$

$T$ zuhaitza konexua denez, $d(x)\ge 1$ izango da $x\in V$ guztietarako.

$T$ zuhaitzak ez balu erpin zintzilikaturik, $d(x)\ge 2$ beteko litzateke $x\in V$ guztietarako eta, beraz, $2(n-1)=\sum _{x\in V}d(x)\ge 2n$ ere beteko litzateke, eta hori ezinezkoa da.

$T$ zuhaitzak $a$ erpin zintzilikatu bakarra izango balu, $d(a)=1$ eta $d(x)\ge 2$ beteko litzateke $x\in V$ guztietarako, $x\ne a$ izanik. Orduan, $2(n-1)=\sum _{x\in V}d(x)\ge 1+2(n-1)$ beteko litzateke, eta hori ere ezinezkoa da.

Ondorioz, $T$ zuhaitzak gutxienez bi erpin zintzilikatu izango ditu. $◻$ $◼$ $◻$

5.81 Adibidea. [zuhaitza] Adibideko $G_1$ grafoak 4 erpin zintzilikatu ditu.

[sortzailea] Adibideko $G_5$ grafoak 3 erpin zintzilikatu ditu.

5.82 Teorema. [defbalio] Izan bedi $G=(V,E)$ $n$ erpin eta $m$ ertz dituen grafo ez-zuzendua eta begiztarik gabea. Hiru baieztapen hauek baliokideak dira:

1. $G$ zuhaitza da.
2. $G$ grafoak ez du ziklorik, eta $n=m+1$.
3. $G$ grafoa konexua da, eta $n=m+1$.

Froga.

i) $⟹$ ii):

Demagun i) betetzen dela, hots, $G$ zuhaitza dela.

[m+1] Teorema erabiliz, $n=m+1$ izango dugu.

$G$ grafoak ez du ziklorik zuhaitza delako.

ii) $⟹$ iii):

Demagun ii) betetzen dela.

Izan bedi $\kappa (G)=r$ eta izan bitez $G_1=(V_1,E_1)$, $\dots$, $G_r=(V_r,E_r)$ $G$ grafoaren osagai konexuak (zuhaitzak direnak ziklorik ez dutelako).

$i=1,\dots ,r$ bakoitzeko, $v_i\in V_i$ erpin bat aukeratuko dugu eta $G$ grafoari $r-1$ ertz hauek erantsiko dizkiogu, $\{v_1,v_2\}$, $\{v_2,v_3\}$, …, $\{v_{r-1},v_r\}$. Horrela lortuko dugun $G^{\prime }=(V,E^{\prime })$ grafoa zuhaitza da, eta $n$ erpin eta $m+r-1$ ertz ditu.

[m+1] Teoremaren arabera, $n=(m+r-1)+1=m+r$ eta, ii) hipotesiz $n=m+1$ denez, $r=1$ lortuko dugu; hau da, $G$ konexua da.

iii) $⟹$ i):

Demagun iii) betetzen dela.

[zuhasor] Teoremaren arabera, $G$ grafoak $T=(V,E^{\prime })$ zuhaitz sortzaile bat du. Izan bedi $m^{\prime }$ $T$ zuhaitzaren ertzen kopurua. [m+1] Teoremaren arabera, $m^{\prime }=n+1$ izango da; baina iii) hipotesiz, $n+1=m$ da. Hortaz, $m^{\prime }=m$ da, eta hortik $G=T$ aterako dugu. $◻$ $◼$ $◻$

5.10.3 Zuhaitz errodunak. Zuhaitz bitarrak

5.83 Definizioa. Izan bedi $G$ grafo zuzendua. $G$ grafoa zuhaitz zuzendua dela esango dugu $G$ grafoaren grafo ez-zuzendu elkartua zuhaitza bada.

5.84 Adibidea. [zuhazuzen]

5.85 Definizioa. $G$ zuhaitz zuzendua bada, $G$ zuhaitza zuhaitz erroduna dela esango dugu $r$ erpin bakarra badago (erro deituko duguna), non $d^{-}(r)=0$ den eta gainerako $x$ erpinetarako $d^{-}(x)=1$ den. Bestela, zuhaitz erro gabea dela esango dugu.

5.86 Adibidea. [errozuha1]

$d^{-}(a)=d^{-}(b)=d^{-}(c)=0$; $d^{-}(e)=d^{-}(d)=2$.

Ezkerreko zuhaitz erroduna geziak irudikatu gabe adieraz daiteke, ertzen noranzkoa goitik behera doala onartzen badugu.

5.87 Definizioa. Izan bedi $T$ zuhaitz erroduna:

$d^{+}(v)=0$ betetzen duen edozein $v$ erpini hosto edo bukaerako erpin deituko diogu. Gainerako erpinei barne-erpin edo adarkatze-adabegi deituko diegu.

$v$ erpina erroarekin lotzen duen bide bakarraren luzera $l$ bada, $v$ erpina $l$ mailan dagoela edo $l$ maila-zenbakia duela esango dugu.

$v_1$ eta $v_2$ erpinak izanik, $v_1$ erpinetik $v_2$ erpinera bide bat badago, $v_1$ erpina $v_2$ erpinaren arbasoa edo $v_2$ erpina $v_1$ erpinaren ondorengoa dela esango dugu. Bidea $1$ luzerakoa bada, $v_1$ erpina $v_2$ erpinaren gurasoa edo $v_2$ erpina $v_1$ erpinaren umea dela esango dugu.

Bi erpinek guraso bera badute, senideak direla esango dugu.

$v$ erpinak eta bere ondorengo guztiek (baldin baditu) induzitutako azpigrafoari $v$ erpineko azpizuhaitz deituko diogu.

5.88 Adibidea. [errozuha2] Zuhaitz honetan, $f$, $g$, $i$, $j$ eta $k$ hostoak dira. $a$ erpina $k$ erpinaren arbasoa da. $k$ erpina $a$ erpinaren ondorengoa da. $d$ erpina $h$ erpinaren gurasoa da. $h$ erpina $d$ erpinaren umea da. $c$ eta $d$ senideak dira.

• 

• 

5.89 Definizioa. Izan bedi $T=(V,E)$ zuhaitz erroduna. $T$ zuhaitzaren hostoen maila-zenbaki handienari $T$ zuhaitzaren altuera deituko diogu.

5.90 Adibidea. [altuera]

zuhaitzak $a=5$ altuera du.

5.91 Definizioa. Izan bedi $T=(V,E)$ zuhaitz erroduna, eta $p$ zenbaki oso positiboa.

Esango dugu $T$ zuhaitz $p$-tarra dela $d^{+}(x)\le p$ bada $x\in V$ guztietarako. ($p=2$ bada, zuhaitz bitarra da).

5.92 Adibidea. [zuhaptar]

5.93 Definizioa. $T=(V,E)$ zuhaitz erroduna zuhaitz $p$-tar osotua da $d^{+}(x)=0$ edo $d^{+}(x)=p$ bada $x\in V$ guztietarako. ($p=2$ bada, zuhaitz bitar osotua da).

5.94 Adibidea. [zuhaptaroso1]

5.95 Teorema. [zenbakia] Izan bedi $T=(V,E)$ $n$ erpin dituen zuhaitz $p$-tar osotua, $i$ barne-erpinak eta $h$ hostoak izanik. Orduan,

1. $n=pi+1$ da.
2. $h=(p-1)i+1$ da.
3. $i=\frac{h-1}{p-1}=\frac{n-1}{p}$ da.

Froga.

(i) Izan bedi $a$ $T$ zuhaitzaren altuera.

$k=0,1,\dots ,a$ bakoitzeko, $n_k$ eta $i_k$ $k$ mailan dauden erpin guztien kopuruak eta barne-erpinen kopuruak izango dira, hurrenez hurren. Orduan, $n_0=1$ da eta $n_k=i_{k-1}p,k=1,\dots ,a.$

Hortaz, $n=\sum _{k=0}^a{n}_k=1+\sum _{k=1}^a{i}_{k-1}p=1+p\sum _{k=1}^a{i}_{k-1}=1+pi.$

(ii) $pi+1=n=i+h$ da. Beraz, $h=pi-i+1=(p-1)i+1$ izango da.

(iii) (i) eta (ii) ataletatik ondorioztatuko dugu. $◻$ $◼$ $◻$

5.96 Adibidea. [zuhaptaroso2] [zuhaptaroso1] Adibideko zuhaitz 3-tar osotuan, $p=3$, $h=7$, $i=3$ eta $n=10$ dira. Eta, beraz, (i) $10=3\cdot 3+1$, (ii) $7=2\cdot 3+1$ eta (iii) $3=\frac{6}{2}=\frac{9}{3}$ betetzen dira.

5.97 Adibidea. [zuhaptaroso3] Bost bikotek mus txapelketa batean parte hartzen dute, non bikote bat kanporatzen den partida bat galtzen duenean. Txapelketa $5$ hosto dituen zuhaitz bitar osotu baten bidez adieraz daiteke:

Txapeldunak izendatzeko jokatu behar diren partida-kopurua barne-erpinen kopurua da. [zenbakia] Teoremaren arabera, $i=\frac{h-1}{p-1}=\frac{5-1}{2-1}=4$.

Oro har, bikoteen kopurua $h$ bada, partiden kopurua $i=\frac{h-1}{p-1}=h-1$ izango da.

5.98 Adibidea. [zuhaptaroso4] Laborategi bateko ordenagailuak $4$ irteera dituen hormako entxufe batean konektatu behar ditugu. Konexioak $4$ irteerako luzapen-kableen bidez egingo ditugu. $7$ luzapen-kable baditugu, zenbat ordenagailu konekta ditzakegu?

Hormako entxufea zuhaitz 4-tar osotu baten erroa bezala har dezakegu. Kable bakoitza barne-erpina izango da, eta ordenagailu bakoitza hosto bat. Barne-erpinen kopurua, beraz, $i=7+1$ da (luzapen-kableak eta hormako entxufea).

[zenbakia] Teoremaren arabera, ordenagailuen kopurua $h=(p-1)i+1=(4-1)8+1=25$ da.

5.99 Definizioa. Izan bedi $T$ $a$ altuerako zuhaitz bat. $T$ zuhaitz orekatua dela esango dugu hosto bakoitzaren maila-zenbakia $a$ edo $a-1$ denean.

5.100 Adibideak. [zuhaoreka1]

1. [altuera] Adibideko zuhaitza ez da orekatua, hosto bat 2 mailan eta beste bi 5 mailan dauzkalako.
2. Zuhaitz hau $a=3$ altuerako zuhaitz orekatua da:

   

5.101 Adibidea. [zuhaoreka2] [zuhaptaroso3] Adibideko zuhaitzak orekatua izan behar du, txapelketa ahalik eta zuzenena izan dadin. Ez bada orekatua, bikoteren batek aukera bat baino gehiago izango du hurrengo fasera pasatzeko partida gutxiago jokatuz.

Txapelketaren zuhaitza hau bada

$a=3$ altuerako zuhaitz orekatua da. Bikote batek, txapeldun izateko, bi edo hiru partida jokatu beharko ditu.

Txapelketaren zuhaitza, aldiz, hau bada

ez da orekatua. Irabazteko, $b$ eta $c$ bikoteek 4 partida jokatu beharko dituzte, $d$ bikoteak 3 partida, $a$ bikoteak 2 partida eta $e$ bikoteak partida 1 bakarrik.

Idazkera. $x\in ℝ$ emanik, $\lceil x\rceil$ ($x$-ren sabaia) $x$ baino handiagoa edo berdina den zenbaki oso txikiena da.

5.102 Adibidea. [sabaia] $\lceil 3.2\rceil =4$, $\lceil -5.7\rceil =-5$, $\lceil 8\rceil =8$.

5.103 Teorema. [sabaiteo] Izan bedi $T=(V,E)$ $a$ altuerako eta $h$ hostoko zuhaitz $p$-tar osotua ($p>1$). Orduan, $h\le p^a$ eta $a\ge \lceil {\log }_{p}h\rceil$ beteko dira.

Froga.

$h\le p^a$ $a$-ren gaineko indukzioaz frogatuko dugu.

$a=0$ bada, $n=h=1$ eta $p^a=p^0=1$ izango dira; orduan, $h=p^a$ betetzen da.

Demagun emaitza zuzena dela $a\le k$ denean, eta izan bedi $a=k+1$.

$T$ zuhaitzaren $h$ hostoen maila-zenbaki posibleak $1,\dots ,a$ dira, eta, gutxienez, $p$ hosto daude $a$ mailan.

Har ditzagun erroaren $p$ umeak, eta izan bitez $T_1,\dots ,T_p$ erroak erpin horietan dituen azpizuhaitzak (zuhaitz $p$-tar osotuak dira). $T_i$ zuhaitzaren hosto-kopurua $h_i$ eta altuera $a_i$ badira, $i=1,\dots ,p$ izanik, $a_i\le a-1$, $i=1,\dots ,p$, eta $h=h_1+\dots +h_p$ izango dira.

$a_i\le a-1=k$ denez, $i=1,\dots ,p$ izanik, indukzio-hipotesiaren arabera, $h_i\le p^{a_i}\le p^{a-1}$ izango dugu, $i=1,\dots ,p$. Hortaz, $h=h_1+\dots +h_p\le p(p^{a-1})=p^a$.

Ondorioz, $h=p^a$ betetzen da $a$ guztietarako.

$h\le p^a$ denez, ${\log }_{p}h\le {\log }_p(p^a)=a$ izango dugu, eta $a\in \mathbb{Z}$ denez, $a\ge \lceil {\log }_{p}h\rceil$ aterako dugu. $◻$ $◼$ $◻$

5.104 Adibidea. Zuhaitz honetan

$p=3$, $a=3$, $h=9$ dira. Orduan, $9\le 3^3$ eta $3\ge \lceil {\log }_{3}9\rceil =\lceil 2\rceil =2$ betetzen dira.

5.105 Korolarioa. Izan bedi $T=(V,E)$ $a$ altuerako eta $h$ hostoko zuhaitz $p$-tar osotu orekatua ($p>1$). Orduan, $a=\lceil {\log }_{p}h\rceil$ beteko da.

Froga.

$a=0$ bada, $h=1$ eta $\lceil {\log }_{p}h\rceil =\lceil {\log }_{p}1\rceil =\lceil 0\rceil =0=a$ izango dira.

$a>0$ bada, $a-1$ mailan, gutxienez, barne-erpin bat dago ($i_{a-1}>0$). $k=0,1,\dots ,a$ balioetarako $n_k$, $i_k$ eta $h_k$ $k$ mailan dauden erpin guztien kopurua, barne-erpinen kopurua eta hostoen kopurua dira, hurrenez hurren. Orduan, $n_0=1$ eta $$n_k=i_{k-1}p,k=1,\dots ,a.$$

Horrez gain, orekatua izateagatik, $h_k=0$ eta $n_k=i_k$, $k=0,\dots ,a-2$ dira. Hortaz, $n_{a-1}=n_{a-2}p=n_{a-3}{p}^2=\dots =n_0{p}^{a-1}=p^{a-1}$ eta $h=h_{a-1}+h_a=h_{a-1}+i_{a-1}p=h_{a-1}+i_{a-1}+i_{a-1}(p-1)>h_{a-1}+i_{a-1}=n_{a-1}=p^{a-1}.$

Hau da, $h>p^{a-1}$ betetzen da. Hortik, ${\log }_{p}h>{\log }_p(p^{a-1})=a-1$ izango dugu. Gainera, [sabaiteo] Teoremaren arabera, ${\log }_{p}h\le a$ betetzen da.

Hortaz, $a=\lceil {\log }_{p}h\rceil$. $◻$ $◼$ $◻$

5.106 Adibidea.

$p=2$, $a=3$, $h=7$ dira. Eta $3=\lceil {\log }_{2}7\rceil =\lceil 2^{\prime }\dots \rceil =3$ betetzen da.