Tree - това е специален случай на графика, най-широко използваният програмиране.
Има доста равностойни определения на дървета, ето някои от тях.
Tree - един свързан граф без цикли.
Tree - свързан графика, в която за N върховете винаги точно N-1 ръбове.
Дърво - графика между всеки два върха има точно един начин.
Е определено по същия начин ориентирани дърво и - като насочена графика, в която между две възли, има не повече от един начин.
Дървото се нарича ограничен свързан граф с линия връх (корен) няма цикли.
За всяка двойка от върховете на дървото - възли - има само един път, така че горната част е удобна за класифициране на степента на отдалеченост от коренът.
Разстоянието до корен връх V0 на върха се нарича ниво ите.
Тъй като на пътя между два възела само тогава. Прилагането на този имот на съседните върхове, можем да заключим, че всеки клон на мост.
При премахването на ребрата маршрут само се прекъсва и броенето е разделена на две подграф.
Вкоренени дърво - е ориентирана дърво, в която могат да бъдат разграничени три топ видове: корена, листата (другия си име: крайни възли) и останалата част на върха (не-терминал); и трябва да бъдат изпълнени две задължителни условия:
листо не излезе, без дъга; други върхове могат да оставят произволен брой дъги;
корена не създава една дъга; за всички останали върхове идва точно една дъга.
Традиционно, математика и природни науки, свързани с него (включително теоретичните програмиране) дървета "растат" с главата надолу: това е направено само за удължаване удобство листа, ако е необходимо. Така, в основата на чертежи дърво е най-горната върха, и листата - най-отдолу.
Предшественикът на върха V - е на върха, от която идва дъгата влизане в горната част на ст. Потомък на връх V - е срещата на върха, която идва дъга, която произтича от връх ст. В тези условия, може да се даде на други определения на понятията корен и листа: в основата нямат прародители, са без листа потомци.
Binary дърво - се корени дърво, така че всеки възел има най-много две деца. В този случай, понякога се говори за ляво и дясно потомък потомък на сегашната среща на върха.
Височината на корена на дървото - максималният брой на дъги, които отделят листата от корена. Ако дървото не е балансиран, а след това си височина - това е просто разстоянието от корена до най-външния лист.
Ърл G (V, X) е дърво, ако и само ако отговаря на поне едно от следните условия:
1. За лесен свързан графика е дърво, е необходимо и достатъчно, че броят на възли е по-голям от броя на ребрата на един.
2. За да граф е дърво, то е необходимо и достатъчно, че всякакви два върха са свързани само с неговия маршрут.
3. Графиката е дърво, ако и само ако добавянето на всеки нов ръб води до точно един цикъл.
4. графиката G (V, X) е свързан и не съдържа цикли.
5. графиката G (V, X) е свързан. но тя губи този имот след отстраняването на който и да е край.
Така че, с п върховете дърво има п-1 ръб, така че ще бъде минимално свързан граф.
Висящи на върха, с изключение на корена, наречена на листата.
Скелетът на свързаната графика е всяко подграф. съдържащ всички върхове на графиката и дърво.
А подграф на G 1 = (V 1, Е 1) на графика G = (В. Е), наречена обхваща дърво
Свързани статии