المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:گراف:ویژگی های درخت

ویژگی درخت

  • هر درخت یک گراف دو بخشی(bipartite graph) و یک گراف میانه (Median graph) است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
  • هر درخت با$2$ ≤ $n$حداقل $2$ برگ ( یا رأس با درجه $1$)دارد. حداقل تعداد برگ مربوط به گراف مسیر (Path graph) و حداکثر تعداد برگ (n - 1) مربوط به گراف ستاره‌ای است.
  • دو سر هر طولانی ترین مسیر در درخت برگ است.
  • هر یال درخت یک یال برشی است.
  • در هر درختی که ماکزیمم درجه آن $Δ$ باشد ، تعداد برگ های آن حداقل $Δ$ است.
  • در درخت ها اگر یک یال به آن ها اضافه شود ، حتما یک مدار ساده در آن بوجود می‌آید.
  • هر دو راسی در درخت با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.

ابزار صفحه