فهرست مطالبشبكه هاشبكه هاي حمل و نقل، واسطه‌هايي براي فرستادن كالاها از مراكز توليد به فروشگاهها هستند. اين شبكه ها را مي‌توان به صورت يك گراف جهت دار با يك سري ساختارهاي اضافي درنظر گرفت و آن ها را به صورت كارآيي مورد تحليل و بررسي قرار داد. اين گونه گراف هاي جهت دار، نظريه اي را به وجود آورده اند كه موضوع مورد بحث ما در اين فصل مي باشد. اين نظريه ابعاد وسيعي از كاربردها را دربرمي‌گيرد.تعريف 1-1فرض كنيم N=(V,E) يك گراف سودار همبند بيطوقه باشد. N را يك شبكه يا يك شبكه حمل و نقل مي‌نامند هرگاه شرايط زير برقرار باشند:(الف) رأس يكتايي مانند وجود دارد به طوري كه ، يعني درجة ورودي a، برابر 0 است. اين رأس a رامبدأيامنبعمي‌نامند.(ب) رأس يكتايي مانند به ناممقصدياچاهك، وجود دارد به-3 قضيه شارش ماكزيمم – برش مينيممدر اين بخش الگوريتمي براي تعيين يك شارش ماكزيمم در شبكه ها ارائه مي‌نمائيم. يكي از اساسي‌ترين ملزومات چنين الگوريتمي اين است كه در صورت ديدن يك شارش، بتواند تشخيص دهد آيا اين شارش ماكزيمم هست يا خير. بنابراين در شروع كار، نگاهي به اين مسأله مي‌اندازيم.فرض كنيد f يك شارش در شبكه N باشد. به هر مسير S در N، يك عدد صحيح نامنفي l(S) به صورت روبرو نسب مي‌دهيم:اگر t يك كمان رو به جلو از S باشد.اگر t يك كمان معكوس از 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 را آلوده...منابعترجمة: دكتر محمد علي رضواني و دكتر بيژن شمسانتشارات فاطميترجمة: دكتر جعفر بي آزارانتشارات دانشگاه گيلانترجمة : حميد ضرابي زادهموسسه فرهنگي هنري ديباگران تهران