درخت (نظریه گراف): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز حذف رده «درخت‌ها (نظریه گراف)» (با استفاده از رده‌ساز) |
←تعاریف: +pic |
||
خط ۶:
== تعاریف ==
[[تصویر:Tree1.png|thumb|200px|left|نمونه‌ای از یک درخت]]
[[تصویر:Tree2.png|thumb|200px|left|در اینجا بدلیل وجود یک دور گراف درخت نمی‌باشد.]]
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
*G متصل است و دور ندارد.
*G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود
*G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست.
*G متصل است و گراف کامل 3 رأسی <math>K_3</math> جزِئی از آن نیست.
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
سطر ۱۹ ⟵ ۲۱:
گراف سادهٔ بدون جهت G را جنگل<ref>forest</ref> گوئیم اگر مسیر ساده نداشته باشد.
[[درخت جهت‌دار]]<ref>Directed tree</ref> گراف جهت‌داری است که اگر جهت روی
یک درخت را ریشه‌دار<ref>Rooted tree</ref> گوییم اگر یک رأس در آن ریشه باشد. مرتبه ی درخت<ref>tree-order</ref> یک [[مرتب‌سازی جزئی]]<ref>partial ordering</ref> روی رئوس درخت است که <math>u\le v</math> اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال<ref>Normal tree</ref> گوییم اگر انتهای هر یال G با این رتبه بندی قابل مقایسه باشد ( Diestel 2005 ,p.15 ).
درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض
درخت چندگانه<ref>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.
درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...وn برچسب گذاری
درخت ساده نشدنی<ref>irreducible tree</ref> درختی است که رأسی با درجه ی 2 ندارد.
درخت مرتب<ref>Ordered tree</ref> درختی است که برای فرزندان هر رأس
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده ی یکتا که رأس 2 را به 6 وصل
==احکام==
| |||