نظریه گراف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات:حذف الگو: Link GA |
|||
خط ۲:
[[پرونده:6n-graf.svg|thumb|left|270px|نمایش تصویری یک گراف]]
'''نظریه گراف'''<ref>'''گراف''' واژهٔ مصوب فرهنگستان زبان و ادب پارسی به جای '''graph''' در [[انگلیسی]] و در حوزهٔ [[ریاضیات]] است. {{یادکرد وب| نشانی = http://www.persianacademy.ir/fa/wordspdf.aspx| عنوان =فرهنگ واژه‌های مصوّب فرهنگستان: ۱۳۷۶ تا ۱۳۸۵، بخش دوم: به ترتیب الفبای لاتینی، صفحهٔ ۱۰۲
پیشرفت‌های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده است به گونه‌ای که هم‌اکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینه‌های گوناگون مانند [[نظریه کدگذاری]]، [[تحقیق در عملیات]]، [[آمار]]، [[شبکه‌های الکتریکی]]، [[علوم رایانه]]، [[شیمی]]، [[زیست‌شناسی]]، [[علوم اجتماعی]] و سایر زمینه‌ها گردیده است.<ref>{{پک|وست|۱۳۸۶|ف=|ک=آشنایی با نظریهٔ گراف|ص=۵}}</ref>
خط ۹:
برخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن [[مسئله پل‌های کونیگسبرگ|مسئلهٔ هفت پل کونیگسبرگ]] است که در سال ۱۷۳۶ توسط [[لئونارد اویلر]] حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برای [[گراف مسطح|گراف‌های مسطح]] ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.
در سال ۱۸۴۷، [[گوستاو کیرشهف]] نوع خاصی از گرافها به نام [[درخت (نظریه گراف)|درخت]] را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم [[قوانین اهم]] برای [[جریان الکتریکی]] در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، [[آرتور کیلی]] همین نوع گراف را برای شمارش [[ایزومر]]های متمایز [[هیدروکربن]]های اشباع شدهٔ C<sub>n</sub>H<sub>۲n+۲</sub> <math>\left (n\in\mathbb{Z}^+\right
در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس [[مسئله چهار رنگ|چهار رنگ]] بود که نخستین بار توسط [[فرانسیس گوثری]] در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط [[کنث ایپل]] و [[ولفگانگ هیکن]] و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد.<ref>{{پک|گریمالدی|۱۳۷۹|ف=نظریه گراف و کاربردهای آن|ک=ریاضیات گسسته و ترکیبیاتی|ص=۷۵۵}}</ref>
ایدهٔ مهم دوم، [[دور همیلتونی]] بود. این دور به افتخار [[ویلیام همیلتون|سر ویلیام روآن همیلتون]] نامگذاری شده است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یال‌های یک دوازده وجهی منتظم به‌کار گرفت. یافتن جوابی برای این معما چندان دشوار
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئلهٔ مشخص کردن [[گراف مسطح|گراف‌های مسطح]] را [[کازیمیر کوراتوفسکی]]، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب دربارهٔ نظریهٔ گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان [[مجار]]، [[دنش کونیگ]]، که خود محقق برجسته‌ای در این زمینه بود، نوشت. از آن پس فعالیت‌های بسیاری در این زمینه صورت گرفته و رایانه نیز در چهار دههٔ اخیر به یاری این فعالیت‌ها آمده است.<ref>{{پک|گریمالدی|۱۳۷۹|ف=نظریه گراف و کاربردهای آن|ک=ریاضیات گسسته و ترکیبیاتی|ص=۷۶۶}}</ref>
سطر ۳۶ ⟵ ۳۵:
{{انبار-رده|Graph theory}}
== جستارهای وابسته ==
* [[یکریختی گراف]]
خط ۴۲:
== پانویس ==
{{پانویس|اندازه=ریز}}
== منابع ==▼
▲== منابع ==
* کتاب آشنایی با نظریهٔ گراف نوشتهٔ [[علیرضا علیپور]]، [[انتشارات فاطمی]]
* {{یادکرد کتاب | همان = | نام خانوادگی =گریمالدی | نام =رالف پ. | عنوان =ریاضیات گسسته و ترکیبیاتی | ترجمه =دکتر محمدعلی رضوانی و دکتر بیژن شمس | جلد =۳ | سال= ۱۳۷۹ | ماه = | سال اصلی = | چاپ=دوم | ناشر =[[انتشارات فاطمی]] | مکان =تهران | شابک =۹۶۴-۳۱۸-۲۵۶-۸}}
* {{یادکرد کتاب | همان = | نام خانوادگی =وست | نام =داگلاس بی. | عنوان =آشنایی با نظریهٔ گراف | ترجمه =دکتر بیژن شمس | جلد = | سال= ۱۳۸۶ | ماه = | سال اصلی = |چاپ=دوم | ناشر =گسترش علوم پایه | مکان =تهران | شابک =۹۶۴-۷۸۱۷-۲۶-۶}}
* کتاب نظریه گرافها و کاربردهای آن نوشته باندی و مورتی، ترجمه حمید ضرابی زاده، [[موسسه دیباگران تهران]]
* کتاب ریاضیات گسسته نوشته [[ر. پ. گریمالدی]]، [[مرکز نشر دانشگاهی]]
* کتاب
* [http://graphtheorysoftware.com/ Graph Theory Software]
[[رده:نظریه گراف]]
| |||