Գրաֆիկների տեսության մեջ ծառը չուղղորդված գրաֆիկ է, որում ցանկացած երկու գագաթ միացված է ճիշտ մեկ ճանապարհով, կամ համարժեք միացված ացիկլիկ չուղղորդված գրաֆիկով: … Բազմանտառը (կամ ուղղորդված անտառը կամ կողմնորոշված անտառը) ուղղորդված ացիկլիկ գրաֆիկ է, որի հիմքում ընկած չուղղորդված գրաֆիկը անտառ է:
Ի՞նչ են ուղղորդված և չուղղորդված ծառերը:
Առանց ցիկլերի չուղղորդված գրաֆիկը անտառ է, և եթե այն կապված է, կոչվում է ծառ: Ուղղորդված գրաֆիկը անտառ է (կամ ծառ), եթե բոլոր եզրերը վերածվում են չուղղորդված եզրերի, այն անուղղորդված անտառ է (կամ ծառ): Արմատավորված ծառը ծառ է, որի մեկ գագաթը նշանակված է որպես արմատ:
Ինչու են ծառերը անուղղորդված:
Թեորեմ. չուղղորդված գրաֆիկը ծառ է, եթե յուրաքանչյուր զույգ գագաթների միջև կա ուղիղ մեկ պարզ ճանապարհԱպացույց. Եթե մենք ունենք T գրաֆիկ, որը ծառ է, ապա այն պետք է կապված լինի առանց ցիկլերի: Քանի որ T-ը միացված է, յուրաքանչյուր զույգ գագաթների միջև պետք է լինի առնվազն մեկ պարզ ճանապարհ:
Ի՞նչ է նշանակում ուղղորդված ծառ:
Ուղղորդված ծառը ացիկլիկ ուղղորդված գրաֆիկ է Այն ունի մեկ հանգույց 1-ին աստիճանով, մինչդեռ մյուս բոլոր հանգույցներն ունեն 1-ին աստիճան, ինչպես ցույց է տրված նկ. կոչվում է արտաքին հանգույց կամ տերմինալ հանգույց կամ տերեւ: Այն հանգույցները, որոնք ունեն մեկից մեծ կամ հավասար աստիճան, կոչվում են ներքին հանգույց:
Ինչպե՞ս որոշել, որ չուղղորդված գրաֆիկը ծառ է:
Չուղղորդված գրաֆիկների դեպքում մենք կատարում ենք երեք քայլ՝
- Կատարեք DFS ստուգում ցանկացած հանգույցից՝ համոզվելու համար, որ յուրաքանչյուր հանգույց ունի ճիշտ մեկ ծնող: Եթե ոչ, վերադարձեք.
- Ստուգեք, որ բոլոր հանգույցներն այցելված են: Եթե DFS ստուգումը չկարողացավ այցելել բոլոր հանգույցները, ապա վերադարձեք.
- Հակառակ դեպքում, գրաֆիկը ծառ է:
