نظريه گراف

[nafise sadeghi]

در ریاضی و علوم کامپیوتر، نظریه گرافعلمی است که به مطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصل شده‌اند.به عبارت ساده‌تر به مجموعه‌ای از نقاط که بوسیله خطوط به هم وصل شده‌‌اند، گراف گویند. مفهوم گراف در سال 1736 توسط اویلر (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%A7%D9%88%DB%8C%D9%84%D8%B1) و با طرح راه‌حلی برای مساله پل konigsberg ارائه شد و به تدریج توسعه یافت.گراف‌ها امروزه کاربرد زیادی در علوم دارند. از گراف‌ها در شبکه‌ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک،و.... استفاده میشود.








تعریف

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/43d5cb18328ea0653f7a52903a12fbff.png باشد در این صورت زوج http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ee8f829b9f8784add8d4de522221c8a7.png را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهت‌دار می گویند و یال از راس http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/68470ca1dcfa6d65e398d643d8e4a234.png به سمت راس http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5d2af5482f8f24f7f413003b834e829d.png را به صورت http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/da9ff506e357562a5d413504638e9d66.png نشان می‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس هایhttp://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/68470ca1dcfa6d65e398d643d8e4a234.png وhttp://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5d2af5482f8f24f7f413003b834e829d.png با نماد http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bd58ecb70442350fcf4300965136636c.png نشان می‌دهند.
http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/7/7d/6n-graf.jpg

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

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

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


گراف همبند
گراف ناهمبند
گراف کامل (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%DA%AF%D8%B1%D8%A7%D9%81+%DA%A9%D8% A7%D9%85%D9%84)
گراف اویلری
گراف همیلتونی
گراف درختی
گراف مسطح
گراف دو بخشی (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%DA%AF%D8%B1%D8%A7%D9%81+%D8%AF%D9% 88+%D8%A8%D8%AE%D8%B4%DB%8C)
گراف چندبخشی
گراف k-مکعب
گراف چرخ (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%DA%AF%D8%B1%D8%A7%D9%81+%DA%86%D8% B1%D8%AE)
گراف ستاره‌ای
گراف بازه‌ای (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%DA%AF%D8%B1%D8%A7%D9%81+%D8%A8%D8% A7%D8%B2%D9%87%E2%80%8C%D8%A7%DB%8C)
گراف اشتراکی
گراف منظم
گراف جهت‌دار
گراف‌ها و ساختار داده‌ها

هر گراف را می‌توان با یک ماتریس نمایش داد ، که به آن ماتریس مجاورت گراف (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B 3+%D9%85%D8%AC%D8%A7%D9%88%D8%B1%D8%AA+%DA%AF%D8%B 1%D8%A7%D9%81) گویند. در این روش از آرایه هااستفاده می‌کنیم.این ماتریس به تعداد راس‌های گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس می‌توان رئوسی را که با یک راس در ارتباط‌اند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.

مسایل گراف


تئوری رنگ آمیزی
قضیه چهار رنگ
مسائل حل نشده در رنگ آمیزی
مسائل موجود در زمینه مسیر

هفت پل konisberg

Minimum spanning tree

درخت steiner
مساله کوتاهترین مسیر
مساله پستچی چینی
مساله فروشنده دوره گرد

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


الگوریتم kruskal
الگوریتم prim
الگوریتم کوتاهترین مسیر

[Only Math]

نظریه گراف:

نظریه گراف شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی بـه نام گراف بحث می‌کند. بـه صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس کـه با یالهایی بـه هم وصل شـده‌انـد. تعـریـف دقـیـق‌تر گراف به این صـورت اسـت کـه گراف مـجـمـوعـه‌ای از رأس‌ها اسـت کـه توسط خانواده‌ای از زوج‌های مرتب کـه هـمان یال‌ها هـسـتـنـد بـه هم مربـوط شـده‌انـد.

یالها بر دو نوع ساده و جهـت دار هـسـتـنـد که هر کدام در جای خود کاربـردهای بـسـیـاری دارد. مثلا اگر صـرفـا اتصال دو نقطه مانند اتصال تهران و زنجان بـا کمک آزادراه مد نـظـر شـما باشـد کافیست آن دو شهر را بـا دو نقطـه نمایش داده و اتـوبـان مزبـور را بـا یـالـی سـاده نمایـش دهـیـد. امـا اگر بین دو شهر جاده ای یک طـرفه وجود داشـتـه بـاشد آنگاه لازمست تا شما بـا قـرار دادن یالی جهت دار مسـیـر حرکـت را در آن جاده مـشـخـص کـنـیـد.

آغاز نـظـریـهٔ گـراف بـه سـدهٔ هـجـدهـم بـر مـی‌گـردد. اویـلـر ریاضیـدان بزرگ مـفـهـوم گـراف را برای حل مـسـئـلـه پل‌های کـونـیگـسـبـرگ ابداع کرد اما رشد و پـویـایــی ایـن نظـریــه عـمـدتـاً مـربـوط بــه نـیـم سـدهٔ اخـیـر و بـا رشـد عـلـم داده‌ورزی یـا انـفـورمـاتـیـک بـوده اسـت.

مهـم‌تـریـن کـاربـرد گـراف مـدل‌سـازی پـدیـده‌های گـوناگـون و بـررسی بر روی آنهاسـت. بـا گـراف می‌توان بـه راحـتی یک نـقـشـه بـسـیار بـزرگ یـا شـبـکـه‌ای عـظـیـم را در درون یـک مـاتـریـس بـه نـام مـاتـریـس وقـوع گـراف ذخـیـره کرد و یـا الگــوریـتـم های‌ مناسب مانـنـد الگـوریـتـم دایـسـتـرا یـا کـروسـکال و ... را بـر روی آن اعـمـال نـمـود.

