معرفی گراف

گراف نوعی ابزار مدل سازی در ریاضیات است که در این پست به معرفی ان می پردازیم

گراف چیست؟ گراف یک روش مدل سازی است. که از خط های که به آن یال می گویند و نقطه های که به ان راس می گوییند و روابط بین انها تشکیل شده است

تاریخچه گراف از کوینگسبرگ رودخانه ای می گذرد که شهر به چهار قسمت تقسیم می کند و این چهار قسمت با هفت پل به هم وصل شده بودند مردم شهر کوینگسبرگ اخر هفته ها در شهر دور می زدند و برایشان سوال شده بود که آیا می توان از یک قسمت شروع کرد از همه پل ها بدون گذشت و به نقطه اول برگشت ؟ انها می خواستند از هر پل دقیقا یکبار بگزرند

اویلر برای حل این سوال به شکل گراف مسئله را مدل سازی کرد و سپس ثابت کرد غیر ممکن است  لئونارد اویلر در سال ۱۷۳۶ پل‌های کونیگسبرگ حل کرد نظریهٔ گراف‌ها را بنیان گذاشت. البته جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ این مدل‌های ریاضی را گراف نامید.

اگر از یک خشکی فقط بگذری و نه شروع کنی و نه تموم کنی (یعنی وسط راه باشه) هر بار که می‌ای وارد بشی، باید بعداً ازش خارج بشی. یعنی تعداد پل‌هایی که به اون خشکی می‌رسه باید زوج باشه. چون هر بار ۲ تا پل مصرف می‌کنی (یکی ورود، یکی خروج). اگر اون خشکی نقطهٔ شروع باشه اولین بار فقط ازش خارج می‌شی بدون اینکه قبلاً وارد شده باشی، پس تعداد پل‌هاش می‌تونه فرد باشه (مثلاً ۳ تا پل: یکی برای خروج اول، بعد یکی ورود، یکی خروج). اگر اون خشکی نقطهٔ پایان باشه  آخرین بار فقط وارد می‌شی و دیگه خارج نمی‌شی، پس تعداد پل‌هاش هم می‌تونه فرد باشه. پس در کل، در یک مسیر که از همه پل‌ها یک‌بار می‌گذره، حداکثر دو تا خشکی می‌تونن تعداد پل‌هاشون فرد باشه (همون شروع و پایان). بقیه باید تعداد پل‌هاشون زوج باشه.  حالا گراف کونیگسبرگ : چهار تا خشکی داشت. تعداد پل‌هایی که به هر کدوم وصل می‌شد: ۳ تا پل ۳ تا پل ۳ تا پل ۵ تا پل همه‌شون تعداد فرد دارن یعنی چهار تا خشکی با درجهٔ فرد. طبق قانون بالا، فقط می‌تونیم ۲ تا فرد داشته باشیم، نه ۴ تا. پس غیرممکن  که همچین مسیری وجود داشته باشه

کاربردهای گراف در دنیای امروز امروز گراف‌ها همه‌جا هستند: • شبکه‌های اجتماعی: فیس‌بوک، اینستاگرام – شما یک رأس هستید، دوستی‌ها یال‌ها. • گوگل مپ: هر تقاطع یک رأس، هر خیابان یک یال. کوتاه‌ترین مسیر را با الگوریتم‌های گراف پیدا می‌کند. • اینترنت: صفحات وب رأس‌ها و لینک‌ها یال‌ها هستند. • شیمی: مولکول‌ها و پیوندهای اتمی.