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

 

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

برخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن [[مسئله پل‌های کونیگسبرگ|مسئلهٔ هفت پل کونیگسبرگ]] است که در سال ۱۷۳۶ توسط [[لئونارد اویلر]] حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برای [[گراف مسطح|گراف‌های مسطح]] ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.

 

 

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

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. [[اولر]] ریاضیدان بزرگ مفهوم گراف را برای حل [[مسئله پل‌های کونیگسبرگ]] ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم [[انفورماتیک]] بوده‌است.

 

 

یکی از قسمت‌های پرکاربرد نظریهٔ گراف، [[گراف مسطح]] است که به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.

برای نمایش تصویری گراف‌ها معمولاً از نقطه یا دایره برای کشیدن راس‌ها و از کمان یا خط راست برای کشیدن یال بین راس‌ها استفاده می‌شود.

 

 

== جستارهای وابسته ==

* کتاب نظریهٔ الگوریتمی و کاربردی گرافها نوشته [[گری چارتراند، آرترود اولرمن]]، ترجمه دکتر سید مهدی تشکری هاشمی، [[انتشارات دانشگاه امیرکبیر]]

* [http://graphtheorysoftware.com/ Graph Theory Software] نرم‌افزارهای گراف تولید شده در دانشگاه صنعتی شریف

[[رده:نظریه گراف]]