پاورپوینت نظریه گراف و کاربردهای آن تالیف مورتی و باندی

پاورپوینت نظریه گراف و کاربردهای آن تالیف مورتی و باندی (pptx) 393 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 393 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بسم الله الرحمن الرحیم نظریه گراف و کاربردهای آن Graph Theory فصل ( 1 ) مقدمه گرافهايي كه در اين كتاب مي خواهيم مطالعه كنيم ، شكلهاي هندسي ساده اي هستند متشكل از نقطه ها و خطهايي كه برخي از اين نقطه ها را به يكديگر وصل ميكنند . اين گرافها گاهي « گرافهاي خطي» ناميده ميشوند . نخستين مقاله درنظريه گرافها را اويلر رياضيدان پر آوازه سويسي نوشت كه در سال 1736 منتشر شد . از ديدگاه رياضي ، نظريه گرافها درآغاز مهم به نظرنمي رسيد ، زيرا بيشتر با معماهاي سرگرم كننده سروكار داشت .اما پيشرفتهاي اخير در رياضيات ، به ويژه در كاربردهاي آن ، تكاني قوي به نظريه ي گرافها داده است .از سده نوزدهم گرافها در زمينه هايي مانند مدارهاي الكتريكي و نمودارهاي مولكولي به كار رفته اند . در حال حاضر مباحثي در رياضيات محض ، مثلآ نظريه رايطه هاي رياضي ، وجود دارند كه نظريه گرافها ابزار مناسبي براي آنها به شمار مي آيد ، البته گرافها موارد استعمال متعدد ديگري نيز در مساله هاي خيلي عملي دارند : مساله هاي جورسازي ، مساله هاي حمل ونقل ، جريان در شبكه هاي خط لوله ، و به اصطلاح « برنامه ريزي » به معني اعم . همچنين ، امروزه از نظريه گرافها در رشته هاي متفاوتي مانند اقتصاد ، روانشناسي و زيست شناسي استفاده ميشود . معماها هنوز بخش كوچكي از نظريه گرافها را تشكيل ميدهند ، به ويژه ، اگر مساله چهار رنگ معروف را نيز ، كه مانند سابق مايه شگفتي رياضيدانهاي معاصر است ، به جرگه آنها اضافه كنيم . نظريه ي گرافها در رياضيات شاخه اي از توپولوژي به حساب مي آيد : البته با جبر و نظريه ي ماتريسها نيز پيوندي محكم دارد . گراف چيست؟ رقابتهاي تيمي فرض كنيم تيم فوتبال مدرسه شما عضو اتحاديه اي باشد كه تيمهاي ان با يكديگر مسابقه ميدهند . تيم خود را a و ديگر تيمها را b ، c ، d ، e و f بناميد ، و فرض كنيد كه مجموعآ 6 تيم در مسابقه شركت ميكنند . همچنين فرض كنيد بعد از گذشت چند هفته از اين دوره ، بازيهاي زير انجام شده است ، مثلآ ، a با c ، d و f بازي كرده است . b با c ، e و f بازي كرده است . C با a و b بازي كرده است . d با a ، e و f بازي كرده است. e با b ، d و f بازي كرده است . f با a ، b ، d و e بازي كرده است . اين وضعيت را مي توان با يك نمودار هندسي نمايش داد . هر تيم را با يك نقطه يا دايره كوچكي نمايش مي دهيم ، و هر دو نقطه را اگر تيمهاي متناظرشان با هم بازي كرده باشند ، با خطي راست به يكديگر وصل ميكنيم . در اين صورت ، شكل 1.1 كه بازيهاي انجام شده رانشان ميدهد ، به دست مي آيد . شكل1-1 هر شكل مشابه با شكل 1.1 گراف ناميده ميشود گراف تشكيل ميشود از نقطه هايي مانند a ، b ، c ، d ، e ، f موسوم به راسهاي گراف وپاره خطهايي كه راسها را به هم وصل مي كنند ، موسوم به يالهاي گراف ، مانند ac ، eb و غيره . اين گراف را G مي ناميم . به طوري كه در شكل 1.1 ديده ميشود ، ممكن است يالهاي گراف يكديگر را در نقطه هايي بجز راسها قطع كنند : اين اشكال ناشي از اين است كه ما گرافمان را در صفحه رسم كرده ايم بنابراين ، شايد مناسب تر باشد يالها را همچون نخهايي در فضا كه از روي هم عبور ميكنند نمايش دهيم . اما در هر صورت ، براي پرهيز از ابهام بايد تعيين موضوع راسها با دقت انجام شود . هر مجمومه از مسابقه هاي انجام شده دريك دوره مسابقه را ميتوان به روش مذكور ، به صورت يك گراف نمايش داد . بر عكس ، اگر گرافي ، يعني شكلي متشكل از نقطه ها يا راسهايي كه با پاره خطها يا يالها به هم وصل شده باشند ، داشته باشيم ، مي توانيم آن را نمودار چنين مسابقه هايي به حساب آوريم .به عنوان مثال گراف رسم شده در شكل 2.1را در نظر مي گيريم . اين شكل را مي توان نمودار مسابقه هايي ميان 8 تيم در نظر گرفت : تيم a با تيمهاي b ، e و d بازي كرده است ، و الي اخر.