V{maketoc}
||در ریاضی و علوم کامپیوتر، نظریه گرافعلمی است که به مطالعه گرافها میپردازد.گراف مجموعهای از راسهاست که بوسیله یالها به هم وصل شدهاند.به عبارت سادهتر به مجموعهای از نقاط که بوسیله خطوط به هم وصل شدهاند، گراف گویند. مفهوم گراف در سال 1736 توسط ((اویلر)) و با طرح راهحلی برای مساله پل konigsberg ارائه شد و به تدریج توسعه یافت.گرافها امروزه کاربرد زیادی در علوم دارند. از گرافها در شبکهها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابانها برای حل مشکل ترافیک،و.... استفاده میشود.||
!تعریف
فرض کنید V یک مجموعه ناتهی و E زیرمجموعهای از {TEX()} {V\times V} {TEX} باشد در این صورت زوج
{TEX()} {G=\left ( V,E \right )} {TEX} را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را ((گراف جهتدار)) می گویند و یال از راس
{TEX()} {v_1} {TEX} به سمت راس
{TEX()} {v_2} {TEX} را به صورت
{TEX()} {e=\left ( v_1,v_2 \right )} {TEX} نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های
{TEX()} {v_1} {TEX} و
{TEX()} {v_2} {TEX} با نماد
{TEX()} {e=\left \{ v_1,v_2 \right \}} {TEX} نشان میدهند.
تعداد راس های یک گراف را __مرتبه__ و تعداد یال های آن را __اندازه__ گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم
---
!انواع گرافها
گرافها دارای انواع متعددی هستند که به برخی از آنها اشاره میکنیم:
*((گراف همبند))
*((گراف ناهمبند))
*((گراف کامل))
*((گراف اویلری))
*((گراف همیلتونی))
*((گراف درختی))
*((گراف مسطح))
*((گراف دو بخشی))
*((گراف چندبخشی))
*((گراف k-مکعب))
*((گراف چرخ))
*((گراف ستارهای))
*((گراف بازهای))
*((گراف اشتراکی))
*((گراف منظم))
*((گراف جهتدار))
---
!گرافها و ساختار دادهها
هر گراف را میتوان با یک ماتریس نمایش داد ، که به آن ((ماتریس مجاورت گراف)) گویند. در این روش از ((آرایه|آرایه ها))استفاده میکنیم.این ماتریس به تعداد راسهای گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس میتوان رئوسی را که با یک راس در ارتباطاند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.
---
!مسایل گراف
*((تئوری رنگ آمیزی))
*((قضیه چهار رنگ))
*((مسائل حل نشده در رنگ آمیزی))
*مسائل موجود در زمینه مسیر
**((هفت پل konisberg))
*((Minimum spanning tree))
**((درخت steiner))
**((مساله کوتاهترین مسیر))
**(( مساله پستچی چینی))
**((مساله فروشنده دوره گرد))
---
!الگوریتمهای مهم
*((الگوریتم kruskal))
*((الگوریتم prim))
*(( الگوریتم کوتاهترین مسیر))
---
!همچنین ببینید
*((ریاضیات گسسته))
*((همریختی گرافها))
*((گراف پترسن))
---
!پیوندهای خارجی
[http://olympiad.roshd.ir/computercontentlist.html]
[http://math.youngzones.org/Konigsberg.html]
[www.wikipedia.com]