دانلود تحقیق رشته رياضي كاربردي با موضوع شبكه ها و تطابق در گراف

نوع فایل : Word 

تعداد صفحات : 49

رشته رياضي كاربردي
شبكه ها و تطابق در گراف

فهرست مطالب

• مقدمه 
  
• فصل 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) را رسم كرده و سپس ظرفيت هر كمان را به عنوان برچسب آن كمان قرار مي‌دهيم...