گراف (ریاضی): تفاوت میان نسخه‌ها

== درجه راس‌هارأس‌ها ==

در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه راس‌هایرأس‌های یک گراف با دو برابر تعداد یال‌های ان گراف برابر است.

گرافی است که بتوان رئوس آن را به گونه ایگونه‌ای به دو مجموعهٔ u و v تقسیم کرد که گراف‌های هر زیرگروه (v یا u)دو به دو با هم همسایه نبوده اما با حداقل یکی از رئوس مجموعهٔ دیگر همسایگی داشته باشند.

* یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنهاآن‌ها برابر مجموعه A باشد؛ و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: '''X'''<math>\bigcup</math>'''Y = V''' و '''X'''<math>\bigcap</math>'''Y = '''<math>\varnothing</math>

'''[[گراف جهت دارو کاربردهای آن]]'''گراف جهت دار D، یک سه تایی مرتب(O(D) و A(D) و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها ویک مجموعه (D) A مجزای از V(D)از کمانها و یک تابع وقوع O(D)که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت می‌دهد. اگر a یک کمان وu,v دو راس باشند به طوریبه‌طوری که(u,v) =(a)O (D)، آنگاه می‌گوییم که u,a را به v وصل کرده است؛کرده‌است؛ u، دم v,a سرa نامیده می‌شود.

'''[[گراف مسطح]]:''' گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در راس‌هارأس‌ها قطع کنند.

می‌توان از '''[[گراف‌های تماس تلفنی]]''' رای مدل کردن تماس‌های تلنفی برقرار شده در یک شبکه مانند شکبه تلفن راه دور استفاده کرد؛ که در ان راس‌هارأس‌ها شماره تلفن‌ها و یال‌ها ارتباط‌های برقرار شده بین شماره تلفن‌ها است

=== گراف همپوشانی منابع غذایی در بوم شناسیبوم‌شناسی ===

'''[[گراف‌های همکاری]]''' برا مدل کردن همکاری نویسندگان در نوشتن مقالات علمی، می‌توان از یک گراف همکاری استفاده کرد. در یک گراف همکاری، رئوس، افراد (شاید محدود به اعضای یک انجمن دانشگاهی خاص) را نمایش می‌دهند و یال‌ها در صورتی دو نفر را بهم وصل می‌کند که آن دو نفر، مقاله ایمقاله‌ای را به طوربه‌طور مشترک نوشته باشند.

با اجرای همزمانهم‌زمان جملات مشخص یک برنامه کامپیوتری، می‌توان آن برنامه را سریع تر اجرا کرد. مهم است که جمله ایجمله‌ای که نتایج جملاتی که هنوز اجرا نشده‌اند، نیاز دارد، اجرا نشود. وابستگی جملات به جملات پیشین را می‌توان با یک [[گراف]] جهت دار نمایش داد. هر جمله با یک راس نمایش داده می‌شود و در صورتی یالی بین یک راس و راس دوم در نظر گرفته می‌شود که جمله نشان داده می‌شود با راس دوم نتواند قبل از اجرای جمله نشان داده شده استشده‌است با راس اول اجرا شود. این [[گراف]] یک [[گراف]] تقدم نامیده می‌شود.<ref>{{یادکرد کتاب | نام خانوادگی۱ = Kenneth H| نام۱ = Rosen | فصل = Graph| عنوان = Discrete Mathematics and its Applications| سری = SIGS Reference Library | سال = 1998| ناشر = William C Brown Pub; 4th edition | شابک = 0072899050| نشانی = https://www.amazon.com/Discrete-Mathematics-Applications-Kenneth-Rosen/dp/0072899050| بازبینی = 2007| زبان = en}}</ref>

در شکل زیر یک برنامه کامپیوتری و [[گراف]] ان نشان داده شده استشده‌است. برای مثال این گراف نشان می‌دهد که جمله S_5 نمی‌تواند قبل از جملات S_2 , S_3 و S_1 اجرا شود.

* اگر درجهٔ همهٔ راس‌هارأس‌ها در گراف ساده با هم برابر و برابر بزرگترین درجهٔ ممکن (یعنی p-۱) باشد، گراف مورد نظر منتظم کامل است. در این گونه گراف‌ها، رابطهٔ میان رأس‌ها و یال‌ها چنین است:

* اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطهٔ بعدی نرسد) می‌گویند گراف درختی است. در اینگونهاین‌گونه گراف‌ها فرمول زیر صدق می‌کند (شرط لازم):

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

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

درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاه‌های معادلات خطی مربوط به شبکه‌های الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد وقتی مثلاً می‌گوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقیماندهباقی‌مانده یک است. اگر هزینه کشیدن مثلاً راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه‌ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مسئله مربوط به راه آهن می‌توان وضعیت مربوط به شبکه‌های برق رسانی و لوله کشی نفت و لوله کشی گاز و ایجاد کانالهایکانال‌های آبرسانی را در نظر گرفت. برای تعیین یک شبکه با نازلترین هزینه از قاعده‌ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد. از گرافها می‌توان به عنوان کدهای کمکی نام برد که به DVB Playerها در بالا بردن قابلیت‌های آنهاآن‌ها کمک می‌کنند. گراف‌ها دارایی مزایای مختلفی هستند که شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلی‌ترین مزایای آنهاآن‌ها بشماربه‌شمار می‌رود.