دانلود پایان نامه شبكه ها و تطابق در گراف 50ص

فهرست مطالب

شبكه ها

• شارش ها

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

تعريف 1-1 فرض كنيم N=(V,E) يك گراف سودار همبند بيطوقه باشد. N را يك شبكه يا يك شبكه حمل و نقل مي‌نامند هرگاه شرايط زير برقرار باشند:

(الف) رأس يكتايي مانند  وجود دارد به طوري كه ، يعني درجة ورودي a، برابر 0 است. اين رأس a را مبدأ يا منبع مي‌نامند.

(ب) رأس يكتايي مانند  به نام مقصد يا چاهك، وجود دارد به

-3 قضيه شارش ماكزيمم – برش مينيمم

در اين بخش الگوريتمي براي تعيين يك شارش ماكزيمم در شبكه ها ارائه مي‌نمائيم. يكي از اساسي‌ترين ملزومات چنين الگوريتمي اين است كه در صورت ديدن يك شارش، بتواند تشخيص دهد آيا اين شارش ماكزيمم هست يا خير. بنابراين در شروع كار، نگاهي به اين مسأله مي‌اندازيم.

فرض كنيد f يك شارش در شبكه N باشد. به هر مسير S در N، يك عدد صحيح نامنفي l(S) به صورت روبرو نسب مي‌دهيم:

كه در آن:

به راحتي مي توان ديد كه l(S)، بيشترين ميزان ممكن براي افزايش شارش در طول S (تحت f) است، بدون اينكه به شرط الف در تعريف 1-2 آسيبي وارد شود. اگر ، مسير S را f- اشباع شده و اگر ، S را f– اشباع نشده مي‌ناميم (حالت…

402 مساله تخصيص شغل

در اين بخش به بيان كاربردي از نظريه تطابق مي پردازيم.

در يك شركت تفنن n كارگر  براي n كار  موجودند و هر كارگر قادر است كه يك يا تعداد بيشتري كار را انجام دهد . آيا مي توان تمام كارها را بين اين افراد طوري تقسيم كرد به طوري كه هر كس قادر به انجام كاري كه به آن گماشته شده باشد؟ اين مساله مساله تخصيص شغل معروف است.

يك گراف در بخش G با دو بخش y,x مي سازيم به طوري كه  و  و  به متصل باشد اگر و تنها اگر كارگر  قادر به انجام كار  باشد . بدين ترتيب مساله ما تبديل مي شود به تعيين اين كه آيا G داراي تطابق كامل هست يا خير ؟ طبق قضيه هال (202) ، يا G داراي چنين هست يا زير مجموعه اي مانند محور x وجود دارد كه . در ادامه الگوريتمي براي حل مساله تعيين شغل ارائه مي دهيم.

يك گراف دو بخشي G با دو بخشy,x داده شده است. الگوريتم مورد نظر يا يك تطابق از G كه تمام راس هاي x را آلوده…

منابع

• رياضيات گسسته و تركيباتي ، مؤلف: رالف پ. گريمالدي

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

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

• درآمدي بر نظرية گراف، مؤلف: ربين ج. ويلسون

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

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

• نظرية گراف و كاربردهاي آن، مؤلفين: جي.اي.باندي و يو.اس.ار.مورتي

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

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