دانلود پاورپوینت درخت ها و الگوریتم های DFS و BFS با فرمت ppt و در 27 اسلاید قابل ویرایش
قسمتی از متن پاورپوینت درخت ها و الگوریتم های DFS و BFS
تعریفها و نتایج اولیه
درخت یک گراف همبند بدون دور است.
جنگل یک گراف بدون دور است. پس هر مولفه همبندی جنگل، درخت است.
هر راس درجه 1 در درخت را یک برگ مینامیم.
تعریفها و نتایج اولیه
یک درخت فراگیر از گراف G یک زیردرخت فراگیر از آن است که درخت باشد.
درخت با یک راس را درخت بدیهی مینامیم.
قضیه: درخت T دارای n راس و n-1 یال است.
قضیه: بین هر دو راس از درخت دقیقا یک مسیر وجود دارد.
نتیجه: هر یال درخت یک پل است.
قضیه: هر درخت غیر بدیهی دارای حداقل 2 برگ است.
قضیه: اگر بزرگترین درجه راسی درخت T برابر با D باشد، آنگاه T دارای حداقل D برگ است.
درخت ریشه‌دار
درخت جهتدار 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 ) نشان داده می‌شود.
دیدگاه خود را ثبت کنید