بررسی شبكه ها و تطابق در گراف

بررسی شبكه ها و تطابق در گراف
بررسی شبكه ها و تطابق در گراف
70,000 ریال 
تخفیف 15 تا 30 درصدی برای همکاران، کافی نت ها و مشتریان ویژه _____________________________  
وضعيت موجودي: موجود است
تعداد:  
افزودن به ليست مقايسه | افزودن به محصولات مورد علاقه

تعداد صفحات: 51 صفحه _فرمت word _ دانلود مطالب بلافاصله پس از پرداخت آنلاین

فهرست مطالب

مقدمه   
فصل 1   
شبكه ها   
1-1 شارش ها   
1-2 برش ها   
1-3 قضيه شارش ماكزيمم – برش مينيمم   
1-4 قضيه منجر   
   
فصل 2   
تطابق ها   
2-1 انطباق ها   
2-2 تطابق ها و پوشش ها در گراف هاي دو بخش   
2-3 تطابق كامل   
2-4 مسأله تخصبص شغل   
   

شبكه ها
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 (ب) در هر دو شرط صدق مي كند و بنابراين، شارشي براي شبكهء مفروض است.



منابع
1)    رياضيات گسسته و تركيباتي ، مؤلف: رالف پ. گريمالدي
ترجمة: دكتر محمد علي رضواني و دكتر بيژن شمس
انتشارات فاطمي
2)    درآمدي بر نظرية گراف، مؤلف: ربين ج. ويلسون
ترجمة: دكتر جعفر بي آزار
انتشارات دانشگاه گيلان
3)    نظرية گراف و كاربردهاي آن، مؤلفين: جي.اي.باندي و يو.اس.ار.مورتي
ترجمة : حميد ضرابي زاده
موسسه فرهنگي هنري ديباگران تهران

نظري براي اين محصول ثبت نشده است.


نوشتن نظر خودتان

براي نوشتن نظر وارد شويد.

محصولات
نظر سنجي
نظرتون در مورد ویکی پروژه چیه؟
  •   مراحل ثبت نام خیلی زیاده!
  •   مطلب درخواستیم رو نداشت!
  •   ایمیل نداشتم که ثبت نام کنم!
  •   مطلبی که میخواستم گرون بود!
نظرنتيجه