دانلود مقاله شبکه ها و تطابق در گراف

اختصاصی از فی دوو دانلود مقاله شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

1-1 شارش ها
شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.
تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:
(الف) رأس یکتایی مانند وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.
(ب) رأس یکتایی مانند به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.
(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان یک ظرفیت، که با نشان داده می‌شود، نسبت می‌دهد.
برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.
مثال 1-1 گراف شکل 1-1 یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون ، مقدار کالای حمل شده از a به z نمی‌تواند از 12 بیشتر شود. با توجه به بازهم این مقدار محدودتر می‌شود و نمی‌تواند از 11 تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد باید ظرفیتهای همة کمانهای بشکه را درنظر بگیریم.

تعریف 1-2 فرض کنیم یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه
الف) به ازای هر کمان و
ب) به ازای هر ، غیر از مبدأ a یا مقصد z ، (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم
مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.
شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همة رأسها به استثنای مبدأ و مقصد بر قرار است.
مثال 1-2 در شبکه های شکل 1-2، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در صدق می کند. در شکل 1-2 (الف)، شارش، وارد رأس می شود،5 است، ولی شارشی که از آن رأس خارج می شود 4=2+2 است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل 1-2 (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.
توجه داشته باشید که هر شبکه، حداقل دارای یک شارش است، زیرا تابع fای که در آن به ازای هر داشته باشیم: در هر دو شرط تعریف
1-2 صدق می کند. این تابع، شارش صفر نامیده می شود.
تعریف 1-3 فرض کنیم f شارشی برای شبکة حمل و نقل N=(V,E) باشد.
الف) کمانی مانند e متعلق به این شبکه را اشباع شده می نامند هر گروه f(e)=c(e) اگر f(e)<c(e) این کمان را اشباع نشده می نامند.
ب) اگر a مبدأ N باشد، را مقدار شارش می نامند.
مثال 1-3 در شبکه شکل 1-2 (ب) فقط کمان اشباع شده است. هر یک از کمان‌های دیگر اشباع نشده است. مقدار شارش این شبکه

است. ولی آیا شارش دیگری مانند وجود دارد که به ؟
می‌گوئیم شارش fدر N، یک شارش ماکزیمم است، هر گاه هیچ شارش دیگری مانند در N با شرط وجود نداشته باشد.
هدف ما در ادامه، تعیین یک شارش ماکزیمم است. برای انجام این کار، ملاحظه می‌کنیم که در شکل 1-2 (ب) داریم.

