نظریه گراف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ←تاریخچه: ویرایش جزئی |
|||
خط ۹:
برخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن [[مسئله پل‌های کونیگسبرگ|مسئلهٔ هفت پل کونیگسبرگ]] است که در سال ۱۷۳۶ توسط [[لئونارد اویلر]] حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برای [[گراف مسطح|گراف‌های مسطح]] ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.
در سال ۱۸۴۷، [[گوستاو کیرشهف]] نوع خاصی از گراف‌ها به نام [[درخت (نظریه گراف)|درخت]] را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم [[قوانین اهم]] برای [[جریان الکتریکی]] در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، [[آرتور کیلی]] همین نوع گراف را برای شمارش [[ایزومر|ایزومرهای]] متمایز [[هیدروکربن|
در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس [[مسئله چهار رنگ|چهار رنگ]] بود که نخستین بار توسط [[فرانسیس گوثری]] در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط [[کنث ایپل]] و [[ولفگانگ هیکن]] و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد.<ref>{{پک|گریمالدی|۱۳۷۹|ف=نظریه گراف و کاربردهای آن|ک=ریاضیات گسسته و ترکیبیاتی|ص=۷۵۵}}</ref>
| |||