Medžiai, apėjimas ir rekursinės struktūros

Vienas kelias tarp dviejų kambarių

Septynis kambarius A, B, C, D, E, F, G jungia praėjimai AB, AC, BD, BE, CF ir FG. Norėdami iš D patekti į G neužsukdami į tą patį kambarį antrą kartą, eikite D, B, A, C, F, G. Šiame kelyje pereisite penkis praėjimus. Antro kelio nėra, nebent pridėtumėte praėjimą arba pakartotumėte dalį kelionės.

Pavaizduokite kambarius kaip pažymėtas viršūnes, o praėjimus – kaip briaunas. Svarbu tiksliai nurodyti visas briaunas; nubrėžtų briaunų ilgiai neatspindi ėjimo atstumo. Šis jungusis tinklas neturi ciklų, todėl jis yra medis. Prieš skaitydami įrodymą, numatykite, kas pasikeistų pridėjus trūkstamą praėjimą DG.

Tiksliai apibrėžkite, kas yra medis

Tema „Skaičiavimas, nulis ir natūralieji skaičiai“ parengia viršūnių ir briaunų skaičiavimui; „Sudėtis ir atimtis“ parengia darbui su formulėmis; „Pavyzdžiai, paaiškinimai ir kontrpavyzdžiai“ parengia suprasti skirtumą tarp pavyzdžio ir įrodymo. Visos čia reikalingos grafų ir rekursijos sąvokos apibrėžiamos šioje pamokoje. Skaitydami pirmą kartą, sekite kambarių pavyzdį ir lankymo tvarką, tada grįžkite prie kelio vienatinumo ir rekursinių įrodymų.

Šioje pamokoje naudojami baigtiniai neorientuotieji paprastieji grafai. Jų viršūnių žymenys yra skirtingi. Briauna jungia dvi skirtingas viršūnes, neturi krypties ir pasitaiko ne daugiau kaip vieną kartą. Taigi kilpos ir lygiagrečiosios briaunos neleidžiamos. Viršūnės laipsnis yra jos kaimyninių viršūnių skaičius.

Kelias yra skirtingų viršūnių seka, kurioje kiekvieną gretimų viršūnių porą jungia briauna. Jo ilgis yra šių briaunų skaičius. Vienos viršūnės seka yra nulinio ilgio kelias. Ciklas yra uždara bent trijų briaunų seka, kurios viršūnės yra skirtingos, išskyrus pasikartojančią pradžios ir pabaigos viršūnę.

Čia grafas laikomas jungiu, jei jis turi bent vieną viršūnę ir kiekvieną viršūnių porą jungia kelias. Medis yra jungus grafas be ciklų. Miškas yra bet kuris grafas be ciklų; jis gali būti nejungus, turėti izoliuotų viršūnių arba neturėti nė vienos viršūnės. Jungumo komponentė yra maksimali tarpusavyje keliais sujungtų viršūnių grupė. Tuščiasis miškas turi nulį komponenčių.

Viršūnių skaičių žymėkime n, briaunų skaičių – e, o komponenčių skaičių – c. Vienos viršūnės grafas be briaunų yra medis. Tuščiasis grafas yra miškas, bet pagal nurodytą netuštumo sąlygą nėra medis.

Medyje yra lygiai vienas kelias

Tegu T yra medis. Pasirinkime skirtingas viršūnes u, v. Iš jungumo išplaukia, kad yra bent vienas kelias. Tarkime, kad yra du skirtingi keliai. Eikime jų bendra pradine dalimi iki viršūnės, kurioje jie pirmą kartą išsiskiria. Toliau eikime antruoju keliu, kol jis pirmą kartą grįš į pirmojo kelio viršūnę; tai turi įvykti ne vėliau kaip ties v. Kadangi keliuose viršūnės nesikartoja, grįžti į ankstesnę bendrą pradinę dalį neįmanoma.

Tarp išsiskyrimo ir grįžimo viršūnių antrasis kelias neturi nė vienos vidinės viršūnės, priklausančios pirmajam keliui. Todėl jo atkarpa ir pirmojo kelio atkarpa sudaro ciklą, o tai prieštarauja medžio sąlygai. Taigi kelias yra vienintelis. Pagal mūsų apibrėžimą vienintelis kelias iš viršūnės į ją pačią yra nulinio ilgio kelias.

