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