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

تفاوت با نگارش: 12

Lines: 1-72Lines: 1-78
-V{maketoc} +
 
 
 
 
  
-{picture file=img/daneshnameh_up/ka.jpg} +{picture=ka.jpg}
  
 
 
 
 
 +V{maketoc}
-
در ریاضی و علوم کامپیوتر، نظریه گراف بیان ویگیهای یک گراف میپردازد.گراف مجموعه ای از راسهاست که بوسیله یالها به هم وصل شده اند.به عبارت ساده تر به مجموعه ای از نقاط که بوسیله خطوط به هم وصل شده اند، گراف گویند />مفهوم گراف در سال 1736 توسط اویلر و با طرح راه حلی برای مسله پل konigsberg ارائه شد،و به تدریج توسعه یافت.گرافها امروزه کاربرد زیادی در علوم دارند. از گرافها در شبکه ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابانها برای حل مشکل ترافیک،و.... استفاده میشود.
+||در ریاضی و علوم کامپیوتر، نظریه گرافمی است ه به مطالعه گراف‌ها مپردازد.گراف مجموعهای از راسهاست که بوسیله یالها به هم وصل شدهاند.به عبارت سادهتر به مجموعهای از نقاط که بوسیله خطوط به هم وصل شده‌‌اند، گراف گویند. مفهوم گراف در سال 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} نشان مدهند.
 
 
 
 
  
-{picture file=img/daneshnameh_up/6n-graf.jpg} +{picture=6n-graf.jpg}
  
 
 
 
 
-تعداد راسهای یک گراف را __مرتبه__ و تعداد یالهای آن را __اندازه__ گراف مینامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده میکنیم


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

((گراف همبند))
((گراف کامل))
((گراف اویلری))
((گراف همیلتونی))
((گراف درختی))
((گراف مسطح))

!گرافها و ساختار داده ها
هر گراف را میتوان با یک ماتریس نمایش داد ، که به آن ((ماتریس مجاورت گراف)) گویند. در این روش از ((آرایه|آرایه ها))استفاده میکنیم.این ماتریس به تعداد راسهای گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس میتوان رئوسی را که با یک راس در ارتباطند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.
+تعداد راس های یک گراف را __مرتبه__ و تعداد یال های آن را __اندازه__ گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم
---
!انواع گرافها
گرافها دارای انواع متعددی هستند که به برخی از آنها اشاره مکنیم:
*((گراف همبند))
*((گراف ناهمبند))
*((گراف کامل))
*((گراف اویلری))
*((گراف همیلتونی))
*((گراف درختی))
*((گراف مسطح))
*((گراف دو بخشی))
*((گراف چندبخشی))
*((گراف k-مکعب))
*((گراف چرخ))
*((گراف ستاره‌ای))
*((گراف بازه‌ای))
*((گراف اشتراکی))
*((گراف منظم))
*((گراف جهت‌دار))
---

!گرافها و ساختار دادهها
هر گراف را متوان با یک ماتریس نمایش داد ، که به آن ((ماتریس مجاورت گراف)) گویند. در این روش از ((آرایه|آرایه ها))استفاده مکنیم.این ماتریس به تعداد راسهای گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس متوان رئوسی را که با یک راس در ارتباط‌اند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.
---
 !مسایل گراف !مسایل گراف
-!!((تئوری رنگ آمیزی))
!!!((قضیه چهار رنگ))
!!!((مسائل حل نشده در رنگ آمیزی))
!!مسائل موجود در زمینه مسیر
!!!((هفت پل konisberg))
!!!((Minimum spanning tree))
!!!((درخت steiner))
!!!((مسله کوتاهترین مسیر))
!!!(( مسله پستچی چینی))
!!!((مسله فروشنده دوره گرد))

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

!!
((الگوریتم kruskal))
!!((الگوریتم prim))
!!(( الگوریتم کوتاهترین مسیر))
+*((تئوری رنگ آمیزی))
*((قضیه چهار رنگ))
*((مسائل حل نشده در رنگ آمیزی))
*مسائل موجود در زمینه مسیر
**((هفت پل 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]

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..