صفحه 32 — ریاضیات گسسته | منظومه ایرانیان

درس 1 معرفی گرافدر اوایل قرن هجدهم، معمایی فکر برخی از اهالی شهر کونیگسبرگ (در حال حاضر در روسیه)را به خود مشغول کرده بود.ٔ رودخانه این شهر که از میان شهر عبور می‌کرد مانند آنچه در شکل زیر می‌بینید، شهر را به چندقسمت تقسیم می‌کرد. برخی از مردم این شهر کنجکاو بودند که بدانند آیا می‌توان با حرکت از یکنقطه از شهر و دقیقاً یکبار عبور از هر کدام از پل ها، به ٔ نقطه شروع حرکت بازگشت؟شکل ١لئونارد اویلر 1 1783(ــ ،)1707 ریاضی دان ٔ برجسته سوئیسی، برای حل این مسئله از شکلزیر، که امروزه به آن «گراف» می‌گوییم، کمک گرفت و با استفاده از استدالل ثابت کرد که این کارامکان پذیر نیست.اگر چهار ٔ ناحیه x و y و z و w را با 4 نقطه نمایش دهیمو به ازای هر پل که بین دو ناحیه قرار دارد نقاط متناظربا آن ناحیه ها ِ را به هم وصل نماییم شکل مقابل به دستمی‌آید که گراف حاصل از مدل سازی ٔ مسئله مذکور است.مدل سازی بسیاری از مسائل با گراف، دسته بندی منظم و شکل 2تفکر منطقی ٔ درباره آنها را آسان تر می‌نماید.اگرچه بیشتر مورخان تاریخ ریاضی شروع بحث گراف را از این ٔ مسئله اویلر می‌دانند، اما نمیتوانLeonhard Euler 1ــفصل دوم: گراف و مدل سازی 32