درخت (نظریه گراف): تفاوت میان نسخه‌ها

جز
ربات: ویرایش جزئی
(T_3 فاقد شرط فوق است. باید محدود شود.)
جز (ربات: ویرایش جزئی)
[[پرونده:Tree2.png|thumb|200px|left|در اینجا بدلیل وجود یک دور گراف درخت نمی‌باشد.]]
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
* G متصل است و دور ندارد.
* G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود می‌آید.
* G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست.
* G متصل است و گراف کامل 3 رأسی <math>K_3</math> جزِئی از آن نیست.
* هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.
 
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
 
* G متصل است و n-1 یال دارد.
* G مدار ساده ندارد و n-1 یال دارد.
گراف سادهٔ بدون جهت G را جنگل<ref>forest</ref> گوئیم اگر مسیر ساده نداشته باشد.
 
 
== احکام ==
* هر درخت یک گراف دو بخشی<ref>bipartite graph</ref> و یک گراف میانه<ref>Median graph</ref> است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
* هر درخت با <math>n\le 2</math> حداقل 2 برگ ( یا رأس با درجه 1)دارد. حداقل تعداد برگ مربوط به گراف مسیر<ref>Path graph</ref> و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره‌ای است.
 
== منابع ==
۱۸۶٬۰۵۸

ویرایش