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

گراف همبند گرافی است که بین همهٔ راسهایراس‌های آن مسیری وجود داشته باشد.

به عبارت دیگر گراف بوجود آمده دارای یالهاییال‌های xy است که هر متقاضی x را از مجموعه X به شغلهایشغل‌های مناسب y از مجموعه Y متصل می‌نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متقاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمی‌باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند.

'''گراف ساده:''' هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهایرأس‌های G و اعضای E را یالهاییال‌های G می‌نامیم. به بیان ساده‌تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که رأس را به خودش وصل می‌کند) نیز وجود نداشته باشد.<ref>{{یادکرد کتاب | تاریخ بازبینی=۰۷ مارس ۲۰۱۲ | سال=۱۳۹۰ | عنوان=آشنایی با گراف | ناشر=فاطمی | نام=یاسر | نام خانوادگی=احمدی فولادی | نام خانوادگی ویراستار=سید عبادالله | نام خانوادگی۲=محمودیان}}</ref>

'''[[گراف جهت دارو کاربردهای آن]]'''گراف جهت دار 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 نامیده می‌شود.

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

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

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

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

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

* [[نظریه گراف]]

* کتاب نظریهٔ الگوریتمی و کاربردی گرافهاگراف‌ها نوشته [[گری چارتراند، آرترود اولرمن]]، ترجمه دکتر سید مهدی تشکری هاشمی، [[انتشارات دانشگاه امیرکبیر]]