درنتیجه، شارش کل خارج شده از مبدأ a شارش کل وارد شده به مقصد z برابر است.
نکته اخیر در مثال 1-3 شرط معقولی به نظر می‌رسد، ولی آیا در حالت کلی چنین وضعیتی روی می دهد؟ برای اثبات آن در مورد هر شبکه دلخواه به نوع خاصی از مجموعه های برشی که در قسمت بعد می‌آید، نیاز داریم.
1-2 برش ها
تعریف 1-4 اگر یک شبکهء حمل و نقل و C یک مجموعة برشی برای گراف بیسوی وابسته به N به صورت که در آن باشد، C را یک برش یا یک برش a-z می نامند هرگاه حذف کمانهای C از شبکة مفروض به جدایی a و z منتهی شود.
ظرفیت هر برش، که با capC نشان داده می شود، با
(1-1)
یعنی مجموع ظرفیتهای همة کمانهای (y,w) که در آن و ، تعریف می‌شود.
مثال 1-4 هر یک از خمهای خط چین در شکل 1-3 برشی برای شبکة مفروض است. برش از کمانهای بیسوی تشکیل شده است. این برش رأسهای شبکة مفروض را بر دو مجموعة و متمم آن، یعنی ، افرازی می‌کند و در این مثال . ] در برش ، اگر یالهای سودار (از P به )، یعنی یالهای ، را درنظر بگیریم می بینیم که حذف این یالها به زیرگرافی با دو مؤلفه منتهی نمی شود. ولی، این سریال مینیمال اند، به این معنی که حذف آنها امکان پیدایش هر مسیر سودار از a به z را از بین می برد[
برش افراز و را برای رأسها القا می‌کند و دارای ظرفیت است.
قضیه 1-1 فرض کنیم f شارشی در شبکة N=(V,E) باشد. اگر برشی در N باشد، آنگاه Val(f) نمی تواند از تجاوز کند.
اثبات فرض کنیم رأس a مبدأ N و رأس Z مقصد آن باشد. چون ، پس به ازای هر ، . درنتیجه،

با توجه به شرط (ب) در تعریف شارش، به ازای هر و ، داریم

اگر برابریهای بالا را به هم بیفزاییم خواهیم داشت:



چون مجموعه های و
روی کل مجموعه متشکل از همة جفتهای مرتب متعلق به P×P محاسبه شده اند، با یکدیگر برابرند. درنتیجه،
(1-2)
به ازای هر ، داریم و از این رو، و
(1-3) .
با توجه به قضیة 1-1 می‌بینیم که در شبکه ای مانند N، مقدار هر شارش کوچکتر از یا برابر با ظرفیت هر برش موجود در آن شبکه است. بنابراین مقدار شارش ماکزیمم نمی تواند از مینیمم ظرفیتهای برشهای شبکه تجاوز کند. در مورد شبکة شکل 2-3 می توان نشان داد که برش متشکل از یالهای و دارای ظرفیت مینیمم 11 است. درنتیجه شارش ماکزیمم f برای این شبکه در صدق می کند.
تعریف 1-5 برش C در N، یک برش مینیمم است، اگر هیچ برش دیگری مانند در N با شرط وجود نداشته باشد.
اگر یک شارش ماکزیمم و یک برش مینیمم به عنوان حالت خاصی از قضیه 1-1 داریم: (1-4)
نتیجه 1-1 فرض کنید f یک شارش و C یک برش باشد، به طوری که در این صورت f یک شارش ماکزیمم و C یک برش مینیمم است.
اثبات فرض کنید یک شارش ماکزیمم و یک برش مینیمم باشد. در این صورت بنا بر رابطة 1-4 داریم:

و چون طبق فرض، ، نتیجه می‌گیریم که و درنتیبجه f یک شارش ماکزیمم و C یک برش مینیمم است .
در بخش آینده، عکس نتیجه 1-1 را اثبات خواهیم کرد، یعنی این که در رابطة 1-4 همواره تساوی برقرار است.
ولی، قبل از پرداختن به این مطلب، با توجه به برهان قضیه 1-1 ملاحظه میکنیم که مقدار هر شارش با

که در آن برشی دلخواه در N است، بیان می شود. بنابراین، به محض آنکه شارشی در شبکه ای ساخته شد، به ازای هر برش در این شبکه، مقدار شارش برابر است با مجموع شارشهای موجود در کمان های سودار از رأسهای P به رأسهای منهای مجموع شارشهای موجود در کمان های سودار از رأسهای به رأسهای P.
این نکته ما را به نتیجة زیر هدایت می کند.
نتیجة 1-2 اگر f شارشی در شبکة حمل و نقل N=(V,E) باشد، انگاه مقدار شارش خارج شده از مبدأ a برابر است با مقدار شارش وارد شده در مقصد z.
اثبات قرار می دهیم . با توجه به نکته قبلی داریم:

چون و ، می‌بینیم که
به همین ترتیب، به‌ازای و داریم
درنتیجه،

و این اثبات تمام است.

1-3 قضیه شارش ماکزیمم – برش مینیمم
در این بخش الگوریتمی برای تعیین یک شارش ماکزیمم در شبکه ها ارائه می‌نمائیم. یکی از اساسی‌ترین ملزومات چنین الگوریتمی این است که در صورت دیدن یک شارش، بتواند تشخیص دهد آیا این شارش ماکزیمم هست یا خیر. بنابراین در شروع کار، نگاهی به این مسأله می‌اندازیم.
فرض کنید f یک شارش در شبکه N باشد. به هر مسیر S در N، یک عدد صحیح نامنفی l(S) به صورت روبرو نسب می‌دهیم:
که در آن:

به راحتی می توان دید که l(S)، بیشترین میزان ممکن برای افزایش شارش در طول S (تحت f) است، بدون اینکه به شرط الف در تعریف 1-2 آسیبی وارد شود. اگر ، مسیر S را f- اشباع شده و اگر ، S را f– اشباع نشده می‌نامیم (حالت اخیر معادل با این است که هر کمان رو به جلو از S، f – اشباع نشده و هر کمان معکوس از S، f- مثبت باشد). به طور ساده می‌توان گفت که یک مسیر f- اشباع نشده، مسیری است که از تمام ظرفیتش استفاده نشده است. مسیر -f افزایشی یک مسیر -f اشباع نشده از مبدأ a به مقصد z می باشد. به طور مثال اگر f شارش مشخص شده در شبکه شکل 1-4 (الف) باشد، در این صورت یک مسیر -f افزایشی خواهد بود. و کمان‌های روبه جلوی S هستند و داریم .
وجود یک مسیر -f افزایشی S در شبکه حائز اهمیت است، زیرا نشان می دهد که f شارش ماکزیمم نیست.
در حقیقت با فرستادن یک شارش اضافی l(S)، در طول S، می توان به شارش جدید ، به صورت زیر رسید:

و در این حال داریم: را شارش اصلاح شده بر پایة S می ‌خوانیم.
در شکل 1-4 (ب) شارش اصلاح شده شبکه 1-4 (الف) بر پایه مسیر -f افزایشی نشان داده شده است.
شکل 1-4 (الف) مسیر -f افزایشی S (ب) شارش اصلاح شده بر پایه f
در شکل (الف)

در شکل (ب)

نقش مسیرهای افزایشی درنظریه شاره‌ها همانند مسیرهای افزوده درنظریه تطابق هاست. قضیه زیرمؤید این مطلب است (آن را با قضیة 2-1 مقایسه نمائید.)
قضیه 1-2 شارش f در N ماکزیمم است، اگر و تنها اگر N دارای هیچ مسیر
-f افزایشی نباشد.
اثبات اگر N شامل یک مسیر -f افزایشی S باشد، در این صورت f نمی تواند یک شارش ماکزیمم باشد. زیرا ، شارش اصلاح شده بر پایه S، دارای مقدار بزرگتری است.
برعکس، فرض کنید که N شامل هیچ مسیر -f افزایشی نباشد. می‌خواهیم نشان دهیم که f یک شارش ماکزیمم است. فرض کنید P مجموعه تمام رأس هایی باشد که a توسط مسیرهای -f اشباع نشده در N به آن ها متصل است. به وضوح داریم . از طرفی چون N دارای هیچ مسیر -f افزایشی نیست، پس . بنابراین یک برش در N است. در ادامه نشان خواهیم داد که هر کمان ، -f اشباع شده و هر کمان ، -f صفر است.
فرض کنید t کمانی با دم و سر باشد. از آن جایی که پس (a,u)- مسیر -f اشباع نشده مانند Q وجود دارد. اگر t، -f اشباع نشده باشد، در این صورت Q را می توان با افزودن کمان t به مسیر Q، به یک (a,v) – مسیر -f اشباع نشده گسترش داد. ولی با توجه به اینکه ، چنین میسری وجود ندارد و بنابراین t باید -f اشباع شده باشد. با استدلال مشابهی می‌توان نتیجه گرفت که اگر ، آنگاه t باید -f صفر باشد.
با به کارگیری قضیه 1-1 نتیجه می شود:

و اکنون با توجه به نتیجه 1-1 روشن می گردد که f، یک شارش ماکزیمم (و C یک برش مینیمم است.) 
طی اثبات فوق، وجود یک شارش ماکزیمم و یک برش مینیمم C که در آن ها شرط برقرار است، به اثبات رسید. بنابراین قضیه زیر که متعلق به فورد، فالکرسن (1956) است، نیز مستقیماً به اثبات می‌رسد:
قضیه 1-3 قضیه شارش ماکزیمم – برش مینیمم. در هر شبکة حمل و نقل ، شارش ماکزیمم که می‌توان در N به دست آورد برابر است با مینیمم ظرفیتهای برشهای این شبکه.
اثبات بنابرقضیه 1-1 اگر برشی با ظرفیت مینیمم در N باشد، مقدار هر شارشی در N مانند f در نابرابری صدق می‌کند. برای تحقیق در وجود شارشی مانند f که به ازای آن داشته باشیم ، الگوریتم زیر، که روش نشانگذاری نام دارد، مراحل لازم را در اختیار می گذارد. 
روش نشانگذاری
مرحله 1: در شبکه مفروض N، شارش آغازی f در N را به ازای هر کمان e متعلق به E با تعریف می‌کنیم. این تابع در شرایط شارش صدق می‌کند.
مرحلة 2: مبدأ a را با نشانگذاری می کنیم. (تین نشانگذاری نشان می دهد که در مبدأ a، هر اندازه ماده برای تحقق شارش ماکزیمم لازم باشد موجود است.)
مرحلة 3: به ازای هر رأس مانند x که مجاور از a است، x را به صورت زیر نشانگذاری می‌کنیم:
الف) اگر ، تعریف می‌کنیم و رأس x را با نشانگذاری می‌کنیم.
ب) اگر ، راس x را بدون نشان رها می‌کنیم. ] نشان بر این امر دلالت دارد که شارش فعلی از a به x را می توان به مقدار افزایش داد و این واحد اضافی از مبدأ a تأمین می شود.[
مرحلة 4: تا زمانی که رأس نشانداری مانند و یالی مانند (x,y) که در آن y بی‌نشان است، وجود دارد و رأس y را به صورت زیر نشانگذاری می‌کنیم.
الف)اگر ،تعریف‌میکنیم و رأس y را با نشانگذاری می‌کنیم.
ب) اگر ، رأس y را بدون نشان رها می‌کنیم.
]نشان بر این امر دلالت دارد که شارش فعلی وارد شده و در رأس y را می توان به مقدار ، که از رأس x می گیریم، افزایش داد.[
مرحلة 5: به همین ترتیب، تا زمانی که رأس نشانداری مانند و کمانی مانند (y,x)، که در آن y بی نشان است، وجود دارد رأس y مقابل را به صورت زیر نشانگذاری می کنیم:
الف) اگر ، راس y را با ، که در آن نشانگذاری می‌کنیم.
ب) اگر ، رأس y را بدون نشان رها می کنیم.
J نشان به ما می گوید که با کاهش شارش از y به x، شارش کل خارج شده از y به رأسهای نشاندار را می توان به اندازة کاهش داد. در این صورت این واحد را می توان برای افزایش شارش کل خارج شده از y با رأسهای بی نشان به کار گرفت.[
چون رأسی مانند y ممکن است مجاور به یا مجاور از بیش از یک رأس نشاندار باشد، نتایج این روش الزاماً یکتا نیست. علاوه بر این، اگر x نشانگذاری شده باشد، شبکة مورد بحث ممکن است شامل هر دو کمان (x,y) و (y,x) باشد و بنابراین، ممکن است دو نشان برای y حاصل شود. ولی این روش برای آن طراحی شده است که یک شارش ماکزیمم به دست دهد و این امکان هست که بیش از یک چنین شارشی موجود باشد. به هر حال هر بار که بتوان رأسی را به بیش از یک طریق نشانگذاری کرد، باید یکی را به دلخواه انتخاب کنیم.
ضمن اینکه روش نشانگذاری را در بارة رأسهای شبکة مفروض به کار می‌بریم، مراحل 4 و 5 تا حد امکان در مورد مجموعة جاری (و در حال تغییر) رأسهای نشانگذاری شده تکرار می شوند. با هر تکرار دو حالت ممکن است روی رهد.
حالت 1: اگر مقصد z با نشانگذاری شود، شارش موجود در کمان (x,z) را می توان مطابق نشانگذاری، از f(x,z) به افزایش داد.
رأس x را می توان با یا ، که در آن ، نشانگذاری کرد. در ارتباط با نشان ، می توانیم برای افزایش شارش موجود در کمان (x,z) به مقدار ، رأس v را به عنوان مبدأ تلقی کنیم. در این حالت نیز شارش حاضر در کمان (v,x) را از f(v,x) به (و نه به ) افزایش می‌دهیم.
اگر x دارای نشان باشد، در این صورت، برای تأمین شارش اضافی واحدی از x به z شارش موجود در یال (x,v) را از f(x,v)به تغییر می دهیم.
به تدریج این فرایند به مبدأ a بازمی‌گردد، شارش موجود در هر کمان متعلق به مسیری که از a به z می رود، به اندازة واحد افزایش یا کاهش می‌یابد ]کاهش مربوط به وقتی است که رأسی (از این مسیر) نشان منفی داشته باشد[. پس از اتمام کار، همة نشانهای رأسها، به استثنای که مربوط به مبدأ است، حذف می‌شوند. این فرایند تکرار می شود تا ببینیم آیا امکان دارد که بازهم شارش را افزایش دهیم یا نه.
حالت 2: اگر روش نشانگذاری را تا حد امکان اجرا کنیم و مقصد z بی نشان باقی بماند، شارش ماکزیمم حاصل شده است. فرض کنیم P مجموعة رأسهایی از V باشد که نشانگذاری شده اند و . چون رأسهای نشانگذاری نشده اند، شارشهای موجود در کمان های (x,y)، که در آن و ، در صدق می کنند.
همچنین، به ازای هر کمان (w,v)، و ، داریم . درنتیجه، شارشی برای شبکة مفروض وجود دارد به طوری که مقدار شارش برابر است با ظرفیت برش . با توجه به قضیة 1-1 نتیجه می‌گیریم که این شارش یک شارش ماکزیمم است.
قبل از ارائه مثالی در بارة روش نشانگذاری، یک نتیجه دیگر و چند تفسیر وابسته به آن را بیان می کنیم.
نتیجه 1-3 فرض کنیم N=(V,E) یک شبکة حمل و نقل باشد که در آن، به ازای هر ، c(e) یک عدد صحیح مثبت است. آنگاه شارش ماکزیممی مانند f برای N وجود دارد به طوری که، به ازای هر کمان e، f(e) یک عدد صحیح نامنفی است.
در تعریف شبکه حمل و نقل و شارش (در یک شبکة حمل و نقل) می توانیم این امکان را مد نظر قرار دهیم که توابع ظرفیت و شارش توابعی حقیقی و نامنفی باشند. اگر در یک شبکة حمل و نقل ظرفیتها اعدادی گویا باشند، در این صورت رو نشانگذاری پایان پذیر است و به شارش ماکزیمم دست خواهیم یافت. ولی، اگر بعضی از ظرفیتها اعداد گنگ باشند، این امکان وجود دارد که این روش پایانی نداشته باشد، به این ترتیب که برای هر تکرار، های کوچکتری پدید آید. علاوه بر این، ال. آرفورد جونیور و دی. آر. فاکرسون نشان دادند که این روش می تواند به یک شارش منتهی شود، ولی این شارش لزوماً یک شارش ماکزیمم نیست. وقتی ظرفیتهای گنگ پیش می آیند می توان اصلاحیة ارائه شده به وسیلة جی. ادموندز. آر.ام.کارپ را به کار برد و در این صورت این روش (پس از تعدادی متناهی مرحله) پایان می‌پذیرد و به یک شارش ماکزیمم دست می‌یابیم.
مثال 1-5 با استفاده از روش نشانگذاری، شارش ماکسیممی برای شبکة حمل و نقل شکل 1-5 (الف) بیابید. در این شبکه، هر کمان با جفت مرتبی مرکب از x و y نشانگذاری شده است، که در آن x ظرفیت کمان است و شارش آغازی برای شبکه را نشان می دهد. شکل 1-5 (ب) نخستین کاربرد روش نشانگذاری را در بارة این شبکه نشان می دهد. در اینجا نشانگذاری مقصد z بر اساس انتخاب صورت گرفته است. را به جای به عنوان نشان انتخاب کرده ایم اگر از z به h به e به s به a بازگردیم و شارش موجود در هر ریال را به اندازة افزایش دهیم، شارش جدید در شکل
1-5 (ب) را به دست می‌آوریم. شکلهای 1-5 (پ)، (ت)، (ث) و (ج) کاربردهای دوم، سوم، چهارم، و پنجم روش نشانگذاری را در بارة شبکة مفروض نشان می‌دهند. ملاحظه می‌کنیم که چگونه رأس در شکل های 1-5 (ت) و (ج) نشان منفی دارد. همچنین، شکل 1-5 (ج) موقعیت دیگری نشانگذاری منفی را، این بار برای رأس d، به دست می دهد. اگر برای آخرین بار روش نشانگذاری را به کار ببریم، شبکة حمل و نقل مفروض مطابق شکل 1-6 نشانگذاری می شود. در اینجا مقصد z بی نشان است و حالت دوم در روش نشانگذاری مطرح می شود. 

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله 43   صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید