پاورپوینت درخت ها و الگوریتم های DFS و BFS

دانلود پاورپوینت با موضوع درخت ها و الگوریتم های DFS و BFS،

در قالب ppt و در 27 اسلاید، قابل ویرایش.

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