پایان نامه شبکه ها و تطابق در گراف

مشخص نشده 1 MB 26644 50
مشخص نشده مشخص نشده ریاضی
قیمت: ۶,۵۰۰ تومان
دانلود فایل
  • بخشی از محتوا
  • وضعیت فهرست و منابع
  • پایان نامه رشته ریاضی کاربردی

    سال 1383 

    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)

    ب) اگر 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)            

    نتيجه 1-1 فرض كنيد f يك شارش و C يك برش باشد، به طوري كه  در اين صورت f يك شارش ماكزيمم و C يك برش مينيمم است.

    اثبات فرض كنيد  يك شارش ماكزيمم و  يك برش مينيمم باشد. در اين صورت بنا بر رابطه 1-4 داريم:

    و چون طبق فرض، ، نتيجه مي‌گيريم كه  و  درنتيبجه f يك شارش ماكزيمم و C يك برش مينيمم است .*

    در بخش آينده، عكس نتيجه 1-1 را اثبات خواهيم كرد، يعني اين كه در رابطه 1-4 همواره تساوي برقرار است.

    ولي، قبل از پرداختن به اين مطلب، با توجه به برهان قضيه 1-1 ملاحظه ميكنيم كه مقدار هر شارش با

    كه در آن  برشي دلخواه در N است، بيان مي شود. بنابراين، به محض آنكه شارشي در شبكه اي ساخته شد، به ازاي هر برش  در اين شبكه، مقدار شارش برابر است با مجموع شارشهاي موجود در كمان هاي سودار از رأسهاي P به رأسهاي  منهاي مجموع شارشهاي موجود در كمان هاي سودار از رأسهاي  به رأسهاي P.

    اين نكته ما را به نتيجه زير هدايت مي كند.

    نتيجه 1-2 اگر f شارشي در شبكه حمل و نقل N=(V,E) باشد، انگاه مقدار شارش خارج شده از مبدأ a برابر است با مقدار شارش وارد شده در مقصد z.

    اثبات قرار مي دهيم . با توجه به نكته قبلي داريم:

    چون  و ، مي‌بينيم كه  

    به همين ترتيب، به‌ازاي  و  داريم

    درنتيجه،

    و اين اثبات تمام است.*

    منابع

    1)

    ترجمه: دكتر محمد علي رضواني و دكتر بيژن شمس

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

    2)

    ترجمه: دكتر جعفر بي آزار

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

    3)

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

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

     

     

  • مقدمه
    فصل 1
    شبکه ها
    1-1 شارش ها
    1-2 برش ها
    1-3 قضیه شارش ماکزیمم – برش مینیمم
    1-4 قضیه منجر

    فصل 2
    تطابق ها
    2-1 انطباق ها
    2-2 تطابق ها و پوشش ها در گراف های دو بخش
    2-3 تطابق کامل
    2-4 مسأله تخصبص شغل
    منابع


تحقیق در مورد پایان نامه شبکه ها و تطابق در گراف, مقاله در مورد پایان نامه شبکه ها و تطابق در گراف, پروژه دانشجویی در مورد پایان نامه شبکه ها و تطابق در گراف, پروپوزال در مورد پایان نامه شبکه ها و تطابق در گراف, تز دکترا در مورد پایان نامه شبکه ها و تطابق در گراف, تحقیقات دانشجویی درباره پایان نامه شبکه ها و تطابق در گراف, مقالات دانشجویی درباره پایان نامه شبکه ها و تطابق در گراف, پروژه درباره پایان نامه شبکه ها و تطابق در گراف, گزارش سمینار در مورد پایان نامه شبکه ها و تطابق در گراف, پروژه دانشجویی در مورد پایان نامه شبکه ها و تطابق در گراف, تحقیق دانش آموزی در مورد پایان نامه شبکه ها و تطابق در گراف, مقاله دانش آموزی در مورد پایان نامه شبکه ها و تطابق در گراف, رساله دکترا در مورد پایان نامه شبکه ها و تطابق در گراف

پایان نامه جهت دریافت درجه کارشناسی ارشد (M.A) گرایش : ارتباط تصویری چکیده پایان نامه (شامل خلاصه، اهداف، روش های اجرا و نتایج به دست آمده): اهداف این تحقیق بررسی قابلیت های تایپوگرافی فارسی در ارتباط با عنوان بندی فیلم های سینمایی می باشد، زیرا از طریق تایپوگرافی نیز می توان فضایی متناسب با فضای فیلم را در عنوان بندی آن ایجاد نمود تا باعث حس انگیزی در بیننده شود و از آنجا که ...

پایان‌نامه کارشناسی ارشد در رشته‌ی کامپیوتر - مهندسی نرم افزار چکیده بررسی اطلاعات بیمه های اتومبیل نشان داده عواملی چون نوع استفاده خودرو، داشتن گواهینامه رانندگی، نوع گواهینامه و تطابق یا عدم تطابق آن با وسیله نقلیه، مبلغ حق بیمه، میزان تعهدات بیمه نامه، کیفیت خودروی خودرو سازان، سن راننده، سواد راننده، عدم تطابق حق بیمه با مورد بیمه، تاخیردرتمدید بیمه نامه، در سود و زیان شرکت ...

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

موضوع علم اقتصاد   اقتصاد علم تخصيص بهينه منابع کمياب است. در جهان کنوني با توجه به رشد روز افزون جمعيت، افزايش نيازهاي بشري و محدوديت شديد منابع لازم است تا در جهت استفاده بهينه از منابع

پايان نامه براي دريافت درجه کارشناسي ارشد رشته روانشناسي تربيتي بهار 93 چکيده نقشه مفهومي يکي از راهبردهاي ياددهي- يادگيري است که مي تواند يادگيري معنادار را در دانش آموزان تسهيل کند و روابط

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

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

پایان نامه کارشناسی ارشد(M.sc) چکیده: امروزه هرزنامه[1] ها یکی از مشکلات اصلی موتور های جستجو هستند، به این دلیل که کیفیت نتایج جستجو را نامطلوب می سازند. در طول سالهای اخیر پیشرفتهای بسیاری در تشخیص صفحات جعلی وجود داشته است اما در پاسخ تکنیک های هرزنامه جدید نیز پدیدار شده اند. لازم است برای پیشی گرفتن به این حملات، تکنیک های ضد هرزنامه بهبود یابد. یک مساله عادی که ما با آن در ...

پایان نامه دوره کارشناسی ارشد مهندسی کامپیوتر نرم افزار (M.Sc) چکیده ماهیت پویای شبکه جهانی و ابعاد رو به رشد آن، بازیابی دقیق اطلاعات را دشوار ساخته است. پاسخ های نادرست برگشت داده شده به وسیله ی موتورهای جستجو، خصوصا برای عبارات پرس‌و‌جو با معانی مختلف، باعث نارضایتی کاربران وب شده‌است که نیاز به پاسخ های دقیق برای تقاضاهای اطلاعاتی خود دارند. امروزه موتورهای جستجو تلاش ...

پایان‌نامه برای دریافت درجه کارشناسی ارشد مهندسی عمران«M. Sc» گرایش: آب چکیده هدف از انجام این پایان‌نامه، بررسی روند تغییرات بارش سالانه 37 ایستگاه منتخب در کل ایران با استفاده از روش ناپارامتری می‌باشد. دو آزمون من کندال و تخمین گر سن که جزء متداول‌ترین روش‌های ناپارامتری به شمار می‌روند، جهت تحلیل رونده داده‌های بارندگی و دما در مقیاس‌های سالانه به کار گرفته شدند. 37 ایستگاه ...

ثبت سفارش