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

بدون خلاصۀ ویرایش
(!!)
بدون خلاصۀ ویرایش
 
[[پرونده:Tree graph.svg|left]]
در [[نظریهٔ گراف]]، '''درخت''' گرافی استهمبند که هر دو [[رأس]] آن با دقیقا یک [[مسیر]] به همو متصلبدون شده است. همچنین، هر گراف [[متصل]] که [[مدار]] نداشته باشد یک درخت است. جنگل، اجتماع چندین درختدور است. درخت ها به طور گسترده در [[علوم کامپیوتررایانه]] و [[ساختار داده‌ها]] کاربرد دارند. مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]<ref>Heaps</ref>، درخت‌های هافمن<ref>Huffman trees</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>Free tree</ref> گوییم.
۱۷٬۱۹۰

ویرایش