5. Gaia: Grafoak

5.1 Sarrera

XVIII. mendean Konigsberg (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

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.

Adibidea. [grafozu] 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})\}.$

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

ertza intzidentea da $a$ eta $b$ erpinekin.
$a$ erpina $b$ -rantz adjazentea da.
$b$ erpina $a$ -tik adjazentea da.
$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.

Definizioa. Ertzen noranzkoak ez badu garrantzirik, hau da, $(a,b)\in E\Rightarrow (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)$ .

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

Adibidea. [grafoezzu] Hona hemen Konigsbergeko zubien problemari dagokion grafoa: lau lur-eremuak erpinak dira, eta zubiak ertzak:

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

Definizioa. $G=(V,E)$ grafo zuzendu bat emanik, 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.

Adibideak. [elkartua]

Hau da [grafozu] Adibideko grafoaren grafo ez-zuzendu elkartua:

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.

Adibideak.

Lehena $2$ -grafo zuzendua da, eta bigarrena $3$ -grafo zuzendua.
Konigsbergeko zubien problemaren grafoa ([grafoezzu] Adibidea) $2$ -grafo ez-zuzendua da.
[elkartua] Adibideko grafoak bakunak dira.

5.3 Erpinen graduak

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)={\mbox{card}}\{b\,\mid \,(a,b)\in E\}.$
$a$ erpinaren sarrera-gradua $a$ -ra iristen diren ertzen kopurua da, $d^{-}(a)$ adierazten da, $d^{-}(a)={\mbox{card}}\{b\,\mid \,(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).$

Adibidea. [grafozu] Adibideko grafoan, $d^{+}(x_{1})=2,\quad d^{+}(x_{2})=1,\quad d^{+}(x_{3})=2,\quad d^{+}(x_{4})=2,\quad d^{+}(x_{5})=0.$ $d^{-}(x_{1})=0,\quad d^{-}(x_{2})=3,\quad d^{-}(x_{3})=2,\quad d^{-}(x_{4})=2,\quad d^{-}(x_{5})=0.$ $d(x_{1})=2,\quad d(x_{2})=4,\quad d(x_{3})=4,\quad d(x_{4})=4,\quad d(x_{5})=0.$

Definizioa. $G=(V,E)$ grafo ez-zuzendua eta $a\in V$ emanik, $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.

Adibideak.

Konigsbergeko zubien problemaren grafoan ([grafoezzu] Adibidea), $d(A)=5,\quad d(B)=d(C)=d(D)=3.$
[elkartua]-2 Adibideko grafoan, $d(x_{1})=2,\quad d(x_{2})=d(x_{3})=3,\quad d(x_{4})=4,\quad d(x_{5})=0.$

Teorema. Izan bedi $G=(V,E)$ grafo ez-zuzendua $m$ ertzekin. 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.)

Frogabidea $m$ ertz-kopuruaren gaineko indukzioaz egingo dugu.

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

