Orientált fák - studopediya
Definíció. Orientált fát (vagy ortree) egy irányított gráf, egyáltalán nem rendelkezik ciklusokkal csúcsa egy kivételével, tartalmaz pontosan egy ív. Csak a csúcsa az ív, amely csak akkor jön ki, az úgynevezett gyökér a fa. A többi fa tetején nevezzük csomópontokat.
A definíció egy fa, ebből következik, hogy az egyetlen módja, hogy root csatlakoztatott más csúcsa a fa.
Ábra. 5. ábra diagramjai összes nem izomorf orientált fa három és négy csúcsot.
Jóváhagyása. Minden fa is célzott.
Bizonyítás. Mi választjuk ki egy tetszőleges csúcsot és a fák, és rendelje hozzá a root. Élek incidens és a tetején. orient a felső és. Ezután ismételje meg az eljárást: belépő v csúcs ívben, irányítja az összes többi éle incidens a vertex v. fentről v. Mivel a fa nincs ciklus, a tájékozódás a bordák nem vezet ellentmondáshoz.
Ábra. A 6. ábra egy példa a irányított fa. A tetején a kiválasztott gyökér jelzi dupla kör.
Kiválasztása a gyökér egyértelműen meghatározza a tájékozódás a fa. Ezért minden fa p csúcsok megfelelnek az o-orientált fák.
Ortree terminális csúcsot nevezzük levél. Az útvonal a gyökértől levél egy ága. Hossza a leghosszabb ág ortree úgynevezett magasság ortree. A távolság a gyökér, hogy egy bizonyos szintet csúcsoknak nevezzük csúcsot. gyökér maga is egy szinten az egyik szint 0. A csúcsok alkotnak egy fa réteg.
A csúcsok megközelíthető a csúcs. úgynevezett leszármazottai a felső és. Ha van egy ív a fán. a felső és felső nevezik az apa v. és v csúcs hívják a fia a felső és. Sons egy apa nevezett testvéreit.
Megjegyzés. Amikor a kép-orientált fák úgy döntött, hogy a gyökér a tetején és az összes nyíl ívek orientált fentről lefelé, ami feleslegessé teszi, hogy képviselje a nyilakat.
Ábra. A 7. ábra egy fa a rizst. 6, a kép szerint ezeket a szabályokat. A fa tetején osztott 4 szintek. Zero tier tartalmazza a gyökér a fa. Az első és második szintek 4 csúcsa, egy harmadik lépcsőt 8 csúcsa.