Qrafik nəzəriyyəsində ağac istənilən iki təpənin tam bir yolla birləşdirildiyi istiqamətsiz qrafikdir və ya ekvivalent olaraq bağlı asiklik yönləndirilməmiş qrafikdir. … Çox meşə (və ya istiqamətləndirilmiş meşə və ya istiqamətlənmiş meşə) əsas istiqamətləndirilməmiş qrafiki meşə olan istiqamətlənmiş asiklik qrafikdir.
İstiqamətli və istiqamətsiz ağaclar nədir?
Dövrü olmayan istiqamətləndirilməyən qrafik meşə və əgər o, bağlıdırsa, ona ağac deyilir. Bütün kənarları yönləndirilməyən kənarlara çevrildikdə istiqamətsiz meşə (və ya ağac) olarsa, istiqamətləndirilmiş qrafik meşə (və ya ağac) sayılır. Köklü ağac kök kimi təyin edilmiş bir təpəsi olan ağacdır.
Ağaclar niyə istiqamətsizdir?
Teorem: İstiqamətsiz qrafik ağacdır, əgər hər təpə cütü arasında bir sadə yol varsaSübut: Əgər ağac olan T qrafikimiz varsa, o zaman dövrlər olmadan bağlanmalıdır. T birləşdirildiyi üçün hər təpə cütü arasında ən azı bir sadə yol olmalıdır.
Yönləndirilmiş ağac dedikdə nə nəzərdə tutulur?
İstiqamətləndirilmiş ağac asiklik yönləndirilmiş qrafikdir Onun dərəcəsi 1 olan bir qovşaq var, digər bütün qovşaqların isə Şəkildə göstərildiyi kimi 1 dərəcəsi var: Dərəcəsi 0 olan qovşaq xarici node və ya terminal node və ya yarpaq adlanır. Dərəcəsi birdən böyük və ya ona bərabər olan qovşaqlar daxili qovşaq adlanır.
İstiqamətsiz qrafikin ağac olduğunu necə müəyyən etmək olar?
İstiqamətsiz qrafiklər vəziyyətində üç addım yerinə yetiririk:
- Hər bir qovşaqda dəqiq bir valideyn olduğundan əmin olmaq üçün istənilən qovşaqdan DFS yoxlanışı həyata keçirin. Yoxdursa, qaytarın.
- Bütün qovşaqların ziyarət edildiyini yoxlayın. DFS yoxlanışı bütün qovşaqları ziyarət edə bilmədisə, geri qayıdın.
- Əks halda, qrafik ağacdır.