$a\neq b$ bada, $\left\{{\begin{array}{ll}d(a)=1,&\\d(b)=1,&\\d(y)=0,&a\neq y\neq b{\mbox{ bada,}}\end{array}}\right.$ $\quad$ eta $a=b$ bada, $\left\{{\begin{array}{ll}d(a)=2,&\\d(y)=0,&y\neq a{\mbox{ bada.}}\end{array}}\right.$

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

Horrez gain, $a\neq b$ bada, $\left\{{\begin{array}{ll}d(a)=d'(a)+1,&\\d(b)=d'(b)+1,&\\d(y)=d'(y),&a\neq y\neq b{\mbox{ bada,}}\end{array}}\right.$ eta $a=b$ bada, $\left\{{\begin{array}{ll}d(a)=d'(a)+2,&\\d(y)=d'(y),&y\neq a{\mbox{ bada.}}\end{array}}\right.$

Bi kasuetan, $\sum _{x\in V}d(x)=\sum _{x\in V}d'(x)+2=2p+2=2(p+1)=2m.$ $\Box$

Adibideak.

Konigsbergeko zubien problemaren grafoan ([grafoezzu] Adibidea), $n=4$ , $m=7$ , $d(A)+d(B)+d(C)+d(D)=5+3+3+3=2\cdot 7.$
[elkartua]-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=2\cdot 6.$

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

Froga.

Izan bedi $V=\{x_{1},\ldots ,x_{n}\}$ eta demagun badaudela gradu bikoitiko $p$ erpin eta gradu bakoitiko $q$ erpin ( $p+q=n$ ). ${\begin{array}{ll}d(x_{i})=2k_{i},&i=1,\ldots ,p;\\d(x_{i})=2k_{i}+1,&i=p+1,\ldots ,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\left(m-\sum _{i=1}^{p+q}k_{i}\right).$ $\Box$

Adibideak.

Konigsbergeko zubien problemaren grafoan ([grafoezzu] Adibidea) gradu bakoitiko 4 erpin daude ( $A$ , $B$ , $C$ eta $D$ ).
[elkartua]-2 Adibideko grafoan gradu bakoitiko 2 erpin daude ( $x_{2}$ eta $x_{3}$ ).

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

Adibidea. [3erregularra] Grafo hau $3$ -erregularra da:

5.4 Ibilaldiak grafo batean

Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua. $x,y\in V$ bi erpin badira, $x-y$ ibilaldia $G$ grafoan erpinen eta ertzen segida txandakatu finitu bat da, zeina $x$ erpinean hasi eta $y$ erpinean bukatzen den: $x=x_{0},e_{1},x_{1},e_{2},x_{2},e_{3},\ldots ,e_{p-1},x_{p-1},e_{p},x_{p}=y$ $e_{i}=\{x_{i-1},x_{i}\}$ ertza izanik, $i=1,\ldots ,p$ .

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

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

Oharra. Grafo bakuna denean, ertzak ez ditugu idatziko.

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 $6$ luzerako ibilaldi itxia da: $x_{1},x_{3},x_{2},x_{4},x_{3},x_{2},x_{1}.$

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

Ertz bat ere ez bada errepikatzen, $x-y$ ibilaldiari kate deituko diogu. Katea itxia denean, $x-x$ ibilaldi itxiari zirkuitu deituko diogu.
Erpin bat ere 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 suposatuko dugu; eta bat bakarrik dagoenean, zirkuitua begizta izango da. Zikloetan gutxienez hiru ertz desberdin daudela suposatuko dugu.

Adibidea. [elkartua]-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.

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

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

Froga.

Demagun $x-y$ ibilaldi bat dagoela. Ibilaldi guztien artean, har dezagun luzera txikieneko ibilaldia: $x=x_{0},x_{1},\ldots ,x_{k-1},x_{k}=y.$

Ibilaldi hori ez bada bidea, $\exists p,q\,/\,0\leq p<q\leq k$ eta $x_{p}=x_{q}$ . Baina, orduan, $x=x_{0},x_{1},\ldots ,x_{p-1},x_{q},x_{q+1},\ldots ,x_{k}=y$ ere $x-y$ ibilaldi bat da, eta $k$ baino luzera txikiagokoa da.

Elkarrekikoa berehalakoa da; izan ere, bide bat ibilaldi bat da. $\Box$

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.

Adibidea. [3erregularra] Adibideko grafoa konexua da.

[elkartua]-1 Adibideko grafoak konexuak dira.

[grafozu] Adibideko grafoa eta [elkartua]-2 Adibideko grafo elkartua diskonexuak dira, ez dagoelako, esaterako, $x_{1}-x_{5}$ biderik.

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

Froga.

${\mathcal {R}}$ bihurkorra da. Hau frogatu behar dugu: $(\forall x\in V)\quad x{\mathcal {R}}x.$ $\forall x\in V$ , $x-x$ ibilaldi nabaria dago; hortaz, $x{\mathcal {R}}x$ .
${\mathcal {R}}$ simetrikoa da. Hau frogatu behar dugu: $(\forall x,y\in V)\quad x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x.$ $x,y\in V$ badira, ${\begin{array}{l}x{\mathcal {R}}y\Rightarrow x=x_{0},x_{1},\ldots ,x_{p-1},x_{p}=y{\mbox{ ibilaldia badago }}\Rightarrow \\\Rightarrow y=x_{p},x_{p-1},\ldots ,x_{1},x_{0}=x{\mbox{ ibilaldia badago }}\Rightarrow y{\mathcal {R}}x.\end{array}}$
${\mathcal {R}}$ iragankorra da. Hau frogatu behar dugu: $(\forall x,y,z\in V)\quad x{\mathcal {R}}y\wedge y{\mathcal {R}}z\Rightarrow x{\mathcal {R}}z.$ $x,y,z\in V$ badira, ${\begin{array}{l}x{\mathcal {R}}y\wedge y{\mathcal {R}}z\Rightarrow \\\Rightarrow x=x_{0},\ldots ,x_{p}=y\;\wedge \;y=y_{0},\ldots ,y_{q}=z{\mbox{ ibilaldiak badadaude }}\Rightarrow \\\Rightarrow x=x_{0},\ldots ,x_{p}=y=y_{0},y_{1},\ldots ,y_{q}=z{\mbox{ ibilaldia badago }}\Rightarrow x{\mathcal {R}}z.\end{array}}$ $\Box$

Definizioa. [baliokidetasuna] Teoreman definitutako baliokidetasun-erlazioak erpinen $V$ multzoa $V_{1},\ldots ,V_{q}$ baliokidetasun-klasetan banatzen du. $G_{1}=(V_{1},E_{1})$ , $\ldots$ , $G_{q}=(V_{q},E_{q})$ grafoei, non $E_{i}$ , $i=1,\ldots ,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.

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

$G_{1}=(V_{1},E_{1})$ eta $G_{2}=(V_{2},E_{2})$ , non $V_{1}=\{x_{1},x_{2},x_{3},x_{4}\},\quad V_{2}=\{x_{5}\}{\mbox{ diren eta}}$ $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}\}\},\quad E_{2}=\emptyset {\mbox{ diren}}.$

5.5 Grafo baten adjazentzia-matrizea

Definizioa. Izan bedi $G=(V,E)$ grafo bakun ez-zuzendua, begiztarik gabea eta $n$ erpinekin, non $V=\{x_{1},\ldots ,x_{n}\}$ den. $G$ grafoari dagokion adjazentzia-matrizea honela definituko dugu: $A=(a_{ij})$ , $i,j=1,...,n$ $a_{ij}=\left\{{\begin{array}{ll}1,&\quad x_{i},x_{j}{\mbox{ adjazenteak badira,}}\\0,&\quad x_{i},x_{j}{\mbox{ ez badira adjazenteak.}}\\\end{array}}\right.$

$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}.$

Adibideak. [matrizea]

[elkartua]-2 Adibideko grafoaren adjazentzia-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).$
grafoaren adjazentzia-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$ .

Teorema. Izan bitez $G=(V,E)$ grafo bakun ez-zuzendua, begiztarik gabea, $V=\{x_{1},\ldots ,x_{n}\}$ izanik, eta $A$ $G$ grafoari dagokion adjazentzia-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: $\left\{{\begin{array}{ll}1,&\quad (x_{i},x_{j})\in E{\mbox{ bada,}}\\0,&\quad (x_{i},x_{j})\not \in E{\mbox{ bada;}}\\\end{array}}\right.$

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, frogatu behar dugu $A^{k+1}$ matrizearen $(i,j)$ elementua $k+1$ luzerako $x_{i}-x_{j}$ ibilaldien kopurua dela.

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

Orduan, $A^{k+1}=A^{k}A$ denez, hau bateko 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,\ldots ,n\}$ ) edozein erpin den.

