آموزش رایگان نظریه گراف

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

نظریه گراف دوران تکامل پنهان خود را طی کرد تا این که کاربردهای آن نظر ریاضی‌دانان حرفه‌ای قرن بیستم را به خود جلب کرد. سرانجام در سال ‎۱۹۳۶‎ اولین کتاب در نظریه گراف توسط کونینگ، به زبان آلمانی نوشته شد. از آن روز این نظریه گسترش و عمومیت فراوانی یافت و مسائل جذاب و گوناگون آن، روز به روز اذهان بیشتری را به سمت خود جذب کرد‎.

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

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

از این رو،‌ ما در مکتب‌خونه تصمیم گرفتیم که دوره آموزش رایگان نظریه گراف را برای علاقه‌مندان این حوزه تدارک ببینیم. این درس در نیمسال اول سال تحصیلی 00-99 در دانشکده علوم ریاضی، دانشگاه صنعتی اصفهان برای دانشجویان کارشناسی ارائه شده است. هدف از ارائه این درس آشنایی با مفاهیم پایه در نظریه گراف است.

 

دوره آموزش رایگان نظریه گراف مناسب چه کسانی است؟

• تمام کسانی که با ریاضیات آشنایی دارند.
• دانشجویانی که باید درس نظریه گراف را بگذرانند.
• دانشجویان رشته‌های مهندسی که برای گذراندن دروس تخصصی خود به یادگیری گراف نیاز دارند.

پیشنیازهای لازم برای فراگیری دوره آموزش رایگان نظریه گراف چیست؟

تمام کسانی که با مبانی علوم ریاضی آشنا هستند و به نظریه گراف علاقه‌مندند می‌توانند بدون هیچ پیش‌زمینه خاصی در این دوره شرکت کنند. بنابراین برای شرکت در این دوره پیش‌نیازی جز آشنایی با مبانی ریاضیات تعریف نشده است.

سرفصل‌های دوره آموزش رایگان نظریه گراف چیست؟

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

 

فصل اول: مفاهیم پایه نظریه گراف

هر آموزشی در ابتدا با تعریف مفاهیم پایه آغاز می‌شود. در فصل اول از دوره آموزش نظریه گراف هم با مفاهیم و تعاریف اولیه گراف و زیرگراف، نمایش‌های ماتریسی و یک‌ریختی، دنباله درجات، مسیرها و هم‌بندی‌ها آشنا می‌شوید. همچنین در این فصل می‌آموزید که چه اعمالی را می‌توانید روی گراف‌ها انجام دهید.

 

فصل دوم: گراف‌های جهت‌دار

گراف‌های جهت‌دار دارای یال‌هایی هستند که تنها یک جهت دارند. در فصل دوم با تعاریف اولیه، تورنمنت‌ها، شبکه‌ها و جریان‌ها آشنا می‌شوید. 

 

فصل سوم: درخت‌ها

از معروف‌ترین انواع گراف‌ها می‌توان به درخت اشاره کرد. درخت‌ها خواص و کاربردهای جالبی دارند. بیشترین کاربرد این گراف‌ها را می‌توان در علوم رایانه و ساختار داده‌ها مشاهده کرد. در این فصل با درخت‌ها، خواص آن‌ها و درخت‌های فراگیر آشنا می‌شوید. همچنین الگوریتم یافتن درخت‌های فراگیر و یافتن کوتاه‌ترین مسیر را می‌توانید به خوبی آموزش ببینید.

 

فصل چهارم: هم‌بندی گراف‌ها

یکی از مفاهیم اولیه در نظریه گراف همبندی است. همبندی رأسی و یالی از جمله موارد پرکاربردی است که در ریاضیات و علوم کامپیوتر استفاده می‌شود. در این فصل از دوره آموزش نظریه گراف با هم‌بندی، گراف‌های دو یال هم‌بند و k هم‌بند آشنا می‌شوید. قضیه منگر یکی از قضایای گراف است که در این مبحث مطرح می‌شود. در این فصل این قضیه و کاربردهای آن را به خوبی فرا می‌گیرید.

 

فصل پنجم: مجموعه‌های مستقل رأسی و یالی در گراف‌ها

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

 

فصل ششم: گراف‌های اویلری و هامیلتونی

همان طور که در تاریخچه گراف اشاره شد، این علم با مسئله مشهور پل‌های کونیگسبرگ به وجود آمد. این مسئله باعث پدید آمدن گراف‌های اویلری و هامیلتونی شد. در این فصل با انجام مثال‌هایی با این نوع از گراف‌ها آشنا می‌شوید.

 

فصل هفتم: رنگ‌آمیزی گراف‌ها

رنگ‌آمیزی گراف از پرکاربردترین حالت‌ها در مسائل دنیای واقعی است. در این حالت باید بتوانید رأس‌های گراف را طوری رنگ‌آمیزی کنید که هیچ دو رأسی رنگ یکسان نداشته باشند. در این فصل با رنگ‌آمیزی رأسی، رنگ‌آمیزی یالی، چندجمله‌ای رنگی و گراف‌های بحرانی آشنا می‌شوید. قضیه بروکس یکی از قضایایی است که در این زمینه وجود دارد و در این فصل به آن می‌پردازیم.

 

فصل هشتم: گراف‌های مسطح

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