Medžiai – paprasčiausia grafų klasė
5 (100%) 1 vote

Medžiai – paprasčiausia grafų klasė

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.

Šiuo metu Jūs matote 50% šio straipsnio.
Matomi 941 žodžiai iš 1879 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.