$(x_{l},x_{j})\in E$ bada, $a_{lj}=1$ izango da eta, beraz, $k+1$ luzerako eta $x_{i}=y_{0},y_{1},\ldots ,y_{k}=x_{l},y_{k+1}=x_{j}$ itxurako ibilaldien kopurua $k$ luzerako $x_{i}-x_{l}$ ibilaldien kopurua izango da, hots, $b_{il}=b_{il}a_{lj}$ .

Ordea, $(x_{l},x_{j})\not \in E$ bada, $a_{lj}=0$ izango da eta, beraz, $k+1$ luzerako eta $x_{i}=y_{0},y_{1},\ldots ,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}.$ $\Box$

Adibidea.

[matrizea]-2 Adibideko grafoaren adjazentzia-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;{\mbox{ eta }}d,e,b,e.$

5.6 Azpigrafoak. Grafo osagarria

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:

$\emptyset \neq V_{1}\subseteq V$ eta
$E_{1}\subseteq E$ eta $E_{1}$ multzoaren ertz bakoitzak intzidente izan behar du $V_{1}$ multzoaren erpinekin soilik.

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

$G_{1}$

$G_{2}$

$G_{3}$

Definizioa. $G_{1}=(V_{1},E_{1})$ grafoa $G=(V,E)$ grafoaren azpigrafoa bada, $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 $\mid E\mid =m$ bada, $2^{m}$ azpigrafo sortzaile izango ditu.

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.

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

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.

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.

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

$x\in V$ emanik, $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$ emanik , $G-e$ idatziko dugu $G-e=(V_{1},E_{1})$ azpigrafoa adierazteko, non:
- $V_{1}=V$ den eta
- $E_{1}=E\setminus \{e\}$ den.

