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

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۲۷ فوریهٔ ۲۰۱۰، ساعت ۲۰:۰۱

برای دیگر معانی درخت به درخت (ابهام‌زدایی) نگاه کنید.

در نظریهٔ گراف، درخت گرافی همبند و بدون دور است. درخت ها به طور گسترده در علوم رایانه و ساختار داده‌ها کاربرد دارند. مثل درخت‌های جستجوی دودویی، پشته‌ها^[۱]، درخت‌های هافمن^[۲] برای فشرده‌سازی اطلاعات و غیره.

تعاریف

در اینجا بدلیل وجود یک دور گراف درخت نمی‌باشد.

درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:

G متصل است و دور ندارد.
G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود می‌آید.
G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست.
G متصل است و گراف کامل 3 رأسی $K_{3}$ جزِئی از آن نیست.
هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.

اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:

G متصل است و n-1 یال دارد.
G مدار ساده ندارد و n-1 یال دارد.

گراف سادهٔ بدون جهت G را جنگل^[۳] گوئیم اگر مسیر ساده نداشته باشد.

درخت جهت‌دار^[۴] گراف جهت‌داری است که گراف زمینه آن یک درخت باشد.

یک درخت را ریشه‌دار^[۵] گوییم اگر راسی داشته باشد که به ازای هر راس دیگر درخت، مسیری از آن به راس مذکور وجود داشته باشد. مرتبهٔ درخت^[۶] یک مرتب‌سازی جزئی^[۷] روی رئوس درخت است که $u\leq v$ اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال^[۸] گوییم اگر انتهای هر یال G با این رتبه بندی قابل مقایسه باشد ( Diestel 2005 ,p.15 ).

درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزاد^[۹] گوییم.

درخت چندگانه^[۱۰] درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.

درخت برچسب دار^[۱۱] درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...وn برچسب گذاری می‌شوند. درخت بازگشتی^[۱۲] یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود.( اگر $u<v$ و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است. )

درخت ساده نشدنی^[۱۳] درختی است که رأسی با درجهٔ 2 ندارد.

درخت مرتب^[۱۴] درختی است که برای فرزندان هر رأس مرتبه‌ای تعیین شده باشد.

درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.

درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر سادهٔ یکتا که رأس 2 را به 6 وصل می‌کند 6-5-4-2 است.

احکام

هر درخت یک گراف دو بخشی^[۱۵] و یک گراف میانه^[۱۶] است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
هر درخت با $n\leq 2$ حداقل 2 برگ ( یا رأس با درجه 1)دارد. حداقل تعداد برگ مربوط به گراف مسیر^[۱۷] و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره‌ای است.

منابع

.Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
Otter, Richard (1948), “The Number of Trees”, Annals of Mathematics, Second Series 49 (3): 583–599

پاورقی

↑ Heaps
↑ Huffman trees
↑ forest
↑ Directed tree
↑ Rooted tree
↑ tree-order
↑ partial ordering
↑ Normal tree
↑ Free tree
↑ Polytree
↑ Labeled tree
↑ Recursive tree
↑ irreducible tree
↑ Ordered tree
↑ bipartite graph
↑ Median graph
↑ Path graph

[1] Heaps

[2] Huffman trees

[3] rest

[4] Directed tree

[5] Rooted tree

[6] tree-order

[7] rtial ordering

[8] Normal tree

[9] Free tree

[10] Polytree

[11] Labeled tree

[12] Recursive tree

[13] rreducible tree

[14] Ordered tree

[15] rtite graph

[16] Median graph

[17] Path graph

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۱۶]

[۱۷]

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