Atvirkščiai, tarkime, kad netuščiajame baigtiniame paprastajame grafe tarp bet kurių dviejų skirtingų viršūnių yra lygiai vienas kelias. Grafas yra jungus, nes šie keliai egzistuoja. Jei būtų ciklas, tarp dviejų jo viršūnių būtų galima eiti dviem skirtingais keliais aplink ciklą, o tai prieštarautų kelio vienatinumui. Todėl grafas yra medis. Netuštumo sąlyga būtina: tuščiajame grafe nėra nė vienos poros, kuriai būtų galima patikrinti sąlygą, tačiau čia jis nelaikomas medžiu.

Miške tarp vienai komponentei priklausančių viršūnių yra lygiai vienas kelias, o tarp skirtingoms komponentėms priklausančių viršūnių kelio nėra. Tas pats dviejų kelių argumentas atmeta galimybę, kad grafe be ciklų būtų du keliai; kiekvienos komponentės jungumas užtikrina, kad vienas kelias egzistuoja.

Pašalinkite lapą ir suskaičiuokite briaunas

Neorientuotajame grafe lapas yra pirmojo laipsnio viršūnė. Kiekvienas baigtinis medis, turintis bent dvi viršūnes, turi bent du lapus. Norėdami tai įrodyti, pasirinkime kuo ilgesnį kelią; toks kelias egzistuoja, nes grafas yra baigtinis. Kiekviena galinė viršūnė turi kaimynę šiame kelyje. Papildoma kaimynė tame pačiame kelyje sudarytų ciklą, o papildoma kaimynė už jo ribų leistų kelią pratęsti. Abi galimybės neįmanomos, todėl abi galinės viršūnės yra pirmojo laipsnio.

Pašalinkime vieną lapą ir vienintelę jo briauną. Lieka bent viena viršūnė. Kelias tarp dviejų likusių viršūnių negali turėti pašalinto lapo kaip vidinės viršūnės, nes tam reikėtų dviejų su tuo lapu incidentinių briaunų. Todėl pradinis vienintelis kelias tarp šių viršūnių išlieka. Pašalinimas nesukuria ciklo, tad likęs grafas vėl yra medis.

Kartokime, kol liks viena viršūnė. Kaskart pašalinama lygiai viena viršūnė ir viena briauna. Pradėjus nuo n viršūnių, reikia n−1 pašalinimų; galutinis vienos viršūnės grafas neturi briaunų. Todėl kiekviename medyje e = n−1. Šis procesas baigiasi, nes teigiamas viršūnių skaičius mažėja kiekviename žingsnyje, o argumentas apie lapus galioja tol, kol lieka bent dvi viršūnės.

Kiekviena miško jungumo komponentė yra medis. Jei komponenčių viršūnių skaičiai yra n₁,…,n_c, jų briaunų skaičiai yra n₁−1,…,n_c−1. Jų suma yra e = n−c, nes komponentės sudaro visų viršūnių aibės skaidinį. Tai galioja ir tuščiam miškui: n = c = e = 0.

Vien lygybė e = n−1 neįrodo, kad grafas yra medis. Trikampį ir izoliuotą viršūnę turinčiame grafe n = 4, e = 3, tačiau jis turi ciklą ir yra nejungus. Vis dėlto jungiam paprastajam grafui lygybė e = n−1 reiškia, kad jis yra medis: šalinkime ciklų briaunas išlaikydami jungumą, kol liks jungiamasis medis. Tam medžiui jau reikia n−1 briaunų, todėl grafas, turintis tik n−1 briaunų, negalėjo prarasti nė vienos. Kitame skyriuje pagrindžiamas šis šalinimo žingsnis.

Viena briauna pakeičia jungumą arba sukuria vieną ciklą

Pašalinkime iš medžio briauną uv. Jei u ir v liktų sujungtos, išlikęs kelias kartu su uv pradiniame medyje sudarytų ciklą. Taigi jos atskiriamos. Kiekviena viršūnė priklauso vienai iš dviejų taip susidariusių komponenčių: jos pradinis kelias į u arba neina per uv, arba prieš eidamas per uv pasiekia v. Vadinasi, gautas grafas turi lygiai dvi komponentes. Kiekviena yra aciklinė ir jungi, todėl kiekviena yra medis.

