منو
 کاربر Online
727 کاربر online
تاریخچه ی: نظریه گراف

در حال مقایسه نگارشها

نگارش واقعی نگارش:15

img/daneshnameh_up/5/54/ka.jpg




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








تعریف

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهت‌دار می گویند و یال از راس به سمت راس را به صورت نشان می‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس های و با نماد نشان می‌دهند.
img/daneshnameh_up/7/7d/6n-graf.jpg


تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم

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

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

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

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

مسایل گراف


الگوریتم‌های مهم


همچنین ببینید


پیوندهای خارجی

http://olympiad.roshd.ir/computercontentlist.html
http://math.youngzones.org/Konigsberg.html
www.wikipedia.com



img/daneshnameh_up/5/54/ka.jpg



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








تعریف

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهت دار می گویند و یال از راس به سمت راس را به صورت نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های و با نماد نشان میدهند.
img/daneshnameh_up/7/7d/6n-graf.jpg


تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم

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

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

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

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

مسایل گراف


الگوریتمهای مهم


همچنین ببینید


پیوندهای خارجی

http://math.youngzones.org/Konigsberg.html
www.wikipedia.com


تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 27 فروردین 1385 [14:24 ]   19   سعید صدری      جاری 
 سه شنبه 22 فروردین 1385 [17:23 ]   18   سعید صدری      v  c  d  s 
 سه شنبه 22 فروردین 1385 [17:04 ]   17   سعید صدری      v  c  d  s 
 سه شنبه 22 فروردین 1385 [17:02 ]   16   سعید صدری      v  c  d  s 
 سه شنبه 22 فروردین 1385 [16:58 ]   15   سعید صدری      v  c  d  s 
 دوشنبه 03 مرداد 1384 [04:25 ]   14   بابک خسروشاهی      v  c  d  s 
 شنبه 03 بهمن 1383 [07:41 ]   13   علی هادی      v  c  d  s 
 شنبه 03 بهمن 1383 [07:37 ]   12   علی هادی      v  c  d  s 
 چهارشنبه 30 دی 1383 [10:24 ]   11   علی هادی      v  c  d  s 
 چهارشنبه 30 دی 1383 [10:24 ]   10   علی هادی      v  c  d  s 
 چهارشنبه 30 دی 1383 [09:59 ]   9   علی هادی      v  c  d  s 
 چهارشنبه 30 دی 1383 [09:10 ]   8   علی هادی      v  c  d  s 
 چهارشنبه 30 دی 1383 [08:48 ]   7   علی هادی      v  c  d  s 
 سه شنبه 29 دی 1383 [10:24 ]   6   علی هادی      v  c  d  s 
 سه شنبه 29 دی 1383 [10:10 ]   5   علی هادی      v  c  d  s 
 سه شنبه 29 دی 1383 [09:42 ]   4   علی هادی      v  c  d  s 
 سه شنبه 29 دی 1383 [08:21 ]   3   علی هادی      v  c  d  s 
 یکشنبه 27 دی 1383 [07:22 ]   2   نفیسه ناجی      v  c  d  s 
 یکشنبه 26 مهر 1383 [12:37 ]   1   محمد نوید      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..