نام فایل : گرافتوری

فرمت : .ppt

تعداد صفحه/اسلاید : 413

حجم : 2 مگابایت

بنام خدا
فصل (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 بازي كرده است ، و الي اخر.
شکل 1-2
1-2- گرافهاي تهي و گرافهاي كامل
....