***2
آنچه که در این اسلاید می خوانیم :
(شبکه فعالیت روی راس ها)AOV 1) نمایش شبکه
(شبکه فعالیت روی یال ها)AOE 2) نمایش شبکه
3) محاسبه ی زودترین زمان فعالیت
4) محاسبه ی دیرترین زمان فعالیت
***3
AOV ) نمایش شبکه1
هر پروژه ای را می توان به چندین زیرپروژه که فعالیت نامیده می شود، تقسیم کرد .
به عنوان مثال :
یک دانشجوی رشته مهندسی نرم افزار برای گرفتن مدرک ناچار به موفقیت در چندین درس است.
پس هر درس به عنوان یک فعالیت در نظر گرفته می شود.
پیش نیازها روابط و اولویت موجود بین دروس را معین می کنند .
***5
مثال
به منظور روشن شدن روابط پیش نیازی می توان از یک گراف جهتدار استفاده کرد، که در آن :
- راس ها را نمایانگر دروس
- وهر یال جهتدار آن را نشان دهنده ی رابطه پیش نیازی قرار می دهیم .
حال اگر یک راس پیش نیاز راس دیگر باشد از راس اول یک یال به سمت راس دوم رسم می کنیم .
***7
تعاریف
شبکه فعالیت روی راس(AOV) :این شبکه در واقع یک گراف جهت دار مانند G می باشد که راس های آن نمایانگر فعالیت ها و یالهای آن نمایانگر ارتباطات بین فعالیت ها می باشد.
راس i در یک شبکه AOV از گراف G راسی قبل از راس j خواهد بود اگر وتنها اگر مسیر جهتداری از راس i به راس j وجود داشته باشد.
راسi در یک شبکه AOV بلافاصله قبل از راس j است اگر و تنها اگر(i, j) یالی در G باشد.
***9
تعاریف
رابطه متعدی:
رابطه ی نقطه (.) را یک رابطه ی متعدی گوییم اگر و تنها اگر برای تمام سه گانه های iو j و k داشته باشیم :
i . j & j . k i . k
رابطه غیرانعکاسی:
رابطه ای را روی مجموعه ی S غیر انعکاسی گوییم اگر برای تمامی مقادیر x در S , x . x نادرست باشد.
رابطه ترتیبی :
رابطه ای که هم متعدی باشد و هم غیر انعکاسی یک رابطه ترتیبی نام دارد.
***10
تعاریف - ادامه
رابطه ی ترتیبی تعریف شده توسط پیش نیازهای درسی یک رابطه ی متعدی
است .
معلوم نیست .AOV اما این موضوع در شبکه ی
اگر یک شبکه دارای چرخه باشد انگاه یک فعالیت وجود خواهد داشت که باید قبل از اغاز شدن کامل گردد و واضح است که این امرغیرممکن است .
هنگامی که هیچ تناقضی از این نوع موجود نباشد پروژه عملی است .
***11
تعریف
ترتیب موضعی :
یک ترتیب خطی از راس های یک گراف است به نحوی که به ازای هر دو راس i و j اگر i یک راس تقدمی برای j در شبکه باشد انگاه i در این ترتیب خطی پیش از j قرار می گیرد .
الگوریتم ارائه شده برای آزمایش عملی بودن پروژه یک ترتیب خطی از راس ها (فعالیت ها) را به صورت V0,V1,…,Vn-2,Vn-1 تولید می کند .
***13
طراحی الگوریتم مرتب سازی موضعی
در ابتدا راسی که هیچ راس دیگری در شبکه قبل از ان قرار ندارد را با تمام یال هایی که از ان خارج می شود از شبکه حذف می کنیم . این مرحله تا زمانی ادامه می یابد که همه ی راس های در شبکه حذف شوند .
1 //Input the AOV network . Let n be the number of vertices .
2 For ( int i=0 ; i
3 {
4 if ( every vertex has a predecessor)
5 return ; //network has a cycle and is infeasible .
6 pick a vertex V that has no predecessors ;
7 cout << V ;
8 delete V and all edges leading out of V from the network ;
9 }