مقاله شبکه ها و تطابق در گراف


دنلود مقاله و پروژه و پایان نامه دانشجوئی

مقاله شبکه ها و تطابق در گراف  مربوطه  به صورت فایل ورد  word و قابل ویرایش می باشد و دارای ۴۸  صفحه است . بلافاصله بعد از پرداخت و خرید لینک دنلود مقاله شبکه ها و تطابق در گراف  نمایش داده می شود، علاوه بر آن لینک مقاله مربوطه به ایمیل شما نیز ارسال می گردد

فهرست مطالب

شبکه ها    ۴
۱-۱شارش ها    ۴
۱-۲برش ها    ۸
۱-۳ قضیه شارش ماکزیمم – برش مینیمم    ۱۳
روش نشانگذاری    ۱۷
۱-۴ قضیه های منجر    ۲۳
تطابق ها    ۲۹
۲-۱ تطابق ها    ۲۹
۲-۲ تطابق و پوشش ها در گراف های دو بخشی    ۳۱
۳-۳ تطابق کامل    ۳۶
۲-۴ مساله تخصیص شغل    ۴۱
منابع    ۴۸

منابع

۱)    ریاضیات گسسته و ترکیباتی ، مؤلف: رالف پ. گریمالدی

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

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

۲)    درآمدی بر نظریة گراف، مؤلف: ربین ج. ویلسون

ترجمة: دکتر جعفر بی آزار

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

۳)    نظریة گراف و کاربردهای آن، مؤلفین: جی.ای.باندی و یو.اس.ار.مورتی

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

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

 شبکه ها

۱-۱شارش ها

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

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

(الف) رأس یکتایی مانند  وجود دارد به طوری که ، یعنی درجة ورودی a، برابر ۰ است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند  به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با ۰ است.

(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان  یک ظرفیت، که با  نشان داده می‌شود، نسبت می‌دهد.

برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.

مثال ۱-۱ گراف شکل ۱-۱ یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون ، مقدار کالای حمل شده از a به z نمی‌تواند از ۱۲ بیشتر شود. با توجه به  بازهم این مقدار محدودتر می‌شود و نمی‌تواند از ۱۱ تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد  باید ظرفیتهای همة کمانهای بشکه را درنظر بگیریم.

تعریف ۱-۲ فرض کنیم  یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه

الف) به ازای هر کمان  و

ب) به ازای هر ، غیر از مبدأ a یا مقصد  z ،  (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.

شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همة رأسها به استثنای مبدأ و مقصد بر قرار  است.

مثال ۱-۲ در شبکه های شکل ۱-۲، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در  صدق می کند. در شکل ۱-۲ (الف)، شارش، وارد رأس  می شود،۵ است، ولی شارشی که از آن رأس خارج می شود ۴=۲+۲ است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل ۱-۲ (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.

توجه داشته باشید که هر شبکه، حداقل دارای یک شارش است، زیرا تابع fای که در آن به ازای هر  داشته باشیم:  در هر دو شرط تعریف
۱-۲ صدق می کند. این تابع، شارش صفر نامیده می شود.

تعریف ۱-۳ فرض کنیم f شارشی برای شبکة حمل و نقل N=(V,E) باشد.

الف) کمانی مانند e متعلق به این شبکه را اشباع شده می نامند هر گروه f(e)=c(e) اگر f(e)<c(e) این کمان را اشباع نشده می نامند.

ب) اگر a مبدأ N باشد،  را مقدار شارش می نامند.

مثال ۱-۳ در شبکه شکل ۱-۲ (ب) فقط کمان  اشباع شده است. هر یک از کمان‌های دیگر اشباع نشده است. مقدار شارش این شبکه

است. ولی آیا شارش دیگری مانند  وجود دارد که به ؟

می‌گوئیم شارش fدر N، یک شارش ماکزیمم  است، هر گاه هیچ شارش دیگری مانند  در N با شرط  وجود نداشته باشد.

هدف ما در ادامه، تعیین یک شارش ماکزیمم است. برای انجام این کار، ملاحظه می‌کنیم که در شکل ۱-۲ (ب) داریم.

درنتیجه، شارش کل خارج شده از مبدأ a شارش کل وارد شده به مقصد z برابر  است.

50,000 ریال – خرید

تمام مقالات و پایان نامه و پروژه ها به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد.

 جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ  را پرداخت نمایید. 

مطالب پیشنهادی:
  • مقاله مجموعه‌های مرکزی و شعاع‌ها در گراف‌های مقسوم علیه صفر از حلقه‌های جابجائی
  • مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن
  • برچسب ها : , , , , , ,
    برای ثبت نظر خود کلیک کنید ...

    براي قرار دادن بنر خود در اين مکان کليک کنيد
    به راهنمایی نیاز دارید؟ کلیک کنید
    

    جستجو پیشرفته مقالات و پروژه

    سبد خرید

    • سبد خریدتان خالی است.

    دسته ها

    آخرین بروز رسانی

      یکشنبه, ۱ اسفند , ۱۳۹۵
    
    اولین پایگاه اینترنتی اشتراک و فروش فایلهای دیجیتال ایران
    wpdesign Group طراحی و پشتیبانی سایت توسط دیجیتال ایران digitaliran.ir صورت گرفته است
    تمامی حقوق برایdjkalaa.irمحفوظ می باشد.