نظریه گراف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
خنثی‌سازی ویرایش 21982219 توسط 192.15.148.59 (بحث) برچسب: خنثی‌سازی |
FreshmanBot (بحث | مشارکت‌ها) جز اصلاح فاصله مجازی + اصلاح نویسه با استفاده از AWB |
||
خط ۴:
'''نظریه گراف'''<ref>'''گراف''' واژهٔ مصوب فرهنگستان زبان و ادب پارسی به جای '''graph''' در [[زبان انگلیسی|انگلیسی]] و در حوزهٔ [[ریاضیات]] است. {{یادکرد وب| نشانی = http://www.persianacademy.ir/fa/wordspdf.aspx| عنوان =فرهنگ واژه‌های مصوّب فرهنگستان: ۱۳۷۶ تا ۱۳۸۵، بخش دوم: به ترتیب الفبای لاتینی، صفحهٔ ۱۰۲ | تاریخ بازدید = ۶ مرداد ۱۳۸۹| تاریخ = | ناشر = وب‌گاه رسمی فرهنگستان | زبان = فارسی}}</ref> شاخه‌ای از [[ریاضیات]] است که دربارهٔ [[گراف (ریاضی)|گراف‌ها]] بحث می‌کند. این مبحث در واقع شاخه‌ای از [[توپولوژی]] است که با [[جبر]] و [[نظریه ماتریس‌ها]] پیوند مستحکم و تنگاتنگی دارد. نظریهٔ گراف برخلاف شاخه‌های دیگر ریاضیات نقطهٔ آغاز مشخصی دارد و آن انتشار مقاله‌ای از [[لئونارد اویلر]]، ریاضیدان [[سوئیسی]]، برای حل [[مسئله پل‌های کونیگسبرگ]] در سال ۱۷۳۶ است.<ref>{{پک|گریمالدی|۱۳۷۹|ف=نظریه گراف و کاربردهای آن|ک=ریاضیات گسسته و ترکیبیاتی|ص=۷۶۶}}</ref>
پیشرفت‌های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف
== تاریخچه ==
خط ۱۳:
در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس [[مسئله چهار رنگ|چهار رنگ]] بود که نخستین بار توسط [[فرانسیس گوثری]] در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط [[کنث ایپل]] و [[ولفگانگ هیکن]] و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد.<ref>{{پک|گریمالدی|۱۳۷۹|ف=نظریه گراف و کاربردهای آن|ک=ریاضیات گسسته و ترکیبیاتی|ص=۷۵۵}}</ref>
ایدهٔ مهم دوم، [[دور همیلتونی]] بود. این دور به افتخار [[ویلیام همیلتون|سر ویلیام روآن همیلتون]] نامگذاری
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئلهٔ مشخص کردن [[گراف مسطح|گراف‌های مسطح]] را [[کازیمیر کوراتوفسکی]]، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین [[
== تعریف ==
خط ۲۶:
مهم‌ترین کاربرد گراف [[مدل‌سازی]] پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک [[ماتریس]] به نام ماتریس وقوع گراف ذخیره کرد یا [[الگوریتم|الگوریتمهای]] مناسب مانند الگوریتم دایجسترا یا الگوریتم کروسکال و... را بر روی آن اعمال نمود.
یکی از قسمت‌های پرکاربرد نظریهٔ گراف، [[گراف مسطح]] است که به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل
نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف [[علوم مهندسی]] (مانند عمران)، [[باستان‌شناسی]] (کشف محدوده یک تمدن) و... است.
روابط میان
برای نمایش تصویری گراف‌ها معمولاً از نقطه یا دایره برای کشیدن
{{ویکی‌انبار-رده|Graph theory}}
| |||