نظریه گراف

نظریه گراف[ ۱] شاخه ای از ریاضیات است که دربارهٔ گراف ها بحث می کند. این مبحث در واقع شاخه ای از توپولوژی است که با جبر و نظریه ماتریس ها پیوند مستحکم و تنگاتنگی دارد. نظریهٔ گراف برخلاف شاخه های دیگر ریاضیات نقطهٔ آغاز مشخصی دارد و آن انتشار مقاله ای از لئونارد اویلر، ریاضیدان سوئیسی، برای حل مسئله پل های کونیگسبرگ در سال ۱۷۳۶ است. [ ۲]
پیشرفت های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده است به گونه ای که هم اکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینه های گوناگون مانند نظریه کدگذاری، تحقیق در عملیات، آمار، شبکه های الکتریکی، علوم رایانه، شیمی، زیست شناسی، علوم اجتماعی و سایر زمینه ها گردیده است. [ ۳] [ ۴]
برخلاف شاخه های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن مسئلهٔ هفت پل کونیگسبرگ است که در سال ۱۷۳۶ توسط لئونارد اویلر حل شد. [ ۵] در سال ۱۷۵۲ قضیهٔ اویلر برای گراف های مسطح ارائه می شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت. [ ۶]
در سال ۱۸۴۷، گوستاو کیرشهف نوع خاصی از گراف ها به نام درخت را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی در کاربردهایی که حاوی شبکه های الکتریکی بودند به کار گرفت. ده سال بعد، آرتور کیلی همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربن های اشباع شدهٔ CnH2n+2 ( n ∈ Z + ) به کار برد. [ ۷]
در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس چهار رنگ بود که نخستین بار توسط فرانسیس گوثری در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط کنث ایپل و ولفگانگ هیکن و با استفاده از یک تحلیل رایانه ای پیچیده حل شد. [ ۸]
ایدهٔ مهم دوم، دور همیلتونی بود. این دور به افتخار سر ویلیام روآن همیلتون نامگذاری شده است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یال های یک دوازده وجهی منتظم ( گراف همیلتونی ) به کار گرفت. یافتن جوابی برای این معما چندان دشوار نیست، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که گراف های بیسوی حاوی مسیر یا دورهای همیلتونی را مشخص کنند.
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئلهٔ مشخص کردن گراف های مسطح را کازیمیر کوراتوفسکی، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب دربارهٔ نظریهٔ گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان مجار، دنش کونیگ، که خود محقق برجسته ای در این زمینه بود، نوشت. از آن پس فعالیت های بسیاری در این زمینه صورت گرفته و رایانه نیز در چهار دههٔ اخیر به یاری این فعالیت ها آمده است. [ ۹]