پاورپوینت نظریه گراف و کاربردهای آن تالیف مورتی و باندی (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
بازي كرده است ، و الي اخر.