Pridėkime prie medžio vieną trūkstamą briauną uv. Pradinis vienintelis kelias iš u į v ir naujoji briauna sudaro ciklą. Bet kuris padidinto grafo ciklas turi eiti per naująją briauną, nes pradinis medis ciklų neturėjo. Pašalinus tą briauną iš tokio ciklo, lieka kelias iš u į v pradiniame medyje; dėl kelio vienatinumo tai turi būti tas pats kelias. Sukurtas lygiai vienas ciklas. Pagal paprastojo grafo sampratą antros briaunos tarp tų pačių viršūnių pridėti negalima.

Jungiojo grafo jungiamasis medis yra pografis, apimantis visas jo viršūnes ir pats esantis medis. Jei jungus baigtinis paprastasis grafas turi ciklą, pašalinkime vieną to ciklo briauną. Likusi ciklo dalis vis dar jungia jos galines viršūnes, todėl bet kurį maršrutą, einantį per pašalintą briauną, galima pakeisti maršrutu, einančiu per kitas ciklo briaunas. Pašalinkime šio maršruto dalis tarp pasikartojančių viršūnių, kad gautume kelią. Jungumas išlieka.

Toliau šalinkime ciklų briaunas. Baigtinis briaunų skaičius mažėja, todėl procesas baigiasi jungiu acikliniu grafu, turinčiu visas pradines viršūnes, – jungiamuoju medžiu. Skirtingi pasirinkimai gali duoti skirtingus jungiamuosius medžius. Šioje pamokoje naudojamos briaunos be svorių ir neteigiama, kad kuris nors konkretus jungiamasis medis minimizuoja sąnaudas.

Šaknis apibrėžia tėvinių ir vaikinių viršūnių ryšius

Pasirinkime vieną viršūnę kaip šaknį. Bet kurios kitos viršūnės tėvinė viršūnė yra prieš ją esanti viršūnė vieninteliame kelyje iš šaknies. Šaknis neturi tėvinės viršūnės. Viršūnės v vaikinės viršūnės yra tos, kurių tėvinė viršūnė yra v. Gylis yra briaunų skaičius kelyje iš šaknies į viršūnę. Kiekviena briauna jungia tėvinę ir vaikinę viršūnes: antraip du keliai iš šaknies ir ta briauna sudarytų ciklą.

Viršūnės v palikuonė yra kita viršūnė, kurios kelias iš šaknies eina per v. Pomedį su šaknimi v sudaro v ir visos jos palikuonės bei jas jungiančios briaunos. Šakninio medžio lapas neturi vaikinių viršūnių. Medyje, turinčiame bent dvi viršūnes, viršūnė, kuri nėra šaknis, yra šakninio medžio lapas tada ir tik tada, kai jos laipsnis lygus vienetui. Pirmojo laipsnio šaknis turi vaikinę viršūnę ir nėra šakninio medžio lapas. Vienintelė medžio viršūnė, kuri yra ir šaknis, neturi vaikinių viršūnių, todėl ji yra šakninio medžio lapas, nors jos laipsnis lygus nuliui.

Kai šaknis yra A, jos vaikinės viršūnės yra B ir C; B turi D ir E; C turi F; F turi G. Gyliai: A:0, B,C:1, D,E,F:2, G:3. Jei šaknimi tampa D, B yra jos vaikinė viršūnė, o A tampa B vaikine viršūne. Neorientuotos briaunos ir viršūnių laipsniai nepasikeitė.

Šaknis nenustato bendrą tėvinę viršūnę turinčių viršūnių tvarkos. Kaimyninėms ir vaikinėms viršūnėms surikiuoti naudojame viršūnių sąrašą A,B,C,D,E,F,G. Šis papildomas susitarimas padaro apėjimo pavyzdžius deterministinius. Kita vaikinių viršūnių tvarka gali duoti kitokią tiesioginio arba atvirkštinio apėjimo seką, nors šakninis medis lieka tas pats.

Apėjimui platyn naudojama eilė

