1. Kas ir koks un mežs?

Koks

• Grafu teorijā a koks ir nevirzīts, savienots un aciklisks grafs . Citiem vārdiem sakot, savienotu grafiku, kas nesatur pat vienu ciklu, sauc par koku.
• Koks attēlo hierarhisku struktūru grafiskā formā.
• Koku elementus sauc par to mezgliem, bet koka malas sauc par zariem.
• Kokam ar n virsotnēm ir (n-1) malas.
• Koki nodrošina daudzas noderīgas lietojumprogrammas, kas ir tik vienkāršas kā ciltskoks un ir tik sarežģītas kā koki datorzinātņu datu struktūrās.
• A lapu kokā ir 1. pakāpes virsotne vai jebkuru virsotni, kurai nav bērnu, sauc par lapu.

Piemērs

Iepriekš minētajā piemērā visi ir koki ar mazāk nekā 6 virsotnēm.

Mežs

Grafu teorijā a mežs ir nevirzīts, atvienots, aciklisks grafiks . Citiem vārdiem sakot, nesadalīta koku kolekcija ir pazīstama kā mežs. Katra meža sastāvdaļa ir koks.

Piemērs

Iepriekš redzamais grafiks izskatās kā divi apakšgrafiki, bet tas ir viens atvienots grafiks. Iepriekš minētajā grafikā nav ciklu. Tāpēc tas ir mežs.

2. Koku īpašības

1. Katram kokam, kuram ir vismaz divas virsotnes, jābūt vismaz divām lapām.
2. Kokiem ir vairākas īpašības:
   Lai T ir grafs ar n virsotnēm, tad šādi apgalvojumi ir līdzvērtīgi:
   • T ir koks.
   • T nesatur ciklus, un tam ir n-1 malas.
   • T ir savienots un tam ir (n -1) mala.
   • T ir savienots grafs, un katra mala ir griezuma mala.
   • Jebkuras divas grafa T virsotnes ir savienotas tieši ar vienu ceļu.
   • T nesatur nevienu ciklu, un jebkurai jaunai malai e grafam T+ e ir tieši viens cikls.
3. Katra koka mala ir nogriezta.
4. Vienas malas pievienošana kokam nosaka tieši vienu ciklu.
5. Katrā savienotajā grafikā ir aptverošs koks.
6. Katram kokam ir vismaz divas otrās pakāpes virsotnes.

3. Izvēršanas koks

A aptverošs koks savienotā grafā G ir G apakšgrafs H, kas ietver visas G virsotnes un ir arī koks.

Piemērs

Apsveriet šādu grafiku G:

No iepriekš redzamā grafika G mēs varam realizēt šādus trīs aptverošus kokus H:

Metodes, lai atrastu aptverošo koku

Mēs varam sistemātiski atrast aptverošo koku, izmantojot vienu no divām metodēm:

1. Izciršanas metode
2. Veidošanas metode

1. Izciršanas metode

• Sāciet izvēlēties jebkuru ciklu grafikā G.
• Noņemiet vienu no cikla malām.
• Atkārtojiet šo procesu, līdz nav palicis neviens cikls.

Piemērs

• Apsveriet grafiku G,

• Ja mēs noņemam malu ac, kas iznīcina ciklu a-d-c-a iepriekš minētajā grafikā, mēs iegūstam šādu grafiku:

• Noņemiet no augšējā grafika malu cb, kas iznīcina ciklu a-d-c-b-a, tad iegūstam šādu grafiku:

• Ja no iepriekš minētā grafika noņemam malu ec, kas iznīcina ciklu d-e-c-d, tad iegūstam šādu aptverošo koku:

2. Apbūves metode

• Atlasiet diagrammas G malas pa vienai. Tādā veidā, lai nebūtu ciklu, tiek izveidoti.
• Atkārtojiet šo procesu, līdz ir iekļautas visas virsotnes.

Piemērs

Apsveriet šādu grafiku G,

• Izvēlieties malu ab ,

• Izvēlieties malu no ,

• Pēc tam izvēlieties malu ec ,

• Tālāk izvēlieties malu cb , tad visbeidzot iegūstam šādu aptverošo koku:

Circuit Rank

Malu skaits, kas mums jāizdzēš no G, lai iegūtu aptverošu koku.

Izplatošais koks G = m- (n-1) , ko sauc par ķēdes rangs no G.

 Where, m = No. of edges. n = No. of vertices. 

Piemērs

Iepriekš minētajā grafikā malas m = 7 un virsotnes n = 5

Tad ķēdes rangs ir,

 G = m - (n - 1) = 7 - (5 - 1) = 3