Adibidea. [ken] [azpigrafoak] Adibidean, $G_{3}=G-d$ eta $G_{2}=G-\{d,e\}$ .

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

Definizioa. Izan bedi $V=\{x_{1},\ldots ,x_{n}\}$ erpinen multzoa; $V$ multzoaren gaineko grafo osotua grafo bakun, ez-zuzendu eta begiztarik gabea da, non $(\forall x,y\in V)\quad x\neq y\;\Longrightarrow \;\{x,y\}\;{\mbox{ 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.

Adibideak.

$K_{4}$

$K_{5}$

Definizioa. Izan bedi $G=(V,E)$ grafo bakuna, ez-zuzendua, begiztarik gabea eta $n$ erpinekin, $V=\{x_{1},\ldots ,x_{n}\}$ izanik. $G$ grafoaren grafo osagarria $K_{n}$ grafo osotuaren ${\overline {G}}=(V,{\overline {E}})$ azpigrafoa da, non ${\overline {E}}$ multzoan $E$ multzoan ez dauden $K_{n}$ grafo osotuaren ertzak dauden.

$G=K_{n}$ bada, ${\overline {G}}$ grafoak $n$ erpin eta $0$ ertz izango ditu; grafo nulua deitzen da.

Adibidea. $G$ grafo hau bada:

orduan, ${\overline {G}}$ beste hau izango da:

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}=\emptyset$ diren eta
$G$ grafoaren $\{x,y\}$ ertz bakoitzean $x\in V_{1}$ eta $y\in V_{2}$ badira.

Horrez gain,

( $\forall x\in V_{1}$ , $\forall y\in V_{2}$ ) $\{x,y\}$ ertza badago,

$G$ zatibiko grafo osotua da, eta $K_{n_{1},n_{2}}$ idatziko dugu, $\mid V_{1}\mid =n_{1}$ eta $\mid V_{2}\mid =n_{2}$ izanik.

Adibideak.

Grafo hau zatibiko grafo (ez osotua) da:
Grafo hau $K_{2,3}$ zatibiko grafo osotua da:

5.7 Grafoen arteko isomorfismoak

Definizioa. Izan bitez $G_{1}=(V_{1},E_{1})$ eta $G_{2}=(V_{2},E_{2})$ bi grafo ez-zuzendu. $f:V_{1}\;\longrightarrow \;V_{2}$ funtzioa grafoen arteko isomorfismoa da hau betetzen badu:

$f$ bijektiboa da eta
$(\forall x,y\in V_{1})\quad \{x,y\}\in E_{1}\,{\mbox{ 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.

Adibideak. [isomorfismo]

Har ditzagun grafo hauek:

$G_{1}=(V_{1},E_{1})\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad G_{2}=(V_{2},E_{2})$

$f:V_{1}\;\longrightarrow \;V_{2}$ funtzioa, $f(a)=w,\quad f(b)=x,\quad f(c)=y,\quad f(d)=z,$ isomorfismoa da. Hau da, $G_{1}\cong G_{2}$ .

${\begin{array}{l}\{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}}$
Ikus ditzagun, orain, grafo hauek:
$G_{3}\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad G_{4}$
Bi grafoek 6na erpin eta 9na ertz dituzte. Baina ez dira isomorfoak.

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

5.8 Kate eta zirkuitu eulertarrak

Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua eta erpin isolaturik gabea. Zirkuitu eulertarra $G$ grafoaren ertz bakoitza behin bakarrik erabiltzen duen zirkuitua da.

Kate eulertarra $G$ grafoaren ertz bakoitza behin bakarrik erabiltzen duen kate irekia da.

$G$ grafoa eulertarra da zirkuitu eulertar bat badauka.

Adibideak.

[isomorfismo]-2 Adibideko $G_{4}$ grafoan zirkuitu eulertar hau aurki dezakegu: $u,v,z,x,v,w,x,y,z,u.$ Beraz, grafo eulertarra da.
[isomorfismo]-2 Adibideko $G_{3}$ grafoan kate eulertar hau aurki dezakegu: $b,a,f,b,c,d,e,c,f,e.$ Ezin da, ordea, zirkuitu eulertar bat ere aurkitu.

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

$G$ eulertarra da $\Longleftrightarrow$ $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 es duenez, $V$ multzoaren erpin guztiak behin gutxienez agertuko dira $C$ zirkuituan. $x,y\in V$ bi erpin desberdinak emanik, $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.

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

Hasteko, frogatuko dugu, $x\in V$ erpin bat emanik, $x$ erpina duen zirkuitu bat dagoela. Izan bedi $x=y_{0},f_{1},y_{1},\ldots ,f_{k},y_{k}$ $x$ erpinean hasten den ibilaldirik luzeena. $i\in \{1,\cdots ,k\}$ baterako $x=y_{i}$ bada, orduan $x=y_{0},f_{1},\cdots ,f_{i},y_{i}=x$ $x$ erpina duen zirkuitu bat da.

$i\in \{1,\cdots ,k\}$ guztietarako $x\neq y_{i}$ bada, orduan $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, suposatu dugunaren kontra, hau da, ibilaldia luzeena izatearen kontra.

$y_{k}\neq 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, orduan 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 $C$ zirkuitu bat dagoela suposa dezakegu.

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'$ grafo bat lortuko dugu, zeinak $\{G_{1},G_{2},\ldots ,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. $\Box$

Adibideak.

Irudiko grafoan, $b$ erpinetik pasatzen den $C$ zirkuitua hartuko dugu: $C=bcgfb$ . Gero, $G$ grafoari $C$ zirkuituaren ertzak eta isolaturik geratzen diren erpinak ( $b$ ) kenduko dizkiogu; $G_{1}$ , $G_{2}$ eta $G_{3}$ osagai konexuek osatzen duten $G'$ grafoa geratuko zaigu.

$G$ grafoaren zirkuitu eulertarra lortzeko, $b$ erpinetik (esaterako) hasiko gara: $bcG_{1}cgG_{2}gfG_{3}fb;$ edo erpin guztiak idatziz: $bc{\underline {adc}}g{\underline {ijg}}f{\underline {ehf}}b.$
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 geratzen diren erpinak ( $d$ , $e$ ) kenduko dizkiogu; $G'$ lortuko dugu. $G'$ grafoan, $C'=bchfb$ zirkuitua hartuko dugu. Orain, $G'$ grafoari $C'$ 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'$ grafoaren zirkuitu eulertarra eratuko dugu. $C'$ 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'$ zirkuitutik segituko dugu. Horrela zirkuitu eulertar hau lortuko dugu: $E'=b{\underline {hafcgb}}chfb$ .

$G$ grafoaren $E$ zirkuitu eulertarra eratzeko, $C$ zirkuituaren edozein erpinetan hasiko gara, adibidez, $d$ erpinean. $C$ zirkuitutik ibiliko gara $G'$ grafoarekin erpin komun bat aurkitu arte, adibidez, $h$ . $h$ erpinetik $G'$ grafoan sartuko gara eta $E'$ zirkuitu eulertarra berridatziko dugu: $E'=hafcgbchfbh$ . Horrela, $G'$ 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{\underline {afcgb{\underline {chfb}}h}}eagd$ .

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

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

Froga.

Demagun

G

grafoak

R

kate eulertar bat duela (ez zirkuitua):

a-b

,

a\neq b

izanik.

Izan bedi $G'$ grafoa $G$ grafoari $\{a,b\}$ ertza eranstean sortzen den grafoa. Orduan, $R\cup \{a,b\}$ $G'$ grafoaren zirkuitu eulertarra da. [zieul]Teorema $G'$ grafoari aplikatuz gero, $G'$ grafoaren erpin guztiek gradu bikoitia izango dute. $x\in V$ emanik, $d(x)$ bada $x$ erpinaren gradua $G$ grafoan, eta $d'(x)$ $x$ erpinaren gradua $G'$ grafoan, orduan ${\begin{array}{ll}d(x)=d'(x)&x\neq a,x\neq b{\mbox{ bada}},\\d(a)=d'(a)-1,\\d(b)=d'(b)-1.\end{array}}$ $\forall x\in V$ , $d'(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\neq b

.

Izan bedi $G'$ grafoa $G$ grafoari $\{a,b\}$ ertza eranstean sortzen den grafoa. $G'$ konexua da eta $G'$ grafoaren erpin guztiek gradu bikoitia badute. [zieul] Teorema aplikatuz, $G'$ 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. $\Box$

Adibideak.

grafoan, $K=acbadc$ kate eulertar bat da. Ez dago zirkuitu eulertarrik.
Konigsbergeko zubien problemaren grafoan ([grafoezzu] Adibidea), 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.

Definizioa. Izan bedi $G=(V,E)$ grafo zuzendu eta erpin isolaturik gabea. Zirkuitu eulertarra deituko diogu $G$ grafoaren ertz bakoitza behin bakarrik erabiltzen duen zirkuitu zuzenduari.

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

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

5.9 Bide eta ziklo hamiltondarrak

Definizioa. Izan bedi $G=(V,E)$ grafo ez-zuzendua, $\mid V\mid =n\geq 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.

Ziklo hamiltondar batetik ertz bat ezabatuz gero, bide hamiltondar bat lortuko dugu.
Grafo batek bide hamiltondar bat badu, konexua da.
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.

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)$ grafo ziklo hamiltondar bat aurkitzeko.

$G$ hamiltondarra bada, $x\in V$ erpin guztietarako $d(x)\geq 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.

Teorema. $G=(V,E)$ grafoa begiztarik gabe eta $n\geq 3$ erpinekin emanik, $\forall x,y\in V\quad (x\neq y)\quad d(x)+d(y)\geq n-1$ betetzen badu, $G$ grafoak bide hamiltondarra izango du.

Korolarioa. $G=(V,E)$ grafoa begiztarik gabe eta $n\geq 3$ erpinekin emanik, $\forall x\in V\quad d(x)\geq {\frac {n-1}{2}}$ betetzen badu, $G$ grafoak bide hamiltondarra izango du.

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 $\forall x\in V\quad d(x)\geq {\frac {7-1}{2}}=3$ betetzen du; beraz, bide hamiltondar bat badu.

Teorema. $G=(V,E)$ grafoa begiztarik gabe eta $n\geq 3$ erpinekin emanik, $\forall x,y\in V\quad (x,y\,{\mbox{ ez-adjazenteak}})\quad d(x)+d(y)\geq n$ betetzen badu, $G$ grafo hamiltondarra izango da.

Korolarioa. $G=(V,E)$ grafoa begiztarik gabe eta $n\geq 3$ erpinekin emanik, $\forall x\in V\quad d(x)\geq {\dfrac {n}{2}}$ betetzen badu, $G$ grafo hamiltondarra izango da.

Adibidea. Hogei laguneko talde batean, bakoitzak gutxienez hamar lagun ezagutzen ditu. Ikus dezagun mahai biribil baten inguruan eseri daitezkeela, bakoitzak alboko bi mahaikideak ezagut ditzan.

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

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

Ziklo hamiltondarra baldintza horietan mahaiaren inguruan esertzeko era bat izango da. Teorema hauek grafo batek bide edo ziklo hamiltondar bat izateko baldintza beharrezkoak ematen dituzte. Lehenengoa zatibiko grafo bati dagokio.

Teorema. $G=(V,E)$ zatibiko grafoa emanik, non $V=V_{1}{\dot {\cup }}V_{2}$ den, $G$ grafoa hamiltondarra bada, $\mid V_{1}\mid =\mid V_{2}\mid$ izango da.

Aurreko teoremak esaten digu, $G=(V,E)$ zatibiko grafoa emanik, non $V=V_{1}{\dot {\cup }}V_{2}$ den, $\mid V_{1}\mid \neq \mid V_{2}\mid$ bada, $G$ grafoa ez dela hamiltondarra.

Adibide honek frogabidearen ideia emango digu.

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 adjazenteak diren erpin guztiak ( $b$ , $c$ eta $d$ ) $y$ izendatuko ditugu. Ondoren, $y$ erpinekin adjazenteak 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},\quad V_{1}=\{a,e,g,i\},\quad V_{2}=\{b,c,d,f,h,j\}$ $\mid V_{1}\mid \neq \mid V_{2}\mid$ 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. $G=(V,E)$ grafoa emanik, eta $V'\subset V$ erpinen azpimultzo bat, $G-V'$ idatziko dugu $G-V'=(V_{1},E_{1})$ grafoa adierazteko, non $V_{1}=V\setminus V'$ den eta $E_{1}$ multzoan $E$ multzoaren ertzak dauden, $V'$ multzoaren erpinekin intzidenteak direnak izan ezik.

Teorema. $G=(V,E)$ grafo hamiltondarra bada, edozein $V'\subset V$ azpimultzotarako, $\emptyset \neq V'\neq V$ izanik, $\kappa (G-V')\leq {\mbox{card}}(V').$

Korolarioa. $G=(V,E)$ grafoa emanik, $V'\subset V$ azpimultzo bat badago, $\emptyset \neq V'\neq V$ izanik, non $\kappa (G-V')>{\mbox{card}}(V')$ betetzen den, $G$ grafoa ez da hamiltondarra izango.

Adibidea. [zatiziham] Adibideko grafoan, $x$ izendatutako erpinak kenduz gero, $y$ izendatutako erpinak isolaturik geratuko lirateke. Beraz, $\kappa (G-V')=6$ eta ${\mbox{card}}(V')=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

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

Grafo baten zuhaitz sortzaile deituko diogu zuhaitz den edozein azpigrafo sortzaileri (grafoaren erpin guztiak dituena).

Adibidea. [zuhaitza]

$G_{1}$ grafoa $G_{2}$ grafoaren zuhaitz sortzailea da.

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

Froga.

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

$T$ konexua denez, gutxienez $a-b$ bide bat dago: $C(a=x_{0},x_{1},\ldots ,x_{p}=b)$ .

Demagun beste $a-b$ bide bat dagoela, $C'$ .

Izan bedi $x_{t}$ erpina $C'$ bidean ez dagoen $C$ bidearen lehen erpina ( $1\leq t\leq p-1$ ); eta izan bedi $x_{s}$ erpina bi bideetan dagoen $C$ bidearen hurrengo erpina ( $t<s\leq p$ ).

Orduan, $C$ eta $C'$ bideen zatiek, $x_{t-1}$ eta $x_{s}$ erpinen artean, ziklo bat osatuko lukete, $T$ zuhaitza izatearen kontra doana. $\Box$

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\,{\mbox{ ertza ziklo batean dago}}\,\Longleftrightarrow G-e\,{\mbox{ grafoa konexua bada}}.$

Froga.

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

Demagun $e$ ertza $C$ ziklo batean dagoela: $C=a,b,x_{1},x_{2},\ldots ,x_{p},a$ .

$G-e$ grafoa konexua dela frogatzeko, edozein $x,y\in V$ bi erpin desberdin emanik, $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},\ldots ,y_{t},a,b,z_{1},\ldots ,z_{q},y$ izango da.

Orduan, $(P-e)\cup (C-e):x,y_{1},\ldots ,y_{t},a,x_{p},\ldots ,x_{1},b,z_{1},\ldots ,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},\ldots ,x_{p},b$ . Hortaz, $P\cup e:a,x_{1},\ldots ,x_{p},b,a$ ziklo bat da $G$ grafoan. $\Box$

Teorema. [zuhasor] Izan bedi $G$ grafo ez-zuzendu bat. $G\,{\mbox{ konexua da}}\,\Longleftrightarrow G\,{\mbox{ 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.

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. $\Box$

Adibidea. [sortzailea]

$G_{5}$ grafoa $G$ grafoaren zuhaitz sortzaile bat da.

Lema. [azpizuhaitzak] Izan bedi $T$ zuhaitz bat eta izan bedi $e$ artza $T$ zuhaitzaren edozein ertz. Orduan, $T-e$ diskonexua 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; $T$ zuhaitza izatearen kontra doana, zuhaitz batean bi erpin lotzen dituen bide bakarra baitago ([bidebakarra] Teorema).

Hortaz, $T-e$ diskonexua da eta bi osagai konexu ditu, $V_{1}=\{a\}\cup \{x\in V\,:\,a-x\,{\mbox{ bide bat dago }}\,T-e\,{\mbox{ grafoan}}\}$ eta $V_{2}=\{b\}\cup \{x\in V\,:\,b-x\,{\mbox{ bide bat dago }}\,T-e\,{\mbox{ grafoan}}\}$ erpinen multzoek induzitutako azpigrafoak hain zuzen.

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

Teorema. [m+1] Izan bedi $T$ zuhaitz bat $n$ erpinekin eta $m$ ertzekin. 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\leq 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\leq m_{1}\leq k$ eta $0\leq m_{2}\leq 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.$ $\Box$

Adibidea. [zuhaitza] Adibideko $G_{1}$ zuhaitzean, $n=6$ eta $m=5$ dira.

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

Froga.

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

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

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

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

Ondorioz, $T$ zuhaitzak gutxienez bi erpin zintzilikatu izango ditu. $\Box$

Adibidea. [zuhaitza] Adibideko $G_{1}$ grafoak 4 erpin zintzilikatu ditu.

[sortzailea] Adibideko $G_{5}$ grafoak 3 erpin zintzilikatu ditu.

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

i): $G$ zuhaitza da.
ii): $G$ grafoak ez du ziklorik, eta $n=m+1$ .
iii): $G$ grafoa konexua da, eta $n=m+1$ .

