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

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)
ب) اگر a مبدأ N باشد، را مقدار شارش می نامند.

مثال 1-3 در شبکه شکل 1-2 (ب) فقط کمان اشباع شده است.

هر یک از کمان‌های دیگر اشباع نشده است.

مقدار شارش این شبکه
است.

ولی آیا شارش دیگری مانند وجود دارد که به ؟

می‌گوئیم شارش fدر N، یک شارش ماکزیمم است، هر گاه هیچ شارش دیگری مانند در N با شرط وجود نداشته باشد.

هدف ما در ادامه، تعیین یک شارش ماکزیمم است.

برای انجام این کار، ملاحظه می‌کنیم که در شکل 1-2 (ب) داریم.

درنتیجه، شارش کل خارج شده از مبدأ a شارش کل وارد شده به مقصد z برابر است.

نکته اخیر در مثال 1-3 شرط معقولی به نظر می‌رسد، ولی آیا در حالت کلی چنین وضعیتی روی می دهد؟

برای اثبات آن در مورد هر شبکه دلخواه به نوع خاصی از مجموعه های برشی که در قسمت بعد می‌آید، نیاز داریم.

برش ها تعریف 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 باشد، مقدار