نمایش مبدأ برای نظریه گراف

[[پرونده:6n-graf.svg|بندانگشتی|چپ|270px|نمایش تصویری یک گراف]]

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

پیشرفت‌های اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده‌است به گونه‌ای که هم‌اکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینه‌های گوناگون مانند [[نظریه کدگذاری]]، [[تحقیق در عملیات]]، [[آمار]]، [[شبکه‌های الکتریکی]]، [[علوم رایانه]]، [[شیمی]]، [[زیست‌شناسی]]، [[علوم اجتماعی]] و سایر زمینه‌ها گردیده‌است.<ref>{{پک|وست|۱۳۸۶|ف=|ک=آشنایی با نظریهٔ گراف|ص=۵}}</ref><ref name=":0">{{cite journal|last=Mashaghi|first=A.|display-authors=etal|year=2004|title=Investigation of a protein complex network|journal=European Physical Journal B|volume=41|issue=1|pages=113–121|arxiv=cond-mat/0304207|bibcode=2004EPJB...41..113M|doi=10.1140/epjb/e2004-00301-0}}</ref>

== تاریخچه ==
برخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن [[مسئله پل‌های کونیگسبرگ|مسئلهٔ هفت پل کونیگسبرگ]] است که در سال ۱۷۳۶ توسط [[لئونارد اویلر]] حل شد.<ref name=":1">Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". ''Comment. Acad. Sci. U. Petrop'' 8, 128–40.</ref> در سال ۱۷۵۲ قضیهٔ اویلر برای [[گراف مسطح|گراف‌های مسطح]] ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.<ref>{{cite journal|last=Shields|first=Rob|date=December 2012|title=Cultural Topology: The Seven Bridges of Königsburg 1736|url=http://journals.sagepub.com/doi/pdf/10.1177/0263276412451161|volume=29|issue=4-5|pages=43–57|doi=10.1177/0263276412451161|work=Theory Culture and Society}} Shields provides a discussion of the social significance of Euler's engagement with this popular problem and its significance as an example of (proto-)topological understanding applied to everyday life.</ref>

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

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

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

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

== تعریف ==
تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند.

یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد؛ مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، می‌توانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. [[لئونارد اویلر]] ریاضیدان بزرگ مفهوم گراف را برای حل [[مسئله پل‌های کونیگسبرگ]] ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم [[انفورماتیک]] بوده‌است.<ref name=":1"/>

مهم‌ترین کاربرد گراف [[مدل‌سازی]] پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک [[ماتریس]] به نام ماتریس وقوع گراف ذخیره کرد یا [[الگوریتم]]های مناسب مانند الگوریتم دایکسترا یا [[الگوریتم کراسکال|الگوریتم کروسکال]] و… را بر روی آن اعمال نمود.

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

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف [[علوم مهندسی]] (مانند عمران)، [[باستان‌شناسی]] (کشف محدوده یک تمدن) و… است.<ref name=":0"/>

روابط میان رأس‌های یک گراف را می‌توان با کمک [[ماتریس]] بیان کرد.

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

== رابطه‌ها و ماتریس‌ها ==
در قسمت [[گراف]]‌ها به هر گراف یک ماتریس صفر و یک نسبت داده می‌شود. [[ماتریس]] مجاورت گراف‌های جهت دار هم به‌طور مشابه تعریف می‌شود. به‌طور مثال [[ماتریس مجاورت]] [[گراف جهت‌دار|گراف جهت دار]] زیر به صورت مقابل است:

[[پرونده:ماتریس مجاورت گراف جهت دار.jpg|400 px|ماتریس مجاورت گراف جهت دار]]

پس می‌توان این ماتریس را متناظر با رابطه مقابل در نظر گرفت. توجه کنید که درایه‌های ij ام ماتریس مساوی با ۱ است اگر و تنها اگر iRj.

اکنون می‌توانیم ویژگی‌های‌های مربوط به رابطه‌ها را برای ماتریس‌ها بیان کنیم؛ مثلاً ویژگی بازتابی یعنی این که همه [[درایه]]‌های [[قطر اصلی]] ماتریس ۱ باشند. بقیه ویژگی‌ها را به زبان ماتریس بیان کنید.

در این‌جا فقط صرفاً ماتریس‌های صفر و یک را در نظر می‌گیریم تا بتوانیم عملیات‌های ضرب و جمع را برای یک [[مجموعه]] صفر و یک به دست آوریم.

{{ویکی‌انبار-رده|Graph theory}}

== جستارهای وابسته ==
* [[یکریختی گراف]]
* [[گراف (ریاضی)]]

== پانویس ==
{{پانویس|۲}}

== منابع ==
* کتاب آشنایی با نظریهٔ گراف نوشتهٔ [[علیرضا علیپور]]، [[انتشارات فاطمی]]
* {{یادکرد کتاب | نام خانوادگی =گریمالدی | نام =رالف پ. | عنوان =ریاضیات گسسته و ترکیبیاتی | ترجمه =دکتر محمدعلی رضوانی و دکتر بیژن شمس | جلد =۳ | سال= ۱۳۷۹ | سال اصلی = | ناشر =[[انتشارات فاطمی]] | مکان =تهران | شابک =964-318-256-8}}
* {{یادکرد کتاب | نام خانوادگی =وست | نام =داگلاس بی. | عنوان =آشنایی با نظریهٔ گراف | ترجمه =دکتر بیژن شمس | جلد = | سال= ۱۳۸۶ | سال اصلی = | ناشر =گسترش علوم پایه | مکان =تهران | شابک =964-7817-26-6}}
* کتاب نظریه گراف‌ها و کاربردهای آن نوشته باندی و مورتی، ترجمه حمید ضرابی زاده، [[مؤسسه دیباگران تهران]]
* کتاب [[ریاضیات گسسته]] نوشته [[ر. پ. گریمالدی]]، [[مرکز نشر دانشگاهی]]
* کتاب نظریهٔ الگوریتمی و کاربردی گرافها نوشته [[گری چارتراند، آرترود اولرمن]]، ترجمه دکتر سید مهدی تشکری هاشمی، [[انتشارات دانشگاه امیرکبیر]]
* [http://graphtheorysoftware.com/ Graph Theory Software] {{Webarchive|url=https://web.archive.org/web/20130313205057/http://graphtheorysoftware.com/ |date=13 مارس 2013 }} نرم‌افزارهای گراف تولید شده در دانشگاه صنعتی شریف
* {{یادکرد کتاب | نام خانوادگی۱ = Kenneth H| نام۱ = Rosen | عنوان = Discrete Mathematics and its Applications| سری = SIGS Reference Library | سال = 1998| ناشر = William C Brown Pub; 4th edition | شابک = 0072899050| نشانی = https://www.amazon.com/Discrete-Mathematics-Applications-Kenneth-Rosen/dp/0072899050| بازبینی =| زبان = en}}

{{علوم رایانه}}
{{شاخه‌های اصلی ریاضیات}}
{{موضوعات سامانه‌های پیچیده}}
{{ریاضیات صنعتی و کاربردی}}
{{داده‌های کتابخانه‌ای}}


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