فایل مارکت

جزوه شبكه ها و تطابق در گراف

شبكه ها

• شارش ها

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

تعريف 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 شرط معقولي به نظر مي‌رسد، ولي آيا در حالت كلي چنين وضعيتي روي مي دهد؟ براي اثبات آن در مورد هر شبكه دلخواه به نوع خاصي از مجموعه هاي برشي كه در قسمت بعد مي‌آيد، نياز داريم.

فهرست مطالب

جزوه شبكه ها و تطابق در گراف