مقاطع تحصیلی
جستجو در منظومه
مطمئن بود که متفکران و دانشمندان دیگری پیش از آن تاریخ برای حل مسائل از مدل سازی با گراف بهره نگرفته باشند. به طورمثال در حدود 100 سال پیش از آن شیخ بهایی، ریاضی دان ایرانی 1 1000(925 ــ خورشیدی) مسئله ای به این صورت طرح کرد:سه خانه و سه چاه آب، مانند شکل مقابل مفروض اند. آیا می‌توان ازهر چاه به هر خانه یک کانال آب حفر کرد به طوری که هیچ دو کانالییکدیگر را قطع نکنند؟ چاه هاحل این مسئله هم ارتباط نزدیکی به مباحث گراف دارد. اگر خانه هاو چاه ها را 6 نقطه مشخص کنیم و کانال ها را با خط ها یا منحنی هانمایش دهیم در این صورت دو ٔ مجموعه مجزای 3 عضوی از نقاط خانه هاداریم که باید نقاط ٔ مجموعه ّ او ل به تک تک نقاط ٔ مجموعه دوم وصلشوند. شکل حاصل از این کار یک گراف است و می‌توان نشان داد که شکل 3این کار نشدنی است و الاقل دو تا از خط ها یکدیگر را قطع می‌کنند.حال به مثالی از تحلیل یک وضعیت به کمک گراف می‌پردازیم.مثال: 5 تیم فوتبال a ، b ، c ، d و e در یک گروه قرار دارند و تیم ها دوبه دو با هم بازی می‌کنند و برخی از این بازی ها انجامشده است و اطالعات زیر را داریم:تیم a تیم های b و e را برده و به c باخته است.تیم b به a باخته و از d برده است.تیم c از تیم های a و e برده است.تیم d به تیم های b و e باخته است.تیم e به a و c باخته و از تیم d برده است.برای نمایش تمام اطالعات باال به صورت خالصه، از نموداری به شکل 4استفاده می‌کنیم که به ازای هر تیم یک نقطه می‌گذاریم و هر دو نقطه را به هموصل می‌کنیم اگر و تنها اگر تیم های مربوط به آنها با هم بازی کرده باشند؛ وجهت خط یا منحنی ای که دو نقطه را به هم وصل می‌کند باید از تیم برنده بهسمت تیم بازنده باشد.حال با یک نگاه به نمودار رسم شده، عالوه بر دریافت اطالعات باال بهسادگی به سؤال های زیر نیز می‌توان جواب داد.ــ مشخص کنید هر تیم با کدام تیم ها بازی نکرده است. شکل 4ــ اگر هر برد 3 امتیاز داشته باشد در بازی هایی که تا اینجا انجام شدهاست کدام تیم ها بیشترین امتیاز را کسب کرده اند؟ــ1 دکتر مهدی بهزاد، متولد ،1315 ریاضی دان مشهور ایرانی، یکی از ِ پیشگامان نظریه گراف در ایران است. بسیاری از پژوهش گران در این زمینه او را پدر علم گرافدر ایران می‌دانند.33 درس ا ّ و ل: معرفی گراف