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

در [[نظریهٔ گراف]]، '''درخت''' گرافی استهمبند که هر دو [[رأس]] آن با دقیقا یک [[مسیر]] به همو متصلبدون شده است. همچنین، هر گراف [[متصل]] که [[مدار]] نداشته باشد یک درخت است. جنگل، اجتماع چندین درختدور است. درخت ها به طور گسترده در [[علوم کامپیوتررایانه]] و [[ساختار داده‌ها]] کاربرد دارند. مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]<ref>Heaps</ref>، درخت‌های هافمن<ref>Huffman trees</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 ).