بخشی از پاورپوینت
اسلاید 1 :
درخت ها و الگوریتم های 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 باشد درخت را دودویی مینامیم.
اسلاید 10 :
درخت ریشهدار
درخت دودویی
درخت دودویی تام
درخت دودویی متعادل
اسلاید 11 :
درخت ریشهدار
قضیه: هر درخت m- تایی تام با i راس داخلی دارای mi+1 راس است.
نتیجه: هر درخت دودویی با i راس داخلی دارای i+1 برگ است.
قضیه: اگر T یک درخت دودویی با ارتفاع h و p راس باشد، آنگاه
ایده اثبات: کران پایین برای مسیر جهتدار به طول p-1 برقرار است.
در هر درخت دودویی تعداد راسها در هر سطح حداکثر دو برابر تعداد راسها در سطح قبل است.
اسلاید 12 :
ورودی: گراف G
خروجی: جنگل فراگیر T (برای حفظ اطلاعات پدر و فرزندی در جنگل از متغیر pred استفاده میکنیم.)
به هر راس u اندیس dfi(u) نسبت داده میشود
اسلاید 13 :
الگوریتم DFS
نظریه الگوریتمی گراف- گروه علوم کامپیوتر دانشگاه شهید بهشتی
1- به ازای هر راس u قرار دهید dfi(u)= 0 و pred(u) = 0 .
2- قرار دهید k = 1 .
3- یک راس r با dfi(r) = 0 انتخاب کنید. قرار دهید u = r، dfi(u) = k و k = k+1
4- تا زمانی که u ≠ r مراحل زیر را تکرار کنید.
اگر همه راسهای مجاور u مشاهده شدهاند، قرار دهید u= pred(u).
در غیر این صورت، فرض کنید v راس مجاور u و مشاهده نشده باشد، قرار دهید
pred(v) = u، dfi(v) = k و u = v و k = k+1
5- اگر برای هر راس u داریم dfi(u) ≠ 0 الگوریتم تمام شده. در غیر این صورت به مرحله 3 بروید.
O(max{n,m})
اسلاید 17 :
الگوریتم DFS
یالهایی که در درخت (جنگل) DFS قرار دارند را از راس با اندیس بزرگتر (پدر) به راس با اندیس کوچکتر (فرزند) جهتدار میکنیم. یک درخت (جنگل) ریشهدار به دست میآید که آن را درخت (جنگل) DFS گراف مینامیم.
یالهایی که در جنگل DFS قرار ندارند را از نوه به طرف جد جهتدار میکنیم و یالهای بازگشتی مینامیم.
نقطه پایین راس v که با نماد نشان داده میشود، کمترین مقدار dfi(u) است به طوری که v با مسیر جهتداری که شامل حداکثر یک یال بازگشتی است، به u متصل باشد.
اسلاید 19 :
یادآوری
یک بلوک در گراف زیرگراف ماکسیمال بدون راس برشی است.
اشتراک هر دو بلوک تنها یک راس برشی است.
بلوکی که فقط یک راس برشی داشته باشد، بلوک پایانی نام دارد.
اسلاید 20 :
الگوریتم DFS برای تعیین راسهای برشی
قضیه: فرض کنید T درخت DFS گراف G و r ریشه T باشد. آنگاه r راس برشی است اگر و تنها اگر r در T دارای حداقل دو فرزند باشد.
ایده اثبات: فرض کنید r دارای دو فرزند u و v باشد. T(u) و T(v) هرکدام یک بلوک از گراف هستند.
برعکس، اگر r راس برشی باشد، وقتی DFS وارد یک بلوک متصل به r میشود، تا زمانی که همه راسهای بلوک را مشاهده نکرده در آن بلوک باقی میماند و برای مشاهده راس های بلوک دیگر به r باز میگردد. پس r دارای دو فرزند میشود.
