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

پایان نامه رشته ریاضی کاربردی

سال 1383 

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-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)

ترجمه: دكتر محمد علي رضواني و دكتر بيژن شمس

انتشارات فاطمي

2)

ترجمه: دكتر جعفر بي آزار

انتشارات دانشگاه گيلان

3)

ترجمه : حميد ضرابي زاده

موسسه فرهنگي هنري ديباگران تهران