Iš eilės pašalinamas anksčiausiai į ją įtrauktas ir vis dar laukiantis elementas: pirmas įtrauktas, pirmas pašalinamas. Pažymėkite šaknį kaip atrastą ir įtraukite ją į eilę. Pašalinkite pirmąją eilės viršūnę, aplankykite ją ir eilės gale pridėkite kiekvieną dar neatrastą kaimynę sąrašo tvarka, pažymėdami ją kaip atrastą pridėjimo metu. Tęskite, kol eilė ištuštės. Žymėjimas atradimo metu neleidžia tos pačios viršūnės įtraukti į eilę du kartus.

Kambarių medyje, kurio šaknis yra A, aplankymo tvarka yra A,B,C,D,E,F,G. Aplankius A, eilėje laukia B,C. Aplankant B, po C pridedamos D,E; aplankant C, po D,E pridedama F. Aplankant F, galiausiai pridedama G. Taigi viršūnės aplankomos pagal gylius 0,1,2,3.

Kodėl lygiai išlieka iš eilės? Iš pradžių eilėje yra tik nulinio gylio viršūnė. Apdorojant k gylio viršūnę, jos k+1 gylio vaikai pridedami po visų jau laukiančių viršūnių. Todėl visos k gylio viršūnės pašalinamos prieš bet kurią (k+1) gylio viršūnę; tie vaikai sudaro būtent kitą lygį, nes kiekviena medžio viršūnė, išskyrus šaknį, turi vieną tėvinę viršūnę. Tai įrodo lygių tvarką bet kuriame baigtiniame medyje su šaknimi.

Bendruoju atveju grafe šakniai priskirkite lygį 0, o kiekvienai naujai atrastai kaimynei – dabartinės viršūnės lygį, padidintą 1. Ta pati eilės taisyklė leidžia apdoroti priskirtus lygius nemažėjančia tvarka: naujai iš k lygio atrastos kaimynės pridedamos k+1 lygyje po visų jau laukiančių viršūnių. Kiekvienas priskirtas lygis nusako maršrutą, turintį tiek briaunų, todėl jis negali būti mažesnis už mažiausią kelio ilgį. Atvirkštinę nelygybę pagrįskite nuosekliai pagal mažiausią atstumą: viršūnė, esanti atstumu d, trumpiausiame kelyje turi ankstesnę viršūnę, esančią atstumu d−1. Ši ankstesnė viršūnė apdorojama prieš lygius, didesnius už d−1, todėl nagrinėjama viršūnė atrandama ne didesniame kaip d lygyje. Pradinis atvejis yra šaknis. Taigi priskirtas lygis lygus mažiausiam briaunų skaičiui. Tas pats argumentas rodo, kad pasiekiama kiekviena šaknies jungumo komponentės viršūnė; jokia apėjimo briauna negali išeiti už tos komponentės ribų. Nejungiajame grafe kiekvienai likusiai komponentei reikia naujos, dar neatrastos šaknies. Šių brėžinių geometriniai ilgiai nėra briaunų svoriai.

Apėjimo gilyn aplankymo tvarka ir tikrasis maršrutas skiriasi

Norėdami apeiti medį su šaknimi tiesiogine tvarka, aplankykite jo šaknį, tada nurodyta tvarka apeikite kiekvieno vaiko pomedį. Taikydami atvirkštinę tvarką, pirmiausia apeikite vaikų pomedžius, tada aplankykite šaknį. Rekursija reiškia tos pačios procedūros taikymą mažesniam pomedžiui. Lapas neturi vaikų, kuriems būtų iškviečiama procedūra, todėl jame procedūra baigiasi. Kiekvienas iškvietimas taikomas griežtai mažesniam baigtiniam pomedžiui, todėl procesas baigiasi.

Kai šaknis yra A ir laikomasi sąrašo tvarkos, tiesioginė tvarka yra A,B,D,E,C,F,G. Atvirkštinė tvarka yra D,E,B,G,F,C,A. Kiekviena viršūnė aplankoma lygiai vieną kartą, nes vaikų pomedžiai nesikerta ir kartu su savo tėvine viršūne sudaro visą jos pomedį. Tiesioginėje tvarkoje kiekvienas protėvis eina prieš savo palikuonis; atvirkštinėje tvarkoje kiekvienas palikuonis eina prieš savo protėvį.

Nė vienas iš šių sąrašų nebūtinai yra grafo kelias. D ir E yra gretimi tiesioginės tvarkos įrašai, tačiau jos nėra gretimos viršūnės. Tikrasis apėjimo gilyn maršrutas briaunomis, baigus apeiti kiekvieno vaiko pomedį, grįžta briauna į tėvinę viršūnę. Čia jis yra A,B,D,B,E,B,A,C,F,G,F,C,A. Viršūnės kartojasi, todėl tai maršrutas, o ne kelias.

Šis visas maršrutas kiekvieną medžio briauną pereina vieną kartą į vaiko pomedį ir vieną kartą atgal. Briaunų yra e = n−1, todėl maršrutą sudaro 2(n−1) perėjimų briaunomis; šiame pavyzdyje jų yra 12. Šis skaičius taikomas visam maršrutui, grįžtančiam į šaknį, o ne paieškai, kuri baigiama anksčiau. Bendruoju atveju grafe saugokite atrastų viršūnių aibę, kad išvengtumėte ciklų; rekursiniai iškvietimai seka atradimo briaunomis, užuot pakartotinai sekę visomis kaimynėmis.

Sujunkite nesikertančius vaikų pomedžius

Apibrėžkite S(v) kaip viršūnių skaičių pomedyje, kurio šaknis yra v, įskaitant v. Apibrėžkite H(v) kaip didžiausią briaunų skaičių nuo v iki to pomedžio lapo, nustatyto pagal šaknį. Lapui S(v) = 1 ir H(v) = 0.

Bet kuriai viršūnei v, S(v) = 1+Σ S(w), kur sumuojama per jos vaikus w. Simbolis Σ reiškia, kad kiekvienam nurodytam vaikui pridedamas vienas dėmuo; jei vaikų nėra, suma lygi nuliui. Vaikų pomedžiai neturi bendrų viršūnių: jei turėtų, iš bendros viršūnės į v vestų du skirtingi keliai. Kiekvienas palikuonis priklauso lygiai vienam iš šių vaikų pomedžių. Taip įrodoma dydžio formulė, nieko nesuskaičiuojant dukart.

Viršūnei v, kuri nėra lapas, H(v) = 1+max H(w), kur maksimumas imamas per jos vaikus. Kiekvienas kelias į lapą palikuonį pirmiausia eina viena briauna į vaiką, o tada keliu to vaiko pomedyje; pasirinkus aukščiausią vaiko pomedį, gaunamas didžiausias ilgis. Tuščio sąrašo maksimumas nenaudojamas: lapo atvejis apibrėžiamas atskirai.

Kambarių medyje, kurio šaknis yra A, B pomedžio dydis yra 3, o aukštis – 1; C pomedžio dydis yra 3, o aukštis – 2. Todėl S(A) = 1+3+3 = 7, o H(A) = 1+max(1,2) = 3. F dydis yra 2, o aukštis – 1. Atvirkštinio apėjimo metu kiekvieno vaiko rezultatas apskaičiuojamas anksčiau, nei jo prireikia tėvui.

Struktūra, kurioje yra bendras vaikas, neatitinka šio šakninio medžio modelio. Skaičiuojant abi vaikines struktūras, bendras objektas gali būti suskaičiuotas dukart. Dėl ciklo rekursinė procedūra be patikrų gali grįžti prie dar neužbaigto kvietimo. Argumentai apie nesikertančius pomedžius ir mažėjantį dydį paaiškina, kodėl medžio prielaidos yra svarbios.

Reiškinys suteikia prasmę sutvarkytam medžiui

Reiškinio (2+3)·(7−4) medžio šaknyje yra daugyba, kairysis vaikas yra sudėtis, o dešinysis – atimtis. Skaitiniai lapai saugo savo reikšmes. Operatoriaus viršūnė sujungia sutvarkytų vaikų reikšmes. Atliekant atimtį, kairės ir dešinės tvarka svarbi: 7−4 = 3, o 4−7 = −3.

Atvirkštinio apėjimo seka yra 2,3,+,7,4,−,×. Prieš atlikdami daugybą 5·3 = 15, apskaičiuokite 2+3 = 5 ir 7−4 = 3. Tai rekursinis skaičiavimas: kiekvieno rezultato teisingumas įrodomas remiantis jau apskaičiuotomis vaikų reikšmėmis ir operatoriaus apibrėžimu. Baigtinis medis užtikrina, kad skaičiavimas baigsis, o vietiniai aritmetiniai veiksmai apibrėžia rezultatą.

