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

توضیحات محصول

دانلود پاورپوینت درخت ها و الگوریتم های 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 ) نشان داده می‎شود.