3- تعیین همبندی نمودار تئوری جـریان های شبکه در این بخش اسـتفاده شده است. برای نشان دادن اثبـات های سازنده قضیه های منجر(Menger) استفاده شده است، که در فصل5 ذکر شده اند. این اثبات ها مستقیماً منجر به الگوریتم هایی برای تعیین همبندی-یال و همبندی- رأس نمودار می شوند. استراتژی ماورای استفاده از جریان های شبکه برای اثبات قضیه های منجر(Menger) براساس خصوصیت شبکه های خاص قرار گرفته است که تمامی قوس ها ظرفیت واحد و یکسان دارند. شبکه های1-0 از نمودار اصلی به وجود آمده اند. گزاره1-3: در اثبات ویژگی شبکه های1-0 استفاده شده است که بعداً نیاز می شود. اثبات آن نیاز به لم ذیل دارد. لم1-3: فرض کنید کهN شبکهs-t باشد به طوری کهoutdegree(s)>indegree(s)، indegree(t)>outdegree(t) و outdegree(v)=indegree(v) برای تمامی رأس هایv. از این رو در شبکهN مسیر جهت دارs-t وجود دارد. اثبات: فرض کنید کهw طولانی ترین مسیر جهت دار در شبکهN باشد که در منبعs شروع می شود و فرض کنید کهz رأس پایانی آن باشد. اگر رأسz مخزنt نبود، پس قوسی وجود دارد که در مسیرw نیست که ازz جهت یافته باشد(از اینروindegree(z)=outdegree(z) است). اما ماکسیمال بودن مسیرw را نقض خواهد نمود. از اینروw مسیر جهت دار از منبعs به مخزنt است. اگرw رأس تکراری دارد، پس بخـشی ازw چرخه جـهت دار را مـشخص می کند که برای دست یافـتن به مسـیر کوتاهـترs-t جهت دار، می توان آن را ازw حذف نمود. مرحله حذف را می توان تکرار کرد تا هیچ رأس تکراری وجود نداشته باشد، در نقطه ای که مسیر برایند جهت دار نظیرs-t است. گزاره2-3: فرض کنید کهN شبکهs-t باشد outdegree(s) – indegree(s) = m = indegree(t) - outdegree(t), outdegree(v) = indegree(v), v ≠ s,t از اینرو مسیرهای جهت دارs-t قوس مجزایm در شبکهN وجود دارند. اثبات: اگرm=1 باشد، پس مسیر جهت دار باز اویلریT از منبعs به مخزنt وجود دارد، در نتیجه قضیه3-1-6. از طریق قضیه2-5-1، مسیرT یا مسیر جهت دارs-t است یا می توان آن را تا مسیرs-t کاهش داد. در نتیجه القا فرض کنید که تصدیق برایm=k، برای مقدارk≥1 صحیح است و شبکهN را در نظر بگیـرید که حالتm=k+1 را دارد. به واسطه لم1-3، مـسیرs-t جهت دارp وجود دارد. اگر قوس های مسیرp از شبکهN‌حذف شوند، سپس شبکه بدست آمدهN حالت گزاره را برایm=k برآورده می کند. در نتیجه فرضیه القا، مسیرهایs-t جهت دار قوس، مجزایt در شبکهN وجود دارند. مسیرهایk با مسیرp مجمـوعه ای از مسیرهای جهت دارs-t قوس مجزایk+1 را در شبکهN بوجود می آورند. دو ویژگی اصلی شبکه های1-0 تعریف: شبکه1-0 شبکه با ظرفیتی است که ظرفیت های قوس یا صفر یا یک می باشند. دو گزاره بعد با دو خصوصیت شبکه های1-0 اثبات می شوند که نقش مهمی را در اثبات های جریان شبکه قضیه های منجر(Menger) ایفا می کند. گزاره3-3: فرض کنید کهN شبکهs-t باشد کهcap(e)=1 برای هر قوسe‌باشد. از اینرو مقدار ماکسیمم جریان در شبکهN مساوی با ماکسیمم تعداد مسیرهایs-t‌جهت دار قوس مجزا درN‌است. اثبات: فرض کنید کهf* ماکسیمم جریان در شبکهN وr ماکسیمم تعداد مسیرهای جهت دارs-t‌قوس مجزا درN‌باشند. شبکهN*‌را بررسی کنید که از طریق حذف نمودنN از تمامی قوس ها بدست آمده است، یعنیf*(e)=0، سپسf*(e)=1 برای تمام قوس هایe در شبکهN* است. این امر به دنبال تعاریفی برای هر رأسv در شبکهN* است. ∑ e Є Out(s) f*(e) = |Out(v)| = outdegree(v) ∑e Є In(s) f*(e) = |In(v)| = indegree(v) از اینرو در نتیجه تعریفval(f*) و خصوصیت پایستگی جریان outdegree(s) – indegree(s) = val(f*) = indegree(t) - outdegree(t), outdegree(v) = indegree(v), v ≠ s,t 210312074930000در نتیجه گزاره2-3، مسیرهایs-t جهت دار قوس مجزایval(f*) در شبکهN* و همینطور درN وجود دارند، که بیانگرval(f*)≤r می باشد. برای دست یافتن به نابرابری معکوس، فرض کنید که{p1,p2,…,pr} بزرگترین مجموعه مسیرهای جهت دارs-t قوس-مجزا درN باشند- و تابع f:E(N) R+ را بررسی کنید، 2103120-31751, if some path Pi uses arc e 0, otherwise. 001, if some path Pi uses arc e 0, otherwise. f(e) = { از اینروf جریان ممکن در شبکهN باval(f)=r است که بیان می کندval(f*)≤r. مجموعه ها و قطع های تفکیک کننده گزاره بعد برحسب قیاس نمودار مجموعه یال تفکیک کنندهs-t بیان شده است. مرور از§5.3 : فرض کنید کهs وt قوس های جداگانه در نمودارG باشند. مجموعه یال تفکیک کننده درG مجموعه ای از یال هایی است که تفکیک آن تمامی مسیرهایs-t را درG از بین می برد. از اینرو، مجموعه یال تفکیک کننده درG زیر مجموعه یالEG است که حداقل یک یال از هر مسیرs-t درG دارد. تعریف: فرض کنید کهs وt قوسهای خاص در نمودارD باشند. مجموعه قوس تفکیک کنندهs-t درD مجموعه ای از قوس هایی است که تفکیک آن تمامی مسیرهای جهت دارs-t را درD از بین می برد. از اینرو مجموعه قوس تفکیک کنندهs-t درD زیر مجموعه قوسED است که حداقل دارای یک قوس از هر مسیر جهت دارs-t در نمودارD می باشد. نکته: برای حالتی که نمودار اصلی یا نمودار جهت دار مسیرهایs-t ندارد، مجموعه تهی به عنوان مجموعه تفکیک کنندهs-t تلقی شده است. گزاره4-3: فرض کنید کهN شبکهs-t باشد به طوریکهcap(e)=1 برای هر قوسe. سپس ظرفیت مینیمم قطعs-t در شبکهN مساوی با تعداد مینیمم قوس ها در مجموعه تفکیک کنندهs-t درN است. اثبات: فرض کنید کهK*=<Vs,Vt> مینیمم قطعs-t در شبکهN است و فرض نمایید کهq مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t درN می باشد. چونK* قطعs-t است، مجموعه قوس تفکیک کنندهs-t است، پسcap(K*)≥q می باشد. برای دست یابی به نابرابری مساوی، فرض کنید کهs مجموعه قوس تفکیک کنندهs-t در شبکهN است که دارای قوس هایq می باشد وb مجموعه تمامی رأس ها درN‌است که از منبعs از طریق مسیر جهت دار قابل دسترسی می باشند که از مجموعهs هیچ قوسی ندارد. از اینرو، در نتیجه تعاریف مجموعه قوسs و مجموعه رأسR، t ¢ R است، که به این معناست که<R,VN-R> قطعs-t می باشد. علاوه بر این<R,VN-R> زیر مجموعهS است که: Cap(K*) ≤ cap<R,VN-R> =|<R,VN-R>| ≤|S| = q اثبات را کامل می کند. انواع قوس و یال قضیه منجر(Menger) بررسی شده قضیه5-3: [فرم قوس قضیه منجر(Menger)]. فرض کنید کهs وt رأس های مجزا در نمودار جهت دارD‌باشند. پس ماکسیمم تعداد مسیرهایs-t جهت دار قوس مجزا درD مساوی با مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t، ازD است. اثبات: فرض کنید کهN شبکهs-t است که از طـریق تخصیص گنجایـش یکسان به هر قـوس نمودار جهت دارD به دست آمده است. پس نتیجه از گزاره های3-3 و4-3 با قضیهmax-flow min-cut حاصل می شود(قضیه4-2). نکته: برعکس این که شکل قوس قضیه منجر(Menger) یا گزاره های3-3 و 4-3. برای اثبات قضیه max-flow min-cut استفاده شده است. شکل یال قضیه منجر(Menger) برای نمودارهای غیرجهت دار مستقیاً از دو تصدیق بعد در نتیجه رابطه بین نمودارG‌و نمودارG بدست آمده از طریق جایگزینی در یالe از نمودارG با جفتی از قوس های جهت دار به طور معکوس بدست می آید که دارای همان نقاط پایانی به عنوان یالe می باشند. هر یک از این تصدیق ها مستقیاً ناشی از این تعاریف است. تصدیق6-3: فرض کنید کهs وt رأس های مجزای نمودارG باشند وG نمودار بدست آمده از طریق جایگزینی هر یالe ازG با جفتی از قوس های جهت به طور مخالف باشد که همان نقاط پایانی را تحت عنوان یالe دارند پس مینیمم تعداد یال ها در مجموعه یال تفکیک کنندهs-t‌نمودارG مساوی با تعداد مینیمم قوس ها در مجموعه قوس تفکیک کنندهs-t نمودار جهت دارG است. قـضیه8-3: [شکل یـال قضیه مـنجر(Menger)]. فـرض کنید کهsوt رأس های مجزایی در نمـودارG می باشند. سپس ماکسیمم تعداد مسیرهایs-t یال-مجزا درG مساوی با مینیمم تعداد یال ها در مجموعه یال تفکیک کنندهs-t نمودارG است. اثبات: این نتیـجه مـیانی تـصـدیق های6-3 و7-3 با شکل قــوس قضیـه منـجر(Menger) است[قضیه5-3]. تعیین همبندی-یال با استفاده از جریان های شبکه مرور از§5.1 : همبندی-یالke(G) سایز کوچکترین یال-قطع در نمودارG است. تعریف: فرض کنید کهs وt رأس های مجزا در نمودارG باشند. همبندی یال موضعی بین رأس هایs وt که بر ke (s,t) دلالت می کند، مینیمم تعداد یال ها در مجموعه قوس تفکیک کنندهs-t درG‌می باشد. گزاره ذیل نشان می دهد که همبندی-یال نمودار را می توان برحسب همبندی-یال موضعی بین تمامی جفت های رأس ها نشان داد. تصدیق و اثبات آن شبیه به لم5-3-5 و اثبات آن می باشد(از§ 5.3 ). گزاره9-3 و نتایج اثبات شده: ke(G) = min{ ke(s,t)} در اثبـات قضـیه8-3 الگوریـتمی را برای تـعیین همـبندی-یـال ke(G) نمـودار دلخـواهG نشان می دهند. الگوریتم همبندی-یال بین هر جهت از رأس ها را درG به واسطه حل نمودن مسئله خاص ماکسیمم جریان در شبکهG محاسبه می کند(به تصدیق های6-3 و7-3 رجوع نمایید). در واقع محاسبه همبندی-یال موضعی بین هر جفت از رأس ها الزامی نیست، همانطور که دو نتیجه بعدی نشان می دهند. هر دو نتیجه از رابطه بین همبندی-یال موضعی و افراز-قطع ها استفاده می کنند. مرور از §4.6 : فرض کنید کهG نمودار باشد وV1 وV2 افرازVG را به وجود آورند. مجموعه ای از تمام یال هایG‌دارای یک نقطه پایانی در زیر مجموعه رأسV1 و نقطه پایانی دیگر در زیر مجموعه رأسV2 افراز-قطعG نامیده شده است و به شکل<V1,V2> نشان داده شده است. گزاره10-3: فرض کنید که<V1,V2> افراز قطع مینیمم مجموعه اصلی در نمودارG باشند وV1 وV2 به ترتیب هر رأسی درV1 وV2 باشند. از اینرو همبندی-یال ke(G)مساوی با همبندی-یال موضعی ke(v1,v2) است. اثـبات: فـرض کنیـد که مـینیـمم همـبندی-اتـصال یال بـین رأس هایx وy بـدست آمـده است. پس ke(G)= ke(x,y) (براساس گزاره9-3). این مسأله براساس نشان دادن ke(V1,V2) ≤ ke(x,y) کافی است. فرض کنید کهG نمودار بدست آمده در نتیجه جابجایی در یال نمودارG یا دو قوس جهت دار مخالف باشد. سپس نمودارG را می توان به عنوانV1-V2 شبکه با ظرفیتGv1,v2 وx-y شبکه با ظرفیتGxy تلقی نمـود، در حالیکه هر قوس ظرفـیت یکسانی دارد. تصور کنید کهK* مینیمم قطعV1-V2 در شبکهGv1,v2 باشد. کهcap(K*) ≤ cap<V1,V2> را بیان می کند چون افراز قطع<V1,V2> مشابه قطعV1-V2 در شبکهGv1,v2 است. سپس، فرض نمایید کهf* ماکسیمم جریان و<Vx,Vy> مینیمم قطعx-y درx-y شبکهGxy‌باشد سپـسcap<Vx,Vy>=val(f*) می باشد. زنجـیره بعـدی با نامـعادله مـورد نـظر را اثبـات می کنـد. Ke(V1,V2) = cap(K*) ≤ cap<V1,V2> = |<V1,V2>| ≤|<Vx,Vy>| = cap<Vx,Vy> = val(f*) = ke(x,y) نتیجه11-3: فرض کنید کهs هر رأسی در نمودارG باشد. در نتیجه ke(G) = min{ ke(s,t)} اثبات: تصور کنید که<V1,V2> افراز-قطع مینیمم مجموعه اصلی باشد و همچنین بدون از دست دادن اصل کلی، رأس s Є V1است. تعدادی رأس t Є V2وجود دارد(در غیر این صورتEG=0 و تصدیق به طور بدیهی صحیح است) در نتیجه گزاره10-3، این نتیجه به دست می آید ke(G)=ke(s,t) متغیر ke، که در الگوریتم بعدی استفاده می شود، همبندی-یال نمودارG را نشان می دهد و با عدد صحیح مثبت بزرگ|EG| شروع شده است. Algorithm 3.1: Edge-Connectivity Calculation Input: a graph G Output: the edge-connectivity ke of graph G Construct digraph G Let s be an arbitrary vertex of graph G Initialize edge-connectivity ke:=|EG| For each vertex t Є NG-{s} Apply algorithm 2.3 to s-t network G to obtain maximum flow f* If val(f*)<ke Ke:=val(f*) Return ke نکتـه مـحـاسبـه ای: الگوریـتم1-3 به تـکرارهایO(n) نیـاز دارد و چون الگوریتـم3-2 نیـاز به محاسبه هایO(n|E|²) دارد. محاسبه کلی الگوریتم1-3،O(n²|E|²) است. این محاسبه را می توان کاهش داد اگر یکی از الگوریتـم های کارآمدتر ماکسیمم-جریان ذکر شده در بخش های قبلی، به جای الگوریتم3-2 استفاده شود. استفاده از جریان های شبکه برای اثبات اشکال رأس قضیه منجر(Menger) شکل رأس قضیه مـنجر(Menger) برای نمودارهای جهت دار و نمودارها را می توان با استفاده از شکل های قوس و یال اثبات نمود(قضیه های5-3 و8-3). اثبات ها براساس ساختار ذیل قرار گرفته اند. ساختار نمودار جهت دارN^D از نمودار جهت دارD فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودار جهت دارD باشند. نمودار جهت دارN^D از نمودار جهت دارD به شرح زیل بدست آمده است: ـ هر رأسxЄVD-{s,t} متناظر با دو رأسx’ وx” در نمودار جهت دارN^D و قوس جهت دار ازx’ بهx” است. ـ هر قوس در نمودار جهت دارD که از رأسsبه رأس xЄVD-{s,t}جهت یافته است متناظر با قوس در نمودار جهت دارN^D جهت یافته ازs بهx’ می باشد. ـ هر قوس درD که از رأسxЄVD-{s,t} به رأسt جهت یافته است متناظر به قوس درN^D جهت یافته ازx” بهt است. 4663440601980x” 00x” 1645920601980x 00x ـ هر قوس درD که از رأس xЄVD-{s,t}به رأس yЄVD-{s,t}جهت یافته است متناظر با قوس درN^D جهت یافته ازx” بهy’ می باشد. 42976802540x’ 00x’ 3840480642620s 00s 2286000-19685y 00y 45720001333500048463201333500053949604191000493776041910004572000419100048463204191000530352041910001920240118110005638800-225425y” 00y” 5669280444500057099201663700044805604445000411480014033500250952015811500219456011811000246888026670001920240266700018288002667000146304011811000 5212080-460375y’ 00y’ 5943600187325t 00t 540067522415500594360012827000420624022415500411480012827000274320018415t 00t 274320010985500219456020129500155448020129500146304010985500 3108960171450004846320262890004480560262890z’ 00z’ 5303520171450004754880179070002011680247650z 00z 210312015621000 3108960122555شکل 1-3 00شکل 1-3 1188720-772795s 00s 5212080-528320z” 00z” مرور از §5.3: فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودارG(یا نمودار جهت دارD) باشند. مجموعه رأس تفکیک کنندهs-t درG(یاD) مجموعه ای از رأس هایی است که تفکیک آن تمامی مسیرهایs-t را درG(یا تمامی مسیرهای جهت دارs-t درD) را از بین می برد. از اینرو، مجموعه رأس تـفکیک کنندهs-t مجمـوعه ای از رأس هایی است که حـداقل دارای یک رأس داخلی در هر مسیرs-t (جهت دار) است. تعریف: دو مسیر(جهت دار)s-t در نمودار جهت دارD از لحاظ درونی مجزا می باشند اگر آنها کاملاً رأس های داخلی نداشته باشند. روابط بین نمودارهای جهت دارD وN^D اشکال رأس قضیه منجر(Menger) به آسانی از چهار رابطه بین نمودار جهت دارD و نمودار جهت دار متناظر آنN^D به دست می آیند. هر یک از اینها از تعاریفی تبعیت می کنند: تصدیق12-3: انطباق یک به یکی بین مسیرهای جهت دارs-t در نمودار جهت دارD و مسیرهای جهت دارs-t در نمودار جهت دارN^D وجود دارد. تصدیق13-3: دو مسیر جهت دارs-t درD از لحاظ داخلی مجزا می باشند اگر مسیرهای جهت دار متناظرs-t آنها درN^D، قوس مجزا باشند. تصدیق14-3: ماکسیمم تعداد مسیرهایs-t جهت دار مجزا از احاظ داخلی درD‌مساوی با ماکسیمم اعداد مسیرهایs-t جهت دار قوس-مجزا درN^D است. تصدیق15-3: مینیمم تعداد رأس ها در مجموعه رأسs-t تفکیک کننده در نمودار جهت دارD مساوی با مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t در نمودار جهت دارN^D می باشد. قضیه16-3: [شکل رأس از منجر(Menger) برای نمودارهای جهت دار]. فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودار جهت دارD باشند. سپس ماکسیمم تعداد مسیرهای جهت دار مجزایs-t درD مساوی با مینیمم تعداد رأس ها در رأس تفکیک کنندهs-t درD است. اثـبـات: ایــن اثبـات به هـمــراه تصــدیــق12-3 تا 15-3 با شــکل قــوس قــضـیه مـنجـر(Menger) می باشد(قضیه5-3). قضیه17-3: [شکل رأس منجر(Menger) برای نمودارهای غیرجهت دار]. فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودارG‌باشند. از اینرو ماکسیمم تعداد مسیرهایs-t مجزا از لحاظ داخلی درG مساوی با مینیمم تعداد رأس ها در مجموعه تفکیک کنندهs-t درG است. اثبات: فرض کنید کهG نمـودار جهت داری باشد که از طریـق جایـگزینی هر یالe ازG با جفتی از قوس های جهت دار معکوس بدست آمده است که همانند یالe نقاط پایانی دارند. نتیجه به واسطه قضیه16-3 و تصدیق های6-3 و7-3 بدست می آیند. تعیین همبندی-رأس با استفاده از جریان های شبکه اثبات شکل رأس قضیه منجر(Menger) که براساس تئوری جریان های شبکه قرار گرفته است منجر به الگوریتمی برای تعیین همبندی-رأس نمودار می شود، در اکثر موارد شکل یال قضیه منجر(Menger) موجب تشکیل الگوریتمی برای همبندی-یال می شود. مرور از §5.3: فرض کنید کهs وt رأس های غیرمجاور نمودار متصل شدهG باشند. از اینرو، همبندی-یال موضعی بینs وt که به شکلKv(s,t) نشان داده شده است، مینیمم تعداد رأس ها در مجموعه رأس تفکیک کنندهs-t است. مرور از لم5-3-5: فرض کنید کهG نمودار به هم پیوسته ای باشد که حداقل دارای یک جفت رأس غیرمجاور است. از اینرو همبندی-رأسKv(G) مینیمم همبندی-رأسKv(s,t) است که شامل تمامی جفت های رأس های غیرمجاورs وt می باشند. نکته: الگوریتم ذیل، که پیچیدگی زمانیO(n|EG|³) را دارد، همبندی-رأس نمودار رأسn را از طریق محاسبه همبندی-رأس موضعی بین جفت های مختلف رأس های غیرمجاور محاسبه می نماید. همانند الگوریتم1-3، محاسبه همبندی-رأس موضعی بین هر جفت الزامی نیست. اثبات صحت آن و پیچیدگی زمانی آن حذف شده اند اما ممکن است یافت شوند. متغیرKv که در الگوریتم2-3 شهود است، همبندی-رأس نمودارG را نشان می دهد و با عدد صحیح مثبت نسبتاً بزرگ|VG| شروع شده است. Algorithm 3.2: Vertex-Connectivity Calculation Input: an graph G with VG={v1,v2,…,vn} Output: the vertex-connectivity ke of graph G Construct digraph G Construct digraph N^G Assing unit capacity to each arc in digraph N^G Initialize edge-connectivity ke:=|VG| Initialize index k:=0 While k≤kv K:=k+1 For j=k+1 to n If vertices vk and vj are not adjacent Apply algorithm 2.3 to network N^G with source vk And sink vj to obtain maximum flow f* If val(f*)<kv Kv:=val(f*) Return kv


دسته‌بندی نشده

سایت ما حاوی حجم عظیمی از مقالات دانشگاهی است . فقط بخشی از آن در این صفحه درج شده شما می توانید از گزینه جستجو متن های دیگری از این موضوع را ببینید 

کلمه کلیدی را وارد کنید :

دسته بندی: دسته‌بندی نشده

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

3- تعیین همبندی نمودار تئوری جـریان های شبکه در این بخش اسـتفاده شده است. برای نشان دادن اثبـات های سازنده قضیه های منجر(Menger) استفاده شده است، که در فصل5 ذکر شده اند. این اثبات ها مستقیماً منجر به الگوریتم هایی برای تعیین همبندی-یال و همبندی- رأس نمودار می شوند. استراتژی ماورای استفاده از جریان های شبکه برای اثبات قضیه های منجر(Menger) براساس خصوصیت شبکه های خاص قرار گرفته است که تمامی قوس ها ظرفیت واحد و یکسان دارند. شبکه های1-0 از نمودار اصلی به وجود آمده اند. گزاره1-3: در اثبات ویژگی شبکه های1-0 استفاده شده است که بعداً نیاز می شود. اثبات آن نیاز به لم ذیل دارد. لم1-3: فرض کنید کهN شبکهs-t باشد به طوری کهoutdegree(s)>indegree(s)، indegree(t)>outdegree(t) و outdegree(v)=indegree(v) برای تمامی رأس هایv. از این رو در شبکهN مسیر جهت دارs-t وجود دارد. اثبات: فرض کنید کهw طولانی ترین مسیر جهت دار در شبکهN باشد که در منبعs شروع می شود و فرض کنید کهz رأس پایانی آن باشد. اگر رأسz مخزنt نبود، پس قوسی وجود دارد که در مسیرw نیست که ازz جهت یافته باشد(از اینروindegree(z)=outdegree(z) است). اما ماکسیمال بودن مسیرw را نقض خواهد نمود. از اینروw مسیر جهت دار از منبعs به مخزنt است. اگرw رأس تکراری دارد، پس بخـشی ازw چرخه جـهت دار را مـشخص می کند که برای دست یافـتن به مسـیر کوتاهـترs-t جهت دار، می توان آن را ازw حذف نمود. مرحله حذف را می توان تکرار کرد تا هیچ رأس تکراری وجود نداشته باشد، در نقطه ای که مسیر برایند جهت دار نظیرs-t است. گزاره2-3: فرض کنید کهN شبکهs-t باشد outdegree(s) – indegree(s) = m = indegree(t) - outdegree(t), outdegree(v) = indegree(v), v ≠ s,t از اینرو مسیرهای جهت دارs-t قوس مجزایm در شبکهN وجود دارند. اثبات: اگرm=1 باشد، پس مسیر جهت دار باز اویلریT از منبعs به مخزنt وجود دارد، در نتیجه قضیه3-1-6. از طریق قضیه2-5-1، مسیرT یا مسیر جهت دارs-t است یا می توان آن را تا مسیرs-t کاهش داد. در نتیجه القا فرض کنید که تصدیق برایm=k، برای مقدارk≥1 صحیح است و شبکهN را در نظر بگیـرید که حالتm=k+1 را دارد. به واسطه لم1-3، مـسیرs-t جهت دارp وجود دارد. اگر قوس های مسیرp از شبکهN‌حذف شوند، سپس شبکه بدست آمدهN حالت گزاره را برایm=k برآورده می کند. در نتیجه فرضیه القا، مسیرهایs-t جهت دار قوس، مجزایt در شبکهN وجود دارند. مسیرهایk با مسیرp مجمـوعه ای از مسیرهای جهت دارs-t قوس مجزایk+1 را در شبکهN بوجود می آورند. دو ویژگی اصلی شبکه های1-0 تعریف: شبکه1-0 شبکه با ظرفیتی است که ظرفیت های قوس یا صفر یا یک می باشند. دو گزاره بعد با دو خصوصیت شبکه های1-0 اثبات می شوند که نقش مهمی را در اثبات های جریان شبکه قضیه های منجر(Menger) ایفا می کند. گزاره3-3: فرض کنید کهN شبکهs-t باشد کهcap(e)=1 برای هر قوسe‌باشد. از اینرو مقدار ماکسیمم جریان در شبکهN مساوی با ماکسیمم تعداد مسیرهایs-t‌جهت دار قوس مجزا درN‌است. اثبات: فرض کنید کهf* ماکسیمم جریان در شبکهN وr ماکسیمم تعداد مسیرهای جهت دارs-t‌قوس مجزا درN‌باشند. شبکهN*‌را بررسی کنید که از طریق حذف نمودنN از تمامی قوس ها بدست آمده است، یعنیf*(e)=0، سپسf*(e)=1 برای تمام قوس هایe در شبکهN* است. این امر به دنبال تعاریفی برای هر رأسv در شبکهN* است. ∑ e Є Out(s) f*(e) = |Out(v)| = outdegree(v) ∑e Є In(s) f*(e) = |In(v)| = indegree(v) از اینرو در نتیجه تعریفval(f*) و خصوصیت پایستگی جریان outdegree(s) – indegree(s) = val(f*) = indegree(t) - outdegree(t), outdegree(v) = indegree(v), v ≠ s,t 210312074930000در نتیجه گزاره2-3، مسیرهایs-t جهت دار قوس مجزایval(f*) در شبکهN* و همینطور درN وجود دارند، که بیانگرval(f*)≤r می باشد. برای دست یافتن به نابرابری معکوس، فرض کنید که{p1,p2,…,pr} بزرگترین مجموعه مسیرهای جهت دارs-t قوس-مجزا درN باشند- و تابع f:E(N) R+ را بررسی کنید، 2103120-31751, if some path Pi uses arc e 0, otherwise. 001, if some path Pi uses arc e 0, otherwise. f(e) = { از اینروf جریان ممکن در شبکهN باval(f)=r است که بیان می کندval(f*)≤r. مجموعه ها و قطع های تفکیک کننده گزاره بعد برحسب قیاس نمودار مجموعه یال تفکیک کنندهs-t بیان شده است. مرور از§5.3 : فرض کنید کهs وt قوس های جداگانه در نمودارG باشند. مجموعه یال تفکیک کننده درG مجموعه ای از یال هایی است که تفکیک آن تمامی مسیرهایs-t را درG از بین می برد. از اینرو، مجموعه یال تفکیک کننده درG زیر مجموعه یالEG است که حداقل یک یال از هر مسیرs-t درG دارد. تعریف: فرض کنید کهs وt قوسهای خاص در نمودارD باشند. مجموعه قوس تفکیک کنندهs-t درD مجموعه ای از قوس هایی است که تفکیک آن تمامی مسیرهای جهت دارs-t را درD از بین می برد. از اینرو مجموعه قوس تفکیک کنندهs-t درD زیر مجموعه قوسED است که حداقل دارای یک قوس از هر مسیر جهت دارs-t در نمودارD می باشد. نکته: برای حالتی که نمودار اصلی یا نمودار جهت دار مسیرهایs-t ندارد، مجموعه تهی به عنوان مجموعه تفکیک کنندهs-t تلقی شده است. گزاره4-3: فرض کنید کهN شبکهs-t باشد به طوریکهcap(e)=1 برای هر قوسe. سپس ظرفیت مینیمم قطعs-t در شبکهN مساوی با تعداد مینیمم قوس ها در مجموعه تفکیک کنندهs-t درN است. اثبات: فرض کنید کهK*=<Vs,Vt> مینیمم قطعs-t در شبکهN است و فرض نمایید کهq مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t درN می باشد. چونK* قطعs-t است، مجموعه قوس تفکیک کنندهs-t است، پسcap(K*)≥q می باشد. برای دست یابی به نابرابری مساوی، فرض کنید کهs مجموعه قوس تفکیک کنندهs-t در شبکهN است که دارای قوس هایq می باشد وb مجموعه تمامی رأس ها درN‌است که از منبعs از طریق مسیر جهت دار قابل دسترسی می باشند که از مجموعهs هیچ قوسی ندارد. از اینرو، در نتیجه تعاریف مجموعه قوسs و مجموعه رأسR، t ¢ R است، که به این معناست که<R,VN-R> قطعs-t می باشد. علاوه بر این<R,VN-R> زیر مجموعهS است که: Cap(K*) ≤ cap<R,VN-R> =|<R,VN-R>| ≤|S| = q اثبات را کامل می کند. انواع قوس و یال قضیه منجر(Menger) بررسی شده قضیه5-3: [فرم قوس قضیه منجر(Menger)]. فرض کنید کهs وt رأس های مجزا در نمودار جهت دارD‌باشند. پس ماکسیمم تعداد مسیرهایs-t جهت دار قوس مجزا درD مساوی با مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t، ازD است. اثبات: فرض کنید کهN شبکهs-t است که از طـریق تخصیص گنجایـش یکسان به هر قـوس نمودار جهت دارD به دست آمده است. پس نتیجه از گزاره های3-3 و4-3 با قضیهmax-flow min-cut حاصل می شود(قضیه4-2). نکته: برعکس این که شکل قوس قضیه منجر(Menger) یا گزاره های3-3 و 4-3. برای اثبات قضیه max-flow min-cut استفاده شده است. شکل یال قضیه منجر(Menger) برای نمودارهای غیرجهت دار مستقیاً از دو تصدیق بعد در نتیجه رابطه بین نمودارG‌و نمودارG بدست آمده از طریق جایگزینی در یالe از نمودارG با جفتی از قوس های جهت دار به طور معکوس بدست می آید که دارای همان نقاط پایانی به عنوان یالe می باشند. هر یک از این تصدیق ها مستقیاً ناشی از این تعاریف است. تصدیق6-3: فرض کنید کهs وt رأس های مجزای نمودارG باشند وG نمودار بدست آمده از طریق جایگزینی هر یالe ازG با جفتی از قوس های جهت به طور مخالف باشد که همان نقاط پایانی را تحت عنوان یالe دارند پس مینیمم تعداد یال ها در مجموعه یال تفکیک کنندهs-t‌نمودارG مساوی با تعداد مینیمم قوس ها در مجموعه قوس تفکیک کنندهs-t نمودار جهت دارG است. قـضیه8-3: [شکل یـال قضیه مـنجر(Menger)]. فـرض کنید کهsوt رأس های مجزایی در نمـودارG می باشند. سپس ماکسیمم تعداد مسیرهایs-t یال-مجزا درG مساوی با مینیمم تعداد یال ها در مجموعه یال تفکیک کنندهs-t نمودارG است. اثبات: این نتیـجه مـیانی تـصـدیق های6-3 و7-3 با شکل قــوس قضیـه منـجر(Menger) است[قضیه5-3]. تعیین همبندی-یال با استفاده از جریان های شبکه مرور از§5.1 : همبندی-یالke(G) سایز کوچکترین یال-قطع در نمودارG است. تعریف: فرض کنید کهs وt رأس های مجزا در نمودارG باشند. همبندی یال موضعی بین رأس هایs وt که بر ke (s,t) دلالت می کند، مینیمم تعداد یال ها در مجموعه قوس تفکیک کنندهs-t درG‌می باشد. گزاره ذیل نشان می دهد که همبندی-یال نمودار را می توان برحسب همبندی-یال موضعی بین تمامی جفت های رأس ها نشان داد. تصدیق و اثبات آن شبیه به لم5-3-5 و اثبات آن می باشد(از§ 5.3 ). گزاره9-3 و نتایج اثبات شده: ke(G) = min{ ke(s,t)} در اثبـات قضـیه8-3 الگوریـتمی را برای تـعیین همـبندی-یـال ke(G) نمـودار دلخـواهG نشان می دهند. الگوریتم همبندی-یال بین هر جهت از رأس ها را درG به واسطه حل نمودن مسئله خاص ماکسیمم جریان در شبکهG محاسبه می کند(به تصدیق های6-3 و7-3 رجوع نمایید). در واقع محاسبه همبندی-یال موضعی بین هر جفت از رأس ها الزامی نیست، همانطور که دو نتیجه بعدی نشان می دهند. هر دو نتیجه از رابطه بین همبندی-یال موضعی و افراز-قطع ها استفاده می کنند. مرور از §4.6 : فرض کنید کهG نمودار باشد وV1 وV2 افرازVG را به وجود آورند. مجموعه ای از تمام یال هایG‌دارای یک نقطه پایانی در زیر مجموعه رأسV1 و نقطه پایانی دیگر در زیر مجموعه رأسV2 افراز-قطعG نامیده شده است و به شکل<V1,V2> نشان داده شده است. گزاره10-3: فرض کنید که<V1,V2> افراز قطع مینیمم مجموعه اصلی در نمودارG باشند وV1 وV2 به ترتیب هر رأسی درV1 وV2 باشند. از اینرو همبندی-یال ke(G)مساوی با همبندی-یال موضعی ke(v1,v2) است. اثـبات: فـرض کنیـد که مـینیـمم همـبندی-اتـصال یال بـین رأس هایx وy بـدست آمـده است. پس ke(G)= ke(x,y) (براساس گزاره9-3). این مسأله براساس نشان دادن ke(V1,V2) ≤ ke(x,y) کافی است. فرض کنید کهG نمودار بدست آمده در نتیجه جابجایی در یال نمودارG یا دو قوس جهت دار مخالف باشد. سپس نمودارG را می توان به عنوانV1-V2 شبکه با ظرفیتGv1,v2 وx-y شبکه با ظرفیتGxy تلقی نمـود، در حالیکه هر قوس ظرفـیت یکسانی دارد. تصور کنید کهK* مینیمم قطعV1-V2 در شبکهGv1,v2 باشد. کهcap(K*) ≤ cap<V1,V2> را بیان می کند چون افراز قطع<V1,V2> مشابه قطعV1-V2 در شبکهGv1,v2 است. سپس، فرض نمایید کهf* ماکسیمم جریان و<Vx,Vy> مینیمم قطعx-y درx-y شبکهGxy‌باشد سپـسcap<Vx,Vy>=val(f*) می باشد. زنجـیره بعـدی با نامـعادله مـورد نـظر را اثبـات می کنـد. Ke(V1,V2) = cap(K*) ≤ cap<V1,V2> = |<V1,V2>| ≤|<Vx,Vy>| = cap<Vx,Vy> = val(f*) = ke(x,y) نتیجه11-3: فرض کنید کهs هر رأسی در نمودارG باشد. در نتیجه ke(G) = min{ ke(s,t)} اثبات: تصور کنید که<V1,V2> افراز-قطع مینیمم مجموعه اصلی باشد و همچنین بدون از دست دادن اصل کلی، رأس s Є V1است. تعدادی رأس t Є V2وجود دارد(در غیر این صورتEG=0 و تصدیق به طور بدیهی صحیح است) در نتیجه گزاره10-3، این نتیجه به دست می آید ke(G)=ke(s,t) متغیر ke، که در الگوریتم بعدی استفاده می شود، همبندی-یال نمودارG را نشان می دهد و با عدد صحیح مثبت بزرگ|EG| شروع شده است. Algorithm 3.1: Edge-Connectivity Calculation Input: a graph G Output: the edge-connectivity ke of graph G Construct digraph G Let s be an arbitrary vertex of graph G Initialize edge-connectivity ke:=|EG| For each vertex t Є NG-{s} Apply algorithm 2.3 to s-t network G to obtain maximum flow f* If val(f*)<ke Ke:=val(f*) Return ke نکتـه مـحـاسبـه ای: الگوریـتم1-3 به تـکرارهایO(n) نیـاز دارد و چون الگوریتـم3-2 نیـاز به محاسبه هایO(n|E|²) دارد. محاسبه کلی الگوریتم1-3،O(n²|E|²) است. این محاسبه را می توان کاهش داد اگر یکی از الگوریتـم های کارآمدتر ماکسیمم-جریان ذکر شده در بخش های قبلی، به جای الگوریتم3-2 استفاده شود. استفاده از جریان های شبکه برای اثبات اشکال رأس قضیه منجر(Menger) شکل رأس قضیه مـنجر(Menger) برای نمودارهای جهت دار و نمودارها را می توان با استفاده از شکل های قوس و یال اثبات نمود(قضیه های5-3 و8-3). اثبات ها براساس ساختار ذیل قرار گرفته اند. ساختار نمودار جهت دارN^D از نمودار جهت دارD فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودار جهت دارD باشند. نمودار جهت دارN^D از نمودار جهت دارD به شرح زیل بدست آمده است: ـ هر رأسxЄVD-{s,t} متناظر با دو رأسx’ وx” در نمودار جهت دارN^D و قوس جهت دار ازx’ بهx” است. ـ هر قوس در نمودار جهت دارD که از رأسsبه رأس xЄVD-{s,t}جهت یافته است متناظر با قوس در نمودار جهت دارN^D جهت یافته ازs بهx’ می باشد. ـ هر قوس درD که از رأسxЄVD-{s,t} به رأسt جهت یافته است متناظر به قوس درN^D جهت یافته ازx” بهt است. 4663440601980x” 00x” 1645920601980x 00x ـ هر قوس درD که از رأس xЄVD-{s,t}به رأس yЄVD-{s,t}جهت یافته است متناظر با قوس درN^D جهت یافته ازx” بهy’ می باشد. 42976802540x’ 00x’ 3840480642620s 00s 2286000-19685y 00y 45720001333500048463201333500053949604191000493776041910004572000419100048463204191000530352041910001920240118110005638800-225425y” 00y” 5669280444500057099201663700044805604445000411480014033500250952015811500219456011811000246888026670001920240266700018288002667000146304011811000 5212080-460375y’ 00y’ 5943600187325t 00t 540067522415500594360012827000420624022415500411480012827000274320018415t 00t 274320010985500219456020129500155448020129500146304010985500 3108960171450004846320262890004480560262890z’ 00z’ 5303520171450004754880179070002011680247650z 00z 210312015621000 3108960122555شکل 1-3 00شکل 1-3 1188720-772795s 00s 5212080-528320z” 00z” مرور از §5.3: فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودارG(یا نمودار جهت دارD) باشند. مجموعه رأس تفکیک کنندهs-t درG(یاD) مجموعه ای از رأس هایی است که تفکیک آن تمامی مسیرهایs-t را درG(یا تمامی مسیرهای جهت دارs-t درD) را از بین می برد. از اینرو، مجموعه رأس تـفکیک کنندهs-t مجمـوعه ای از رأس هایی است که حـداقل دارای یک رأس داخلی در هر مسیرs-t (جهت دار) است. تعریف: دو مسیر(جهت دار)s-t در نمودار جهت دارD از لحاظ درونی مجزا می باشند اگر آنها کاملاً رأس های داخلی نداشته باشند. روابط بین نمودارهای جهت دارD وN^D اشکال رأس قضیه منجر(Menger) به آسانی از چهار رابطه بین نمودار جهت دارD و نمودار جهت دار متناظر آنN^D به دست می آیند. هر یک از اینها از تعاریفی تبعیت می کنند: تصدیق12-3: انطباق یک به یکی بین مسیرهای جهت دارs-t در نمودار جهت دارD و مسیرهای جهت دارs-t در نمودار جهت دارN^D وجود دارد. تصدیق13-3: دو مسیر جهت دارs-t درD از لحاظ داخلی مجزا می باشند اگر مسیرهای جهت دار متناظرs-t آنها درN^D، قوس مجزا باشند. تصدیق14-3: ماکسیمم تعداد مسیرهایs-t جهت دار مجزا از احاظ داخلی درD‌مساوی با ماکسیمم اعداد مسیرهایs-t جهت دار قوس-مجزا درN^D است. تصدیق15-3: مینیمم تعداد رأس ها در مجموعه رأسs-t تفکیک کننده در نمودار جهت دارD مساوی با مینیمم تعداد قوس ها در مجموعه قوس تفکیک کنندهs-t در نمودار جهت دارN^D می باشد. قضیه16-3: [شکل رأس از منجر(Menger) برای نمودارهای جهت دار]. فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودار جهت دارD باشند. سپس ماکسیمم تعداد مسیرهای جهت دار مجزایs-t درD مساوی با مینیمم تعداد رأس ها در رأس تفکیک کنندهs-t درD است. اثـبـات: ایــن اثبـات به هـمــراه تصــدیــق12-3 تا 15-3 با شــکل قــوس قــضـیه مـنجـر(Menger) می باشد(قضیه5-3). قضیه17-3: [شکل رأس منجر(Menger) برای نمودارهای غیرجهت دار]. فرض کنید کهs وt جفتی از رأس های غیرمجزا در نمودارG‌باشند. از اینرو ماکسیمم تعداد مسیرهایs-t مجزا از لحاظ داخلی درG مساوی با مینیمم تعداد رأس ها در مجموعه تفکیک کنندهs-t درG است. اثبات: فرض کنید کهG نمـودار جهت داری باشد که از طریـق جایـگزینی هر یالe ازG با جفتی از قوس های جهت دار معکوس بدست آمده است که همانند یالe نقاط پایانی دارند. نتیجه به واسطه قضیه16-3 و تصدیق های6-3 و7-3 بدست می آیند. تعیین همبندی-رأس با استفاده از جریان های شبکه اثبات شکل رأس قضیه منجر(Menger) که براساس تئوری جریان های شبکه قرار گرفته است منجر به الگوریتمی برای تعیین همبندی-رأس نمودار می شود، در اکثر موارد شکل یال قضیه منجر(Menger) موجب تشکیل الگوریتمی برای همبندی-یال می شود. مرور از §5.3: فرض کنید کهs وt رأس های غیرمجاور نمودار متصل شدهG باشند. از اینرو، همبندی-یال موضعی بینs وt که به شکلKv(s,t) نشان داده شده است، مینیمم تعداد رأس ها در مجموعه رأس تفکیک کنندهs-t است. مرور از لم5-3-5: فرض کنید کهG نمودار به هم پیوسته ای باشد که حداقل دارای یک جفت رأس غیرمجاور است. از اینرو همبندی-رأسKv(G) مینیمم همبندی-رأسKv(s,t) است که شامل تمامی جفت های رأس های غیرمجاورs وt می باشند. نکته: الگوریتم ذیل، که پیچیدگی زمانیO(n|EG|³) را دارد، همبندی-رأس نمودار رأسn را از طریق محاسبه همبندی-رأس موضعی بین جفت های مختلف رأس های غیرمجاور محاسبه می نماید. همانند الگوریتم1-3، محاسبه همبندی-رأس موضعی بین هر جفت الزامی نیست. اثبات صحت آن و پیچیدگی زمانی آن حذف شده اند اما ممکن است یافت شوند. متغیرKv که در الگوریتم2-3 شهود است، همبندی-رأس نمودارG را نشان می دهد و با عدد صحیح مثبت نسبتاً بزرگ|VG| شروع شده است. Algorithm 3.2: Vertex-Connectivity Calculation Input: an graph G with VG={v1,v2,…,vn} Output: the vertex-connectivity ke of graph G Construct digraph G Construct digraph N^G Assing unit capacity to each arc in digraph N^G Initialize edge-connectivity ke:=|VG| Initialize index k:=0 While k≤kv K:=k+1 For j=k+1 to n If vertices vk and vj are not adjacent Apply algorithm 2.3 to network N^G with source vk And sink vj to obtain maximum flow f* If val(f*)<kv Kv:=val(f*) Return kv


دسته‌بندی نشده

سایت ما حاوی حجم عظیمی از مقالات دانشگاهی است . فقط بخشی از آن در این صفحه درج شده شما می توانید از گزینه جستجو متن های دیگری از این موضوع را ببینید 

کلمه کلیدی را وارد کنید :

دسته بندی: دسته‌بندی نشده

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

مطالب مرتبط

دسته‌بندی نشده

3 (1140)

واژه «شطرنج»تلفظ فارسی «چاتورانگا » است کلمه ای که در زبان سانسکریت برای نام گذاری این بازی به کار برده می شود،جایی که معمولاً از آن به عنوان نخستین زادگاه این بازی یاد می شود. اگر ادامه مطلب…

دسته‌بندی نشده

3 (1141)

بررسی تاریخ شناخت تاریخچه و علل پیدایش شهر شهر نیشابور مانند سایر شهرهای استان خراسان جزء اولین مراکز مسکونی است که اقوام آریایی پس از ورود به ایران در آن سکنی گزیدند. خراسان قدیم به ادامه مطلب…

دسته‌بندی نشده

3 (1142)

بنام خدا سازمان صنایع کوچک و شهرکهای صنعتی ایران شرکت شهرکهای صنعتی مازندران معاونت صنایع کوچک طرح امکان سنجی "پارچه بافی" پاییز 85 فهرست مطالب فصل اول بررسی بازار مطالعه و شناخت محصول...............................................................................................................................4 عوامل موثردر ادامه مطلب…

background