فهرست مطالب

شبكه ها

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