السلامعلیک یا فاطمه؛ یا سیدةنساءالعالمین
سلام دوستان و همراهان عزیز، سالروز شهادت بزرگمرد راستین، و قهرمان بهحق ایرانی، سردار خوبیها و مهربانیها، حاج قاسم سلیمانی را تسلیت میگوییم.
حتماً یادتان هست که در این دوره در هر شماره درباره یکی از مفاهیم اساسی ریاضیات صحبت میکنیم و در این شماره میخواهیم درباره گراف بگوییم. به این منظور فرض کنید، میخواهیم از شهر شیراز به شهر مقدس مشهد سفر کنیم. فرض کنید که میدانیم از شهر شیراز تا شهر اصفهان، 4 راه و از شهر اصفهان تا شهر تهران، ۳ راه و از شهر تهران تا شهر مشهد، ۲ راه وجود دارد.
قبل از سفر سؤالهایی مطرح کنیم؛ سؤالهایی نظیر:
- به چند طریق میتوانیم از شهر شیراز به شهر مشهد سفر کنیم؟
- بهترین وکوتاهترین مسیر کدام است؟
- به چند روش میتوان از شهر شیراز به شهر مشهد رفت و دوباره به شهر شیراز برگشت، بهطوری که از هر مسیر حداکثر یک بار عبور کنیم و از تمام شهرها هم عبور کرده باشیم؟
- و سؤالهای دیگر.
برای پاسخ به این سؤالها قلم وکاغذی بردارید و یک شکل هندسی و مدلی از سفرتان را با استفاده از اطلاعاتی که دارید، ترسیم کنید. شهرها را با نقطه و فاصلهها را با خط مستقیم و یال نشان دهید. مدل ترسیمیتان را تجزیه و تحلیل کنید و پاسخ خود را بیابید. مدل هندسی که شما ترسیم کردهاید، «گراف» نام دارد. گرافها مدلهایی هستند به صورت نمودارهای هندسی که در صفحه رسم میشوند، به طوری که رأسها یا نقطهها در موقعیت کلی با خطهای مستقیم و یالها به هم متصل میشوند. گراف یکی از مفهومهای مهم در ریاضیات است که کاربردهای فراوانی در دنیای واقعی دارد.
تاریخچه نظریه گراف به سال 1735 برمیگردد؛ یعنی زمانی که ریاضیدان سوئیسی، لئونارد اویلر، مسئله «پل کونیگزبرگ» را حل کرد. مسئله کونیگزبرگ یکی از معروفترین مسئلهها در نظریه گراف است که در مکان و شرایط واقعی طراحی شده است. مسئله چنین است: در اوایل سده ۱۸، ساکنان شهر کونیگزبرگ در «پروسیا» (در حال حاضر کالینینگراد روسیه)، روزهای یکشنبه پیادهرویهایی طولانی در شهر داشتند. رود «پرگل» شهر را به چهار قسمت (خشکی) تقسیم کرده بود: خشکیهای C, B ,A و D که با هفت پل به هم مرتبط بودند. افراد سعی میکردند مسیری پیدا کنند که از نقطهای در شهر شروع شود و از تمامی پلها فقط یکبار عبور کنند و به نقطه شروع بازگردند.
اویلر ثابت کرد که چنین مسیری وجود ندارد. ﻃﺒﻖ ﺍﺳﺘﺪﻻﻝ ﺍﻭ، ﻧمیﺗﻮﺍﻥ ﻓﻘﻂ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﻳﻚ دورکاملزدن، ﺍﻳﻦ ﮔﺮﺍﻑ ﺭﺍ ﻛﺎﻣﻼً ﭘﻴﻤﻮﺩ. ﺑﻪ عبارت ﺩﻳﮕﺮ، ﺍﺯ ﻫﺮ ﺭأﺳﻲ ﻛﻪ ﺷﺮﻭﻉ ﻛﻨﻴﻢ، ﻧﻤﻲﺗﻮﺍﻧﻴﻢ ﺑﺪﻭﻥ ﻋﺒﻮﺭ ﻣﺠﺪﺩ ﺍﺯ ﻳﺎﻝ ﻳﺎ ﻳﺎلهاﻳﻲ، ﻛﻞ ﮔﺮﺍﻑ ﺭﺍ بپیماییم ﻭ ﺑﻪ نقطه ﺷﺮﻭﻉ ﺑﺎﺯ ﮔﺮﺩﻳﻢ. راهحل اویلر باعث شکلگیری شاخه جدیدی از ریاضیات به نام «توپولوژی» شد. مهمتر اینکه راهحل اویلر در تاریخ ریاضیات به عنوان اولین قضیه در نظریه گراف شناخته شد. امروزه گراف شاخهای پرکاربرد در ریاضیات به حساب میآید. اجزا و اصطلاحات اصلی و اساسی هر گراف شامل نقطه، خط، رأس، یال و ویژگیهای نمودارهاست. ما با نظریه گراف میتوانیم هر شیء و شکل هندسی را به طور دقیق مطالعه کنیم، رابطه بین یالها و رأسها را بیابیم و بسیاری از حقایق را روشن سازیم.
از نمونه کاربردهای گراف در زندگی میتوان به یافتن کوتاهترین مسیر در سفرهای شهری و بینشهری اشاره کرد. مثلاً در نقشههای مسیریاب، مکانهای متفاوتی به صورت رأس یا گره و جادهها به صورت خط و یال نشان داده شدهاند که با استفاده از نظریه گراف کوتاهترین مسیر بین دو گره و یا رأس مشخص میشود. از دیگر کاربردهای نظریه گراف و استفاده از شبکههای هندسی میتوان به این موردها اشاره کرد: برنامهریزی شهری، کنترل ترافیک، حملونقل و ناوبری، شبکههای تلفن همراه، برنامهریزی جدولهای زمانی، شبکههای ارتباطی و اینترنتی، جستوجوی صفحههای وب، سامانههای تلفن، سامانههای رایانهای، برنامهریزی اقتصادی، مالیاتی و شبکههای مالی، تجزیه و تحلیل و تهیه بودجه سالانه کشور، کنترل مسیرهای هوایی و دریایی، ترسیم مدلهای پیوندهای مولکولی، نمایش نمودارهای خطی در زیستشناسی، شیمی، پزشکی و داروسازی، طراحی شبکههای توزیع آب و شبکههای برق، تعیین مسیر خطهای لوله گاز، ارائه خدمات تلفن و تلفن همراه و هزاران کاربرد دیگر.
شاد و سلامت باشید.