یکی از قـسـمـت‌های پـركاربـرد نـظـریـهٔ گـراف، گـراف‌های مـسـطح یـا هـامـنی اسـت کـه بـه بـررسـی گـراف‌هـایـی می‌پـردازد كـه مـی‌تـوان آن‌ها را بـه نـحـوی روی صـفـحه كـشـیـد كـه یـال‌ها جـز در مـحـل راس ها یـكـدیگـر را قطع نكـنـنـد. این نـوع گـراف در سـاخت جـاده ها و حـل مـسـاله کلاسـیک و قـدیمی سه خانه و سـه چاه آب بـه کار مـی رود.

نـظـریـه گـراف یکـی از پـرکـاربـردتـریـن نـظـریــه ها در شـاخـه های مخـتـلـف عـلـوم مهـنـدسـی مانـنـد عمران، باسـتـانـشـنـاسـی کـشـف محدوده یک تمدن و ... اسـت.

انواع گراف :

گـراف سـاده : هـر گـراف g زوج مـرتـبی مـانـنـد (v , e) اسـت کـه در آن v مجـمـوعـه ای مـتـنـاهـی و نـاتهـی اسـت و e زیـرمـجـمـوعـه ای از تـمـام زیـر مـجـمـوعـه هـای دو عـضـوی v مـی بـاشــد . اعـضـای v را رأس هـای g و اعـضـای e را یـالهـای g مـی نامـیـم. بـه بـیـان سـاده تـر بـیـن دو رأس یـک گـراف سـاده حـداکـثـر یـک یـال وجـود دارد.

گراف چـندگانه : هـرگاه بـیـن دو رأس مـتـمـایـز از یـک گـراف بـیـش از یـک یـال وجـود داشـتـه بـاشـد، آن را یـک گـراف چـنـد گـانـه مـی گـویـیـم.

گـراف جهـت دار: هـر گـراف g زوج مـرتـبـی مانـنـد (v,e) اسـت کـه در آن v مجموعـه ای مـتـنـاهـی و نـاتهی است و e زیـرمـجـموعـه ای از مجموعه ی تـمـام زوج مـرتـب هـای مـتـشـکـل از اعـضـای v اسـت.

[babak razaghi]

سلام , عرض ادب

1 - لطفا توضیح کاملی در مورد گرافهای مکعبی بدهید .

2 - در چه مواردی میتوان از گرافهای مکعبی استفاده کرد ؟

3 - چگونه میتوان ارتباطی بین گرافهای مکعبی و مشاغلی که با آن سر و کار داریم، برقرار نمود؟

با تشکر

[mohamad sam]

با سلام من دانشجوي ارشد رشته نظريه گراف هستم

اگر ممكن است در مورد domination in graph مقالاتي را ارايه دهيد

قربون همتون برم graph

[صبا محمدي]

دوست عزيز به سايت زير مراجعه كنيد /www.civilica.com

[صبا محمدي]

K – مکعب Qk گرافی است که رئوس آن متناظر با دنباله (a1 . a2 , … ak) است ، که در آن هر ai صفر یا یک است ، و یالهای آن عناصری را به هم وصل می کند که فقط در میان اختلاف دارند . توجه کنید که گراف مکعبی ، همان گراف Q3است . می توان دید که QK تعداد K2 رأس و K-12K بال دارد ، و منتظم از مرتبه K است .

[MorphiN]

سلام , عرض ادب

1 - لطفا توضیح کاملی در مورد گرافهای مکعبی بدهید .

2 - در چه مواردی میتوان از گرافهای مکعبی استفاده کرد ؟

3 - چگونه میتوان ارتباطی بین گرافهای مکعبی و مشاغلی که با آن سر و کار داریم، برقرار نمود؟

با تشکر

سلام . منم دقیقا همین سوال برام پیش اومده . ممنون میشم از راهنماییتون ;;)

[صبا محمدي]

يك گراف «http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gif مكعب» (k-Cube) گرافي است كه رؤوس آن http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gifتايي از «صفر» و «يك» هستند كه دو رأس آن به يكديگر متصل هستند اگر و فقط اگر دو رأس‌شان دقيقاً در يك مؤلفه با يكديگر تفاوت داشته باشند.
به‌عبارت ديگر اگر http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gifعددي طبيعي باشد منظور از «http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gif مكعب» گرافي است كه رأس‌هاي آن همه‌ي دنباله‌هاي http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gifرقمي از «صفر» و «يك» هستند و دو رأس در اين گراف مجاور بوده هرگاه دنباله‌هاي متناظرشان دقيقاً در يك مؤلفه اختلاف داشته باشند (شكل 1).







http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036-11.gif
شكل 1 – گراف «http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gif مكعب» به‌ترتيب از سمت چپ:
«يك مكعب»، +«دو مكعب» و «سه مكعب».





مي‌توان نشان داد كه يك گراف «http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(13).gif مكعب» (k-Cube) داراي ويژگي‌‌هايي نظير ذيل است:

- تعداد رؤوس = http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(25).gif
- تعداد يال‌ها = http://roshd.ir/roshd/Portals/0/0and1/olympiad/Computer/BreakTime/Bt-Com-036%20(26).gif
- گرافي «دوبخشي» (Bipartite) است.

[mig]

با سلام ،دوستان در مورد گراف های آزاد-h یا h-free graph کسی اطلاعای داره مهمه برام.ممنون:-/:-/