Sutvarkyto dvejetainio medžio viršūnė turi ne daugiau kaip du vaikus, kuriems skirtos kairioji ir dešinioji pozicijos. Ankstesnės dydžio ir aukščio formulės leidžia bet kokį vaikų skaičių. Vidurinis apėjimas yra dar vienas sutvarkytų dvejetainių medžių apėjimo būdas, o ne tvarka, savaime priskiriama kiekvienam neorientuotam medžiui.

Numatykite ir patikrinkite visą įrašą

Palyginkite vienintelio kelio, pridėtos briaunos ir pašalintos briaunos atvejus. Tada pakeiskite šaknį arba atskleiskite pradines lankymo sekos atkarpas. Išsamiose lentelėse išsaugomas tikrasis briaunų sąrašas, komponentės ir šakninė struktūra, kad brėžinys negalėtų nepastebimai pridėti jungties.

Rekursiniais atvejais numatykite pasirinkto pomedžio dydį ir aukštį prieš juos atskleisdami. Reiškinio atveju numatykite pasirinkto operatoriaus rezultatą ir išlaikykite jo vaikų tvarką. Baigtinis modelis iliustruoja pirmiau pateiktus bendruosius įrodymus; vien visų pateiktų atvejų patikrinimas neįrodytų teoremos kiekvienam medžiui.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Pagal šioje pamokoje taikomus susitarimus nustatykite, kaip klasifikuojamas grafas su viena viršūne ir be briaunų bei grafas be viršūnių.

   Rodyti atsakymą ir paaiškinimą

   Grafas su viena viršūne yra medis ir miškas. Tuščiasis grafas yra miškas, bet nėra medis.

   Grafas su viena viršūne yra netuščias, jungus ir aciklinis. Tuščiasis grafas yra aciklinis, bet neatitinka aiškiai nurodytos sąlygos būti netuščiam ir jungiam; jis turi nulį komponenčių.

2. Paprastasis grafas turi keturias viršūnes ir tris briaunas. Ar jis būtinai yra medis?

   Rodyti atsakymą ir paaiškinimą

   Ne. Trikampis kartu su izoliuota viršūne turi tiek pat viršūnių ir briaunų.

   Jis turi ciklą ir dvi komponentes. Formulė e = n−1 galioja, jei grafas yra medis, tačiau be jungumo sąlygos vien ši formulė nereiškia, kad grafas yra medis.

3. Baigtinis miškas turi 12 viršūnių ir keturias komponentes. Kiek jis turi briaunų?

   Rodyti atsakymą ir paaiškinimą

   Jis turi 12−4 = 8 briaunų.

   Kiekviena netuščia komponentė, turinti nᵢ viršūnių, turi nᵢ−1 briaunų. Sumuojant atimama po vieną už kiekvieną iš keturių komponenčių, įskaitant ir kiekvieną izoliuotą viršūnę.

4. Jei viena briauna sujungia viršūnes, esančias dviejose skirtingose miško komponentėse, ar susidaro ciklas? Kaip pasikeičia komponenčių ir briaunų skaičius?

   Rodyti atsakymą ir paaiškinimą

   Ciklas nesusidaro; komponenčių skaičius sumažėja vienetu, o briaunų skaičius padidėja vienetu.

   Kad susidarytų ciklas su naująja briauna, tarp jos galinių viršūnių jau turėtų būti kelias, tačiau jos buvo skirtingose komponentėse. Sujungta komponentė yra medis; miško formulė tebegalioja.

5. Koks ciklas susidaro pridėjus briauną DE prie kambarių medžio?

   Rodyti atsakymą ir paaiškinimą

   D,B,E,D yra vienintelis naujas ciklas, turintis tris briaunas.

   Pradinis kelias iš D į E yra D,B,E. Naujoji briauna uždaro šį kelią. Kelio vienatinumo argumentas atmeta bet kokio kito ciklo galimybę.

6. Jei D yra kambarių medžio šaknis, ar D yra šakninio medžio lapas? Ar ji yra neorientuoto medžio lapas?

   Rodyti atsakymą ir paaiškinimą

   D yra neorientuoto medžio lapas, bet nėra šakninio medžio lapas.

   Jos laipsnis neorientuotame medyje išlieka lygus vienetui. Jos kaimynė B tampa jos vaiku, taigi ji turi vaiką. Šiuose dviejuose lapo apibrėžimuose taikomos skirtingos sąlygos.

7. Kodėl A,B,D,E,C,F,G nėra kelias kambarių medyje?

   Rodyti atsakymą ir paaiškinimą

   Gretimi įrašai D ir E nėra sujungti briauna; taip pat nėra sujungti E ir C.

   Tai lankymo tiesiogine tvarka sąrašas. Tikrojo ėjimo metu tarp šių vaikinių pomedžių grįžtama per B ir A, todėl viršūnės aplankomos pakartotinai.

8. Ar apeinant kambarių medį, kurio šaknis yra A, atvirkštine tvarka A galėtų būti aplankyta prieš G?

   Rodyti atsakymą ir paaiškinimą

   Ne. G yra A palikuonė ir turi būti aplankyta pirmiau.

   Apeinant atvirkštine tvarka, kiekvienas vaikinis pomedis baigiamas apeiti prieš aplankant jo tėvinę viršūnę. Taikant šią taisyklę išilgai G, F, C, A, G būtinai aplankoma prieš A, nepriklausomai nuo tos pačios tėvinės viršūnės vaikų eilės.

9. Medis turi devynias viršūnes. Kiek žingsnių briaunomis atliekama per visą ėjimą gilyn, kai grįžtama į pradinę šaknį?

   Rodyti atsakymą ir paaiškinimą

   Atliekama 2(9−1) = 16 žingsnių briaunomis.

   Medis turi aštuonias briaunas. Per visą ėjimą kiekviena briauna pereinama vieną kartą vaikinio pomedžio link ir vieną kartą atgal. Tai nėra pirmųjų apsilankymų skaičius, kuris lygus devyniems.

10. Viršūnės vaikinių pomedžių dydžiai yra 2,4,1, o aukščiai – 1,2,0. Raskite šios viršūnės pomedžio dydį ir aukštį.

    Rodyti atsakymą ir paaiškinimą

    Jo dydis yra 1+2+4+1 = 8, o aukštis – 1+max(1,2,0) = 3.

    Tėvinė viršūnė skaičiuojama vieną kartą, o nesikertančių vaikinių pomedžių dydžiai sudedami. Aukštis nustatomas pagal ilgiausią vaikinę šaką, o ne sudedant visus aukščius.

11. Kaip pasikeičia reiškinio reikšmė, jei atimties mazgo vaikai 7 ir 4 sukeičiami vietomis?

    Rodyti atsakymą ir paaiškinimą

    Naujoji reikšmė yra (2+3)·(4−7) = −15.

    Atimties pomedžio reikšmė pasikeičia iš 3 į −3; tada daugyba duoda 5·(−3). Brėžinys, kuriame vaikų tvarka nenustatyta, negali nurodyti nekomutatyvaus operatoriaus vaikų tvarkos.

Ką verta įsidėmėti

• Medis yra netuščias baigtinis jungus beciklis paprastasis neorientuotasis grafas; lygiavertiškai – netuščias baigtinis paprastasis neorientuotasis grafas, kuriame tarp kiekvienos skirtingų viršūnių poros yra lygiai vienas kelias.
• Medis turi e = n−1 briaunų; miškas su c komponentėmis turi e = n−c. Vien briaunų skaičius neįrodo, kad grafas yra medis.
• Pašalinus medžio briauną, susidaro dvi komponentės; pridėjus trūkstamą briauną, susidaro lygiai vienas ciklas.
• Šaknis apibrėžia tėvus, gylius ir pomedžius, o papildomai nustatyta vaikų tvarka vienareikšmiškai apibrėžia apėjimo sekas.
• Apeinant į plotį naudojama eilė ir judama pagal gylį. Tiesiogine tvarka pirmiausia aplankomas tėvas; atvirkštine tvarka jis aplankomas po savo palikuonių.
• Aplankytų viršūnių sąrašas nebūtinai yra grafo kelias. Visas ėjimas į gylį, grįžtant į pradžią, kiekviena briauna eina du kartus.
• Nesikertantys vaikų pomedžiai pagrindžia rekursinį dydžio ir aukščio skaičiavimą bei reiškinio reikšmės skaičiavimą pagal nustatytą tvarką; bendras vaikas arba ciklas pakeičia samprotavimą.