Froga.

Demagun i) betetzen dela.

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

$G$ grafoak ez du ziklorik zuhaitza delako.

Demagun ii) betetzen dela.

Izan bedi $\kappa (G)=r$ eta izan bitez $G_{1}=(V_{1},E_{1})$ , $\ldots$ , $G_{r}=(V_{r},E_{r})$ $G$ grafoaren osagai konexuak (zuhaitzak direnak ziklorik ez dutelako).

$i=1,\ldots ,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'=(V,E')$ grafoa zuhaitza da, $n$ erpinekin eta $m+r-1$ ertzekin.

[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.

Demagun iii) betetzen dela.

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

5.10.3 Zuhaitz errodunak. Zuhaitz bitarrak

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

Adibidea. [zuhazuzen]

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.

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.

Definizioa. Izan bedi $T$ zuhaitz erroduna:

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

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

$v_{1}$ eta $v_{2}$ erpinak emanik, $v_{1}$ erpina $v_{2}$ erpinaren asaba edo $v_{2}$ erpina $v_{1}$ erpinaren ondorengoa dela esango dugu $v_{1}$ erpinetik $v_{2}$ erpinera bide bat badago. 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$ erpineko azpizuhaitz deituko diogu $v$ erpinak eta bere ondorengo guztiek (baldin baditu) induzitutako azpigrafoari.

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

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

