نظریه گراف: تفاوت میان نسخه‌ها

در سال ۱۸۴۷، [[گوستاو کیرشهف]] نوع خاصی از گراف‌ها به نام [[درخت (نظریه گراف)|درخت]] را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم [[قوانین اهم]] برای [[جریان الکتریکی]] در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، [[آرتور کیلی]] همین نوع گراف را برای شمارش [[ایزومر|ایزومرهای]] متمایز [[هیدروکربن|هیدروکربن‌های]] اشباع‌شدهٔ C_nH_2n+2 <math>\left (n\in\mathbb{Z}^+\right)</math> به‌کار برد.<ref>{{پک|گریمالدی|۱۳۷۹|ف=درخت‌ها|ک=ریاضیات گسسته و ترکیبیاتی|ص=۸۲۴}}</ref>

 

 

ایدهٔ مهم دوم، [[دور همیلتونی]] بود. این دور به افتخار [[ویلیام همیلتون|سر ویلیام روآن همیلتون]] نامگذاری شده‌است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یال‌های یک دوازده وجهی منتظم ([[گراف همیلتونی]]) به‌کار گرفت. یافتن جوابی برای این معما چندان دشوار نیست، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که [[گراف‌های بیسوی]] حاوی [[مسیر همیلتونی|مسیر]] یا [[دور همیلتونی|دورهای همیلتونی]] را مشخص کنند.