Sakņoti koki

Last modified by superadmin on 2018-01-12 20:40

Koki

Par koku sauc tādu grafu G ar virsotnēm V = {v1, v2, ..., vn} un šķautnēm E = {e1, e2, ..., em}, kurš ir
  • sakarīgs (t.i. no katras virsotnes var nokļūt uz katru citu),
  • aciklisks (t.i. tajā nav ciklu - no katras virsotnes uz katru citu var nokļūt ne vairāk kā vienā veidā).

    Abas šīs pazīmes kopā nozīmē to, ka no katras virsotnes uz katru citu ved tieši viens ceļš (par ceļu saucam virsotņu virkni, kurā katras divas blakusesošās virsotnes savienotas ar šķautni un kurā virsotnes neatkārtojas). Šajā zīmējumā attēlotie grafi nav koki: pirmais nav sakarīgs, bet otrajā eksistē cikls. Abos grafos ir 7 virsotnes. Vienam ir tikai 5 šķautnes, otram - 7 šķautnes.

    #pic("App_Graphs_NonTrees.gif", "160") Attēls: Grafi, kas nav koki

    Var pamatot, ka sakņotā kokā šķautņu ir par 1 mazāk nekā virsotņu: m=n-1. T.i. katram kokam ar 7 virsotnēm ir tieši 6 šķautnes.

    Pamatojums:

  • Ja šķautņu būtu mazāk nekā n-1, tad grafs nevar būt sakarīgs: grafā ar n virsotnēm, bet bez nevienas šķautnes ir n "saliņas". Novelkot kārtējo šķautni, var izveidot "tiltu" starp divām saliņām (t.i. nesakarīgo gabalu skaits var samazināties par 1). Novelkot tieši n-1 šķautnes, var panākt, lai viss grafs sastāvētu no viena sakarīga gabala. Tātad katrā kokā ir vismaz n-1 šķautne.
  • Līdzīgu spriedumu var atkārtot arī pretējā virzienā - ja kokā nodzēš vienu šķautni, tad atlikušajā grafā gabalu skaits palielinās par 1 (ja gabalu skaits nemainītos, tad starp kādām divām virsotnēm būtu iespējami divi ceļi, t.i. pastāvētu cikls). Tātad kokam var nodzēst n-1 šķautni, iegūstot n izolētas virsotnes. T.i. katrā kokā ir ne vairāk kā n-1 šķautne.

Sakņoti koki

Par sakņotu koku sauc tādu grafu G ar virsotnēm V = {v1, v2, ..., vn} un šķautnēm E = {e1, e2, ..., em}, kuram viena virsotne, piemēram, v1 ir īpaši izdalīta, un to sauc par koka sakni (root), turklāt izpildās sekojošas īpašības:
  1. No saknes v1 var pa šķautnēm nonākt jebkurā citā virsotnē vk. Šī īpašība nozīmē, ka grafs ir sakarīgs, t.i. nesatur ar šķautnēm nesavienotus "gabalus" un no katras virsotnes pa šķautnēm var nonākt katrā citā virsotnē.
  2. No saknes v1 uz katru citu virsotni vk ved tikai viens ceļš (path), t.i. kokā sazarotie ceļi nesatiekas.

    Sakņotus kokus parasti uzskata arī par orientētiem. Šķautnēm izvēlas virzienus tā, lai tās visas vestu prom no saknes (t.i. lai no saknes, sekojot orientētajām šķautnēm, varētu nonākt katrā citā grafa virsotnē).

    Matemātikā kokus parasti attēlo augošus no augšas uz leju - sakne ir pašā augšā, zem tās ir bērni, mazbērni, utt. Koka sakni papildus var apzīmēt ar mazu ieejošu bultiņu. Šajā zīmējumā attēloti dažādi koki ar septiņām virsotnēm. Visiem tiem ir sešas šķautnes. Ir spēkā šāds apgalvojums: kokā ar n virsotnēm ir n-1 šķautne.

#pic("App_Graphs_SimpleTrees.gif", "250") Attēls: Koku piemēri

Par virsotnes dziļumu (depth) kokā sauc tās attālumu līdz saknei (pašai saknei dziļums ir 0). Koka dziļums ir lielākais no virsotņu dziļumiem. Zīmējumā attēlotajiem kokiem visiem ir vienāds virsotņu skaits (septiņas), bet to dziļumi būtiski atšķiras - tie ir attiecīgi 6, 3 un 2. Kokus, kuru dziļums ir tuvs virsotņu skaitam kokā sauc par izstīdzējušiem, bet tos, kuru dziļums ir būtiski mazāks par virsotņu skaitu kokā sauc par krūmainiem kokiem. Pirmais no zīmējumā attēlotajiem kokiem ir tipisks izstīdzējis koks, bet pēdējais - tipisks krūmains koks.

Tags:
Created by Kalvis Apsītis on 2008-05-03 14:20
    
This wiki is licensed under a Creative Commons 2.0 license
XWiki Enterprise 6.4 - Documentation