Adibidea. [altuera]

zuhaitzak $a=5$ altuera du.

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

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

Adibidea. [zuhaptar]

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).

Adibidea. [zuhaptaroso1]

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

(a): $n=pi+1$ da.
(b): $h=(p-1)i+1$ da.
(c): $i={\dfrac {h-1}{p-1}}={\dfrac {n-1}{p}}$ da.

Froga.

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

$k=0,1,\ldots ,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,\quad k=1,\ldots ,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.$

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

(c) (a) eta (b) ataletatik ondorioztatuko dugu. $\Box$

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

Adibidea. [zuhaptaroso3] Bost bikotek hartzen dute parte mus txapelketa batean, 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={\dfrac {h-1}{p-1}}={\dfrac {5-1}{2-1}}=4$ .

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

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 $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.

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

Adibidea. [zuhaoreka1] [altuera] Adibideko zuhaitza ez da orekatua, hosto bat 2 mailan dauka eta.

Zuhaitz hau $a=3$ altuerako zuhaitz orekatua da:

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.

Zuhaitza hau bada

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

Zuhaitza 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 \mathbb {R}$ emanik, $\lceil x\rceil$ ( $x$ -ren sabaia) $x$ baino handiagoa edo berdina den zenbaki oso txikiena da.

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

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

Froga.

$h\leq 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}$ .

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

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

Har ditzagun erroaren $p$ umeak, eta izan bitez $T_{1},\ldots ,T_{p}$ erroak erpin horietan dituzten azpizuhaitzak (zuhaitz $p$ -tar osotuak dira). $T_{i}$ zuhaitzaren hosto-kopurua $h_{i}$ eta altuera $a_{i}$ badira, $i=1,\ldots ,p$ izanik, $a_{i}\leq a-1$ , $i=1,\ldots ,p$ , eta $h=h_{1}+\ldots +h_{p}$ .

$a_{i}\leq a-1=k$ denez, $i=1,\ldots ,p$ izanik, indukzio-hipotesiaren arabera, $h_{i}\leq p^{a_{i}}\leq p^{a-1}$ izango dugu, $i=1,\ldots ,p$ . Hortaz, $h=h_{1}+\ldots +h_{p}\leq p(p^{a-1})=p^{a}$ .

$h\leq p^{a}$ denez, $\log _{p}h\leq \log _{p}(p^{a})=a$ izango dugu, eta $a\in \mathbb {Z}$ denez, $a\geq \lceil \log _{p}h\rceil$ aterako dugu. $\Box$

Adibidea. Zuhaitz honetan

$p=3$ , $a=3$ , $h=9$ dira; eta $9\leq 3^{3}$ eta $3\geq \lceil \log _{3}9\rceil =\lceil 2\rceil =2$ betetzen dira.

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, barn-erpin bat dago ( $i_{a-1}>0$ ). $k=0,1,\ldots ,a$ balioetarako $n_{k}$ , $i_{k}$ eta $h_{k}$ $k$ mailan dauden erpin guztien kopurua, barne-erpinen kopurua eta hostoen kopuruak dira, hurrenez hurren. Orduan, $n_{0}=1$ eta $n_{k}=i_{k-1}p,\quad k=1,\ldots ,a.$

Horrez gain, orekatua izateagatik, $h_{k}=0$ eta $n_{k}=i_{k}$ , $k=0,\ldots ,a-2$ dira. Hortaz, $n_{a-1}=n_{a-2}p=n_{a-3}p^{2}=\ldots =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\leq a$ betetzen da.

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

Adibidea.

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