دانشنامه فارسی اقتصاد - Persian Encyclopedia of Economics

در ریاضی و علوم کامپیوتر، نظریه گراف علمی است که بهمطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصلشده‌اند.به عبارت ساده‌تر به مجموعه‌ای از نقاط که بوسیله خطوط به هم وصل شده‌‌اند،گراف گویند. مفهوم گراف در سال 1736 توسط اویلر و با طرحراه‌حلی برای مساله پلKongsberg ارائه شد و به تدریج توسعه یافت.گراف‌ها امروزهکاربرد زیادی در علوم دارند. از گراف‌ها در شبکه‌ها،طراحی مدارهای الکتریکی, اصلاحهندسی خیابان‌ها برای حل مشکل ترافیک،و.... استفادهمیشود.

تعریف

فرض کنیدV یک مجموعه ناتهی وE زیرمجموعه‌ای ازباشد در اینصورت زوجرا یکگراف می نامندV. را مجموعه راس ها وE را مجموعه یال ها می گویند. اگر ترتیب قرارگرفتن راس ها در مجموعهE مهم باشد،گراف راگراف جهت‌دارمی گویند و یال از راسبه سمتراسرا بهصورتنشانمی‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس هایوبا نمادنشانمی‌دهند. تعداد راس های یک گراف رامرتبهو تعدادیال های آن رااندازهگراف می نامیم.
در شکل زيرگرافی را با شش راس وهفت یال مشاهده می کنیم

انواع گراف‌ها

گراف‌ها دارای انواع متعددی هستند که به برخی از آنهااشاره می‌کنیم:
گراف همبند
گراف ناهمبند
گراف کامل
گراف اویلری
گراف همیلتونی
گراف درختی
گراف مسطح
گراف دو بخشی
گراف چندبخشی
گرافk-مکعب
گراف چرخ 
گراف ستاره‌ای
گراف بازه‌ای
گراف اشتراکی
گراف منظم
گراف جهت‌دار

گراف‌ها و ساختار داده‌ها

هر گراف را می‌توان با یک ماتریس نمایش داد، که به آن ماتریس مجاورت گراف گویند. در این روش ازآرایه هااستفاده می‌کنیم.این ماتریس بهتعداد راس‌های گرافدارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راسو عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفرو یک است. با استفاده از این ماتریس می‌توان رئوسی را که با یک راس در ارتباط‌اند ونیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.

مسایل گراف

تئوری رنگ آمیزی
قضیه چهار رنگ
مسائل حل نشده در رنگ آمیزی
مسائل موجود در زمینه مسیر
هفت پلKongsberg
Minimum spanning tree
درختSteiner
مساله کوتاهترین مسیر
مساله پستچی چینی
مساله فروشنده دوره گرد
الگوریتم‌های مهم
الگوریتمkruskal
الگوریتمprim
الگوریتم کوتاهترین مسیر
منبع:http://daneshnameh.roshd.ir-1

To create link towards this article on your website,
copy and paste the text below in your page.

<style type="text/css"><!--.quote {width:350px; padding: 6px; border: solid 1px #456B8F; font: 10px helvetica, verdana, sans-serif; color: #222222; background-color: #ffffff}.quote a {font: 13px arial, serif; color: #003399; text-decoration: underline}.quote a:hover {color: #FF9900; }//--></style><div style="float:left;padding:5px;"><img src="http://tweetmeme.com/i/scripts/button.js" width="120" alt="" /></div><div class="quote"><a href="http://www.daneshnamah.com/index.php?option=com_content&view=article&id=669:1388-07-29-16-32-14&catid=15:economics&Itemid=3" target="_blank">نظریه گراف</a><br />چهارشنبه, ۲۹ مهر ۱۳۸۸<br /> در ریاضی و علوم کامپیوتر، نظریه گراف علمی است که بهمطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصلشده‌اند.به عبارت ساده‌تر...<div align="right" style="width:350px"><p style="text-align:right;">© 2010 - <a href="http://www.daneshnamah.com/" target="_blank">دانشنامه فارسی اقتصاد - Persian Encyclopedia of Economics</a></p></div></div>

Preview :

نظریه گراف
چهارشنبه, ۲۹ مهر ۱۳۸۸
در ریاضی و علوم کامپیوتر، نظریه گراف علمی است که بهمطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصلشده‌اند.به عبارت ساده‌تر...

© 2010 - دانشنامه فارسی اقتصاد - Persian Encyclopedia of Economics

Powered by QuoteThis © 2008

• افزودن جدید
• جستجو

نظر ها (0)

نوشتن نظر

Your Contact Details:

نام:

ایمیل: اعلام نکردناعلام کردن

آدرس سایت:

نظر:

عنوان:

قالب نوشته:         -رنگ-آبی کمرنگسیاهآبیبنفشخاکستریسبزلیموییقرمز آلبالوییسرمه ایزیتونیزرشکیقرمزنقره ایآبی سیرسفیدزرد -اندازه-ریزکوچکمعمولیبزرگبسیار بزرگ

Message:

Security

کد آنتی اسپم نمایش داده شده در عکس را وارد کنید.

Powered by !JoomlaComment 4.0 beta1

!joomlacomment 4.0 Copyright (C) 2009 Compojoom.com . All rights reserved."