Se presupune că graficul G = (V, E) îndeplinește condițiile din definiția 10.2. Se arată prin inducție numărul de vârfuri | V |. asta.
Dacă | V | = 1. atunci vârful unic este prin proprietatea (1) rădăcina copacului, adică în acest grafic nu există margini :. Apoi.
Să presupunem că fiecare grafic c <= n вершинами, удовлетворяющий определению 10.2 входит в . Пусть граф G=(V,E) с (n+1) -й вершиной удовлетворяет условиям определения 10.2. По условию (1) в нем имеется вершина - корень r0. Пусть из r0 выходит k ребер и они ведут в вершины r1. rk (k>= 1). Indicăm prin Gi, (i = 1. k) graficul. Inclusiv nodurile și marginile lor de legătură. Este ușor de observat că Gi îndeplinește condițiile condițiilor din definiția 10.2. Într-adevăr, ri nu include margini; acest vârf este rădăcina lui Gi. În fiecare din celelalte puncte ale lui Vi există o margine, ca în G. Dacă, atunci este accesibilă de la rădăcina ri prin definirea graficului Gi. Deoarece | Vi | <= n. то по индуктивному предположению . Тогда граф G получен по индуктивному правилу (2) определения 10.3 из деревьев G1. Gk и поэтому принадлежит классу .
Dacă un grafic G = (V, E) aparține unei clase, atunci este ușor să se stabilească condițiile (1) - (3) din definiția 10.2 pentru aceasta prin inducție prin definiția 10.2. Lăsăm acest lucru cititorului ca un exercițiu.
O terminologie bogată este asociată cu arbori orientați, provenind din două surse: botaniști și zone de relații de familie.
Root - acesta este singurul vârful care nu include coaste, frunze - este partea de sus, care nu lasă coaste. Calea de la rădăcină la frunză este numită ramura copacului. Înălțimea copacului este maximul lungimilor ramurilor sale. Adâncimea vârfului este lungimea căii de la rădăcină până la acest vârf. Pentru un vârf, subgraful unui arbore este T = (V, E). care cuprinde toate accesibile de la vârf v și nervurile conectarea lor forme de E. Tv subramificație înrădăcinate arbore T v (cm. problema 10.3). Înălțimea vârfului v este înălțimea copacului Tv. Un grafic care reprezintă unirea mai multor arbori disociați se numește o pădure.
Dacă o margine de la vârful v duce la vârful w. atunci v este numit tatăl lui w. și w este fiul lui v (recent o pereche de termeni asexuali este folosită în literatura angolingvă: părinte-copil). Rezultă direct din definiția unui copac că pentru fiecare vârf, cu excepția rădăcinii, există un tată unic. Dacă din punctul vertex v ajunge calea spre vârful w. atunci v este numit strămoș al lui w. și w este descendent al v. Vârfurile, în care tatăl comun, se numesc frați sau surori.
Dați-ne o singură clasă de grafice, generalizând copacii aciclice orientați spre copaci. Două tipuri de astfel de grafice marcate vor fi utilizate ulterior pentru a reprezenta funcțiile Boolean. Aceste grafice pot fi mai multe rădăcini - topuri, care nu sunt incluse în coaste, și fiecare nod poate include mai multe coaste, mai degrabă decât una, ca în copaci.
Articole similare
Trimiteți-le prietenilor: