مرجع دانلود پاورپوینت های درسی

حجم فایل : 2.0 MB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 413
بنام خدا فصل (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 ديده ميش...