تاریخچه گراف

اندک زمانی است که واژه گراف در ادبیات ریاضی وارد شده است، گرچه شروع آن را می توان از زمان لئناردو اویلر ریاضیدان سوئیسی (1707-1783) دانست. اما علاقه ی شدید و مداوم به این دانش، بعنوان شاخه ای از ریاضیات ، از سال 1930 به بعد، آشکار گردید و امروزه این نظریه یکی از پربارترین و محبوب ترین شاخه‌های ریاضیات و علوم کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در بسیاری از مسائل گسترده ی جامعه مدرن امروزی است.هنگامی که مساله ای به زبان گراف فرمول بندی شد، درک آن بسیار آسان تر خواهد شد. امروزه نظریه ی گراف یکی از موضوعات مهم در ریاضیات گسسته است. گرافها، مدل های ریاضی برای یک مجموعه گسسته هستند، که اعضای آن به طریقی با هم مرتبط می باشند. اعضای این مجموعه می توانند انسان ها یا رابطه ی خویشاوندی ، یا دوستی و… باشد. اعضای این مجوعه می توانند، محل اتصال های سیم های یک شبکه ی برق و رابطه ی آنها، سیم های واصل بین دو نقطه باشد و یا عناصر مجوعه می توانند اتم‌های یک مولکول و ارتباط آن ها، اتصال های شیمیایی باشد. نظریه گراف ریشه در بازی ها و معما ها نیز دارد، اما امروزه این نظریه نه تنها در ریاضیات بلکه در سایر علوم مانند برنامه نویسی، اقتصاد، روانشناسی، ژنتیک و باستان شناسی و … کاربرد فراوانی دارد.

شاید بتوان نقطه آغاز پیدایش نظریه گراف را در قرن هجدهم میلادی (1736) توسط ریاضیدان بزرگ، لئناردو اویلر ریاضیدان سوئیسی دانست اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سده اخیر و با رشد علم انفورماتیک بوده‌است.

مفهوم گراف را اولین بار برای حل مسئله پل‌های کونیگسبرگ ابداع کرد.

مسئله پل‌های کونیگسبرگ یکی از مشهورترین مسائل در نظریه گراف است که در مکان و شرایط واقعی طرح شده‌است.

در اوایل سده ۱۸ ساکنین کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد در روسیه) در روزهای یکشنبه پیاده‌روی‌هایی طولانی در شهر داشتند.

این هفت پل، برای ارتباط بین خشکی‌های دو طرف رودخانه‌ای به‌نام پرگِل احداث شده بود. ساکنین سعی می‌کردند مسیری بیابند که از نقطه‌ای در شهر شروع کنند و از تمامی پل‌ها فقط یکبار بگذرند و به نقطه شروع بازگردند.

در سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که این امکان پذیر نیست و چنین مسیری وجود ندارد. در واقع، اویلر ثابت کرد برای آنکه مسیر از یک رأس شروع شود و از همه یال‌ها یک بار عبور کند و به همان رأس بازگردد، باید گراف همبند بوده و مرتبه هر یک از رأس‌های آن نیز زوج باشد.

او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای با عنوان Solutio problematis ad geometriam situs pertinentis (راه حل مسئله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.

اویلر ابتدا نقشه شهر را با نقشه‌ای که فقط خشکی‌ها، رود و پل‌ها را نشان می‌داد، جایگزین کرد.

سپس هر خشکی را با یک نقطه نشان داد که رأس نامیده می‌شود و هر پل را نیز با یک خط نشان داد که یال نامیده می‌شود.

این ساختار ریاضی را گراف می‌نامند.

اولین بار لغت گراف توسط سیلوستر در سال 1878 به کار برده شد.

( در مقاله ای در مجله نیچر نیچر)

200 سال پس از اثبات اویلر اولین کتاب نظریه گراف به زبان آلمانی تحت عنوان Theorie der Edichen und vndichen Graphen (konig 1936) توسط کنینگ نوشته شد.

اولین کتاب نظریه گراف به زبان انگلیسی و قابل مطالعه توسط فونک هروی در سال 1969 نوشته شد.

نظریه گراف اکنون یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و … است.

کاربردهای نظریه گراف

نظریه گراف کاربردهای زیادی در علوم مختلف و رشته‌های مهندسی دارد که برخی از آن‌ها به‌شرح زیر است:

مهندسی برق: گراف در مهندسی برق برای نمایش اتصال مدارها به کار می‌رود. برخی از این اتصالات به عنوان ستاره، مثلث سری و موازی شناخته می‌شوند.

علوم کامپیوتر: یکی از کاربردهای گراف در علوم کامپیوتر، مطالعه الگوریتم‌ها است. همچنین، برای بیان رابطه بین کامپیوترها در شبکه، از گراف‌ها استفاده می‌شود.

علوم: ساختار مولکولی و شیمیایی ماده، ساختار DNA و… از مواردی هستند که برای نمایش آن‌ها از گراف‌ها استفاده می‌شود.

زبان‌شناسی: graphs برای نمایش نمودار درختی تجزیه و دستور زبان نیز به‌کار می‌روند.

عمومی:‌ نمایش مسیرهای بین شهرها نیز یکی از کاربردهای عمومی graph theory است.

گراف چیست؟

Graph ساختاری است متشکل از مجموعه‌ای از نقاط و مجموعه از قطعه خط یا منحنی‌هایی که زوج‌های معینی از این نقاط را به‌هم وصل می‌کند.

نقاطی که گراف از آنها تشکیل شده، راس (Vertex) می باشد. و مجموعه این نقاط را در یک گراف، مجموعه رئوس می‌نامیم.

قطعه خطوط یا منحنی‌هایی که راس ها را به‌هم وصل می‌نمایند را یال (Edge). و مجموعه ان ها را در یک گراف، مجموعه یالی می‌نامیم.

شرکت ویرا پرداز خیام مفتخر است که در حوزه ریاضیات و نظریه گراف در حال فعالیت است، به طوری که علاوه بر فعالیت تیم در این عرصه ، وب سایت جهانی گراف (graphtheoryassociation.com) را طراحی کرده است.

این وب سایت برای پشتیبانی و ارتقای سطح آموزش و پژوهش در نظریه گراف، ترکیبیات و نظریه گراف جبری طراحی شده است.

در سال های اخیر، graph theory خود را به عنوان یک ابزار ریاضی مهم در بسیاری از موضوعات دیگر تثبیت کرده است. ساختار اجتماعی و روابط بین فردی ممکن است به صورت شبکه های اجتماعی باشد. شبکه هایی که رئوس یعنی افراد و یال های بین جفت رئوس، یعنی روابط بین آن افراد.. در مطالعه انواع شبکه، نظریه گراف و علوم مشابه نقش مهمی ایفا می کنند.

یکی از اهداف، معرفی کوتاه و ظریف با استفاده از فیلم برای برخی از نتایج در graph theory و ترکیبیات و همچنین حدس های اخیر به دانشجویان و محققان جوان است. علاوه بر این، مایل هستند دانش آموزان دبیرستانی را با موضوعات جالب در graph theory و ترکیبیات آشنا کنند. ما سوالاتی را در سطوح مختلف برای دانشجویان علاقه مند پیشنهاد می کنیم. هدف ما تقویت جامعه دانشجویان و اساتید فعال در تئوری گراف، ترکیبیات و … است.