4. MEDŽIAI
4.1. Įvadas
Medžiai nusipelno išsamios apžvalgos dėl šių dviejų priežasčių:
• Medžiai yra paprasčiausia grafų klasė. Juos tenkina daugelis savybių,
tačiau jos ne visada tinka bendru grafų atveju. Taikant medžiams daugumą
įrodymų ir pamąstymų, jie iš tikrųjų yra daug paprastesni nei
atrodo.Grafų uždavinių sprendimui iškeliama hipotezė, tikslinga juos
pirmiausia patikrinti medžių pagalba.
• Medžiai yra pati populiariausia grafų klasė, kyri yra taikoma
programavime įvairiausiose situacijose.
4.2. Laisvieji medžiai
Grafas, kuriame nėra ciklų, vadinamas acikliniu arba mišku. Jungus
aciklinis grafas vadinamas laisvu medžiu. Jungi grafo elementai sudaro
medžius ir gaunasi miškas, sudarytas iš medžių. Jungus grafas yra medis
tada, kai jo briaunų skaičius yra lygus q(G)=p(G)-1.
Medžiu vadinamas susietas grafas, kuriame nėra ciklų. Toks grafas,
suprantama, neturi kartotinių briaunų ir kiekvienos dvi jo viršūnės
sujungtos tik viena grandine. Jungūs grafo elementai sudaro medžius, 0
medžiai – miškus. Jungus grafas vadinamas laisvuoju medžiu. Jungus grafas
yra tada ir tik tada medis, kai jo briaunų skaičius lygus m = n – 1. Pagal
viršūnės laipsnį medžiai gali būti binariniai (maksimalus viršūnės laipsnis
2), ternariniai ir t.t. Medžio viršūnės, kurių laipsnis lygus vienam,
vadinamos kabančiomis viršūnėmis arba lapais. Medis, kurio viršūnių
skaičius n [pic] 2, turi bent du lapus. Pirmoji medžio viršūnė, paprastai
viršutinė, vadinama šaknimi – tai viršūnė, iš kurios šakos išeina, bet nė
viena neįeina.
Viršūnės, kurios nutolusios nuo šaknies vienodu atstumu, sudaro vieną lygį.
Kelias iš šaknies į lapą vadinamas šaka. Didžiausias šakos ilgis
orientuotame medyje vadinamas medžio aukščiu. Paprasčiausi ir, beje,
labiausiai paplitę yra binarinės ( dvejetainės) struktūros medžiai.
[pic]
1 pav. Iliustracinė medžio tipo struktūra
Acikliniame grafe G z(G)=O. Tegul u, v – grafo G viršūnės, x =(u,v) E.
Jeigu grafas G+x turi tik tai vieną paprastą ciklą, z(G+x)=l, tai grafas G
vadinamas subcikliniu.Pavyzdys:
Čia yra laisvieji medžiai su penkiom viršūnėm:
[pic]
Laisvieji medžiai su šešiom viršūnėm:
[pic]
4.2.1 Bendros medžių savybės
Teorema: Tegul G(V,E) – grafas su p viršūnėmis, q briaunomis, k jungeis
komponentais ir z paprastais ciklais. Tegul x – briauna, jungianti bet
kurią norimą negretimą porą į grafą G. Tada sekantys teiginiai
ekvivalentūs:
1. G – medis, tai yra surištas grafas be ciklų, k(G)=l & z(G)=O;
2. Bet kurios dvi viršūnės sujungtos į grafą G vienguba paprasta grandimi,
( u, v (! (u,v);
3. G – sujungtas grafas, ir bet kuri briauna yra tiltas, k(G)=l& ;feEE k
(G-e»l;
4. G – surištas ir medžio pavidalo, k(G)=l & q(G)=p(G)-l;
5. G – aciklinis ir medžio pavidalo, z(G)=O & q(G)= p(G)-l;
6. G – aciklinis ir subciklinis, z(G)=O & z(G+x)=l;
7. G – jungus, subciklinis ir nepilnas, k(G)=l & K & p 3 & z(G+x)=l;
8. G – medžio pavidalo ir subciklinis, q(G)=p(G)-l & G(K1 U K3&G( K2 U K3
&z(G+x)=1.
4.2.2. Pagrindinės medžių savybės:
1. Medžiai turi vieną viršūnę, į kurią neįeina jokia kita. Ši viršūnė
vadinama šaknimi.
2. Į kiekvieną viršūnę, išskyrus šaknį, įeina ne daugiau kaip viena viršūnė
(incidentiška).
3. Iš šaknies į kiekvieną viršūnę veda vienintelis kelias.
4. Viršūnės, kurių laipsnis nelygus 0, vadinamos tėvinėmis, 0 joms
incidentiškos dukterinėmis medžio viršūnėmis.
5. Viršūnės, kurios neturi dukterinių, vadinamos terminalinėmis arba
lapais.Medžiai pritaikomi labai įvairiai. Čia paminėsime, kad bet kurį rūšiavimo
procesą galima išreikšti medžiu. Dauguma klasifikacinių schemų ar tiesiog
klasifikatorių turi tipišką medžio struktūrą.
4.3. Orientuoti, sutvarkyti ir binariniai medžiai
Orientuotu medžiu vadinamas medis turintis šias savybes:1. Egzistuoja vienintelė viršūnė, kurios įėjimo puslaipsnis yra lygus 0. Ši
viršūnė
vadinama šaknimi.
2. Įėjimo puslaipsnis lygus 1 kitų viršūnių atžvilgiu.
3. Kiekviena viršūnė yra pasiekiama iš šaknies.Pavyzdys:
Orientuoti medžiai su trim viršūnėm:
[pic]Orientuoti medžiai su keturiom viršūnėm:
[pic]
Orientuotas medis – tai aibė viršūnių, kur tam tikra viršūnė U yra medžio
šaknis, 0 kitos viršūnės yra poromis nesikertančiose aibėse, kurių
kiekviena yra orientuotas medis.
Pografis, kurį sudaro viršūnių aibė, kurį galima pasiekti iš bet kurios
viršūnės, yra orientuotas medis, kurio šaknis yra atitinkama viršūnė. Jei
laisvame grafe bet kurią viršūnę pavadinsime šaknimi, gausime orientuotą
medį.
Orientuotame medyje viršūnės V, pasiekiamos iš viršūnės U, vadinamos
palikuonimis, jei tarp tam tikrų viršūnių U ir V yra laukas, tai viršūnė U
vadinama tėvu, o V – sūnumi. Visi vienos viršūnės sūnūs vadinami broliais.Teorema: Orientuotas medis turi šiai savybes:
1. q=p-1;
2. Jeigu orientuotame medyje panaikinus orientacines ribas, tai gautųsi
laisvasis
medis;
3. Orientuotas medis neturi kontūrų;
4. Kiekvienam mazgui egzistuoja vienintelis
kelias, vedantis jį iš šaknis;
5. Pografis apibrėžiamas daugelio mazgų, pasiekiamų iš mazgo v, yra
orientuotas medis su šaknimi v.
6. Jeigu laisvame medyje bet kurią viršūnę pažymėsime šaknimi, gausime
orientacinį medį.Kiekvieną laisvą medį apibrėžia ne daugiau p orientuotų medžių. Tokiu
būdu, bendras skaičius skirtingų orientuotų medžių su p mazgais ne daugiau
kaip p kartų pralenkia bendrą skaičių skirtingų orientuotų medžių su p
viršūnėmis.