V{maketoc}
{picture file=img/daneshnameh_up/ka.jpg}
|
در ریاضی و علوم کامپیوتر، نظریه گراف به بیان ویژگیهای یک گراف میپردازد.گراف مجموعه ای از راسهاست که بوسیله یالها به هم وصل شده اند.به عبارت ساده تر به مجموعه ای از نقاط که بوسیله خطوط به هم وصل شده اند، گراف گویند
مفهوم گراف در سال 1736 توسط اویلر و با طرح راه حلی برای مسئله پل konigsberg ارائه شد،و به تدریج توسعه یافت.گرافها امروزه کاربرد زیادی در علوم دارند. از گرافها در شبکه ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابانها برای حل مشکل ترافیک،و.... استفاده میشود.
!تعریف
فرض کنید v یک مجموعه ناتهی باشد در این صورت زوج
{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} نشان میدهند.
{picture file=img/daneshnameh_up/6n-graf.jpg}
|
تعداد راسهای یک گراف را __مرتبه__ و تعداد یالهای آن را __اندازه__ گراف مینامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده میکنیم
!انواع گرافها
گرافها دارای انواع متعددی هستند که به برخی از آنها اشاره میکنیم:
((گراف همبند))
((نظریه گراف کامل))
((گراف اویلری))
((گراف همیلتونی))
((گراف درختی))
((گراف مسطح))
!گرافها و ساختار داده ها
هر گراف را میتوان با یک ماتریس نمایش داد ، که به آن ((ماتریس مجاورت گراف)) گویند. در این روش از ((آرایه|آرایه ها))استفاده میکنیم.این ماتریس به تعداد راسهای گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس میتوان رئوسی را که با یک راس در ارتباطند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.
!مسایل گراف
!!((تئوری رنگ آمیزی))
!!!((قضیه چهار رنگ))
!!!((مسائل حل نشده در رنگ آمیزی))
!!مسائل موجود در زمینه مسیر
!!!((هفت پل konisberg))
!!!((Minimum spanning tree))
!!!((درخت steiner))
!!!((مسئله کوتاهترین مسیر))
!!!(( مسئله پستچی چینی))
!!!((مسئله فروشنده دوره گرد))
!الگوریتمهای مهم
!!((الگوریتم kruskal))
!!((الگوریتم prim))
!!(( الگوریتم کوتاهترین مسیر))
!پیوندهای خارجی
[http://math.youngzones.org/Konigsberg.html]
[www.wikipedia.com]