გრაფების თეორიაში ხე არის მიმართული გრაფიკა, რომელშიც ნებისმიერი ორი წვერო დაკავშირებულია ზუსტად ერთი ბილიკით, ან ექვივალენტურად დაკავშირებული აციკლური არამიმართული გრაფიკით. … პოლიტყე (ან მიმართული ტყე ან ორიენტირებული ტყე) არის მიმართული აციკლური გრაფიკი, რომლის ფუძემდებლური არამიმართული გრაფიკა არის ტყე.
რა არის მიმართული და არამიმართული ხეები?
მიმართული გრაფიკი ციკლების გარეშე არის ტყე და თუ ის დაკავშირებულია მას უწოდებენ ხეს. მიმართული გრაფიკი არის ტყე (ან ხე), თუ როდესაც ყველა კიდე გარდაიქმნება არამიმართულ კიდეებად, ეს არის არამიმართული ტყე (ან ხე). დაფესვიანებული ხე არის ხე, რომელსაც ერთი წვერო აქვს ფესვად განსაზღვრული.
რატომ არის ხეები მიუმართავი?
თეორემა: მიუმართავი გრაფიკი არის ხე, თუ არის ზუსტად ერთი მარტივი გზა წვეროების თითოეულ წყვილს შორისდადასტურება: თუ გვაქვს გრაფიკი T, რომელიც არის ხე, მაშინ ის უნდა იყოს დაკავშირებული ციკლების გარეშე. ვინაიდან T დაკავშირებულია, უნდა არსებობდეს მინიმუმ ერთი მარტივი გზა წვეროების თითოეულ წყვილს შორის.
რას ნიშნავს მიმართული ხე?
მიმართული ხე არის აციკლური მიმართული გრაფიკი მას აქვს ერთი კვანძი 1 გრადუსით, ხოლო ყველა სხვა კვანძს აქვს ხარისხი 1, როგორც ნაჩვენებია ნახზე: კვანძი, რომელსაც აქვს 0 ხარისხის ეწოდება გარე კვანძი ან ტერმინალური კვანძი ან ფოთოლი. კვანძებს, რომლებსაც აქვთ ერთზე მეტი ან ტოლი ხარისხი, ეწოდება შიდა კვანძი.
როგორ გავიგოთ, რომ არამიმართული გრაფიკი არის ხე?
მიმართული გრაფიკების შემთხვევაში ჩვენ ვასრულებთ სამ ნაბიჯს:
- შეასრულეთ DFS შემოწმება ნებისმიერი კვანძიდან, რათა დარწმუნდეთ, რომ თითოეულ კვანძს აქვს ზუსტად ერთი მშობელი. თუ არა, დაბრუნდით.
- შეამოწმეთ, რომ ყველა კვანძი მონახულებულია. თუ DFS შემოწმებამ ვერ შეძლო ყველა კვანძის მონახულება, მაშინ დაბრუნდით.
- წინააღმდეგ შემთხვევაში, გრაფიკი არის ხე.
