صفحه محصول - پاورپوینت درخت ها و الگوریتم های DFS و BFS

پاورپوینت درخت ها و الگوریتم های DFS و BFS (pptx) 27 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 27 اسلاید

قسمتی از متن PowerPoint (.pptx) :

نیمسال اول 99-1398 استاد درس: مریم طهماسبی گروه علوم کامپیوتر دانشگاه شهید بهشتی درخت ها و الگوریتم های DFS و BFS تعریف‎ها و نتایج اولیه نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 2 درخت یک گراف همبند بدون دور است. جنگل یک گراف بدون دور است. پس هر مولفه همبندی جنگل، درخت است. هر راس درجه 1 در درخت را یک برگ می‎نامیم. تعریف‎ها و نتایج اولیه نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 3 یک درخت فراگیر از گراف G یک زیردرخت فراگیر از آن است که درخت باشد. درخت با یک راس را درخت بدیهی می‎نامیم. تعریف‎ها و نتایج اولیه نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 4 قضیه: درخت T دارای n راس و n-1 یال است. قضیه: بین هر دو راس از درخت دقیقا یک مسیر وجود دارد. نتیجه: هر یال درخت یک پل است. قضیه: هر درخت غیر بدیهی دارای حداقل 2 برگ است. قضیه: اگر بزرگترین درجه راسی درخت T برابر با  باشد، آنگاه T دارای حداقل  برگ است. درخت ریشه‌دار نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 5 درخت جهتدار T گراف جهتداری است که گراف زمینه آن درخت باشد. درخت ریشه‌دار T درخت جهتداری است که راسی مانند r به نام ریشه داشته باشد به طوری که از ریشه به هر راس دیگر مسیر جهتداری وجود داشته باشد. درخت ریشه‎دار نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 6 اگر T یک درخت ریشه دار باشد، معمول است T طوری رسم شود که ریشه در بالاترین سطح (سطح صفر)، راس‌های مجاور آن در سطح یک و به همین صورت راس‎های مجاور راس‎های هر سطح i در سطح i+1 قرار گیرند. در این صورت جهت کمان ها در نمایش حذف می‌شود. بزرگترین سطح در درخت را ارتفاع درخت می‎نامیم. درخت ریشه‌دار نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 7 قضیه: درخت جهتدار T ریشه دار است اگر و تنها اگر T شامل راسی مانند r باشد به طوری که id(r) = 0 و برای هر راس دیگر u داشته باشیم id(u) = 1 ایده اثبات: اگر T درخت ریشه دار باشد، حکم به وضوح برقرار است. فرض کنید T درخت جهتدار با شرط داده شده باشد. یک راس دلخواه u انتخاب کنید. id(u) = 1، پس کمان ورودی (v,u) وجود دارد. اگر v = r مساله حل شده است. در غیر این صورت v هم یک کمان ورودی دارد. با ادامه این روند مسیری جهتدار از r به u تعیین می‎شود. درخت ریشه‎دار نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 8 در درخت ریشه دار T، اگر کمان (w,v) وجود داشته باشد، v فرزند w و w پدر v است. اگر مسیر جهتداری از u به v وجود داشته باشد، u جد v و V نوه u است. زیردرخت ریشه‎داری که از راس u و همه نوادگان آن تشکیل می‏شود، زیردرخت ماکسیمال T با ریشه u نام دارد و با نماد T( u ) نشان داده می‎شود. درخت ریشه‌دار نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی 9 درخت ریشه دار T را m-تایی می‎نامیم هرگاه هر راس آن حداکثر m فرزند داشته باشد. درخت m-تایی را تام می‎نامیم هرگاه هر راس m یا صفر فرزند داشته باشد. درخت m-تایی را متعادل می‏نامیم هرگاه همه برگ‏های آن در سطح h یا h-1 قرار داشته باشند. اگر m=2 باشد درخت را دودویی می‏نامیم.