گراف (ریاضی)

نمایشی از یک گراف برچسبدار ۶ راسی با ۷ یال
واژه گراف در ریاضیات حداقل دارای دو معنی می‌باشد. در ریاضیات ابتدایی گراف به نمودار تابع اشاره دارد و در اصطلاح ریاضی‌دانان گراف مجموعه‌ای از نقاط و خطوط متصل به هم هستند.
در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضای آن به طریقی به هم مرتبط هستند. اعضای این مجموعه می‌توانند انسان باشند و ارتباط آن‌ها با هم دست دادن باشد. اعضا می‌توانند اتم‌ها در یک مولکول باشند و ارتباط آن‌ها اتصال‌های شیمیایی باشد یا اعضا می‌توانند قسمت‌های مختلف زمین و ارتباط بین آن‌ها پل‌هایی باشد که آن‌ها را به هم مرتبط می‌کند (همانند مسئله کونیگسبرگ).
نظریه گراف یکی از موضوع‌های مهم در ریاضیات گسسته است که به مطالعه گراف‌ها و مدل‌بندی مسائل به وسیله آن‌ها می‌پردازد. لئونارد اویلر در سال ۱۷۳۶ با حل مسئله پل‌های کونیگسبرگ نظریه گراف‌ها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ از واژه گراف برای نامیدن این مدل‌های ریاضی استفاده کرد.
تعریف
یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام راس تشکیل شده، که آن را با نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که راس‌ها را به هم وصل می‌کنند و با نمایش می‌دهیم. یک چنین گرافی را با نشان می‌دهیم. اگر یال دو راس و را به هم وصل کند می‌نویسیم .
اندازه گراف
اندازه گراف تعداد یال‌های یک گراف است و به صورت بیان می‌شود.
درجه راس‌ها
در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه راس‌های یک گراف با دو برابر تعداد یال‌های ان گراف برابر است.
انواع گراف
گراف همبند گرافی است که بین همه راسهای آن مسیری وجود داشته باشد.
گراف هی وود(Heawood Graph)
گراف کنزر(Kneser)
گراف کامل
گراف کامل ۵ راسی
در نظریه گراف، یک گراف کامل، گرافی‌است که بین هر دو راس آن دقیقا یک یال وجود داشته باشد.
یک گراف کامل از مرتبه n، دارای n راس و یال است که آن را با نشان می‌دهند. یک گراف کامل یک گراف منتظم از درجه n-۱ است.
گراف‌های کاملی که p≥۳ قطعا همیلتونی هستند.
گراف‌های کاملی که p≥۳ و p فرد باشد (p=2k+۱) اویلری هستند، چون درجه هر راس زوج است.
گراف پترسن
گراف پترسن گرافی با ۱۰ راس و ۳- منتظم است.
گراف دو بخشی(Bipartite Graph)
گرافی است که بتوان رئوس آن را به گونه‌ای به دو مجموعه u و v تقسیم کرد که گراف‌های هر زیرگروه (v یا u)دو به دو با هم همسایه نبوده اما با حداقل یکی از رئوس مجموعه دیگر همسایگی داشته باشند.
گراف دو بخشی کامل (Complete Bipartite Graph)
نمایی از گراف‌های دو بخشی کامل
گراف دو بخشی کامل گرافی است که رئوس هر کدام از مجموعه‌های v یا u دو به دو با رئوس مجموعه دیگر همسایه باشند. اگر حتی یکی از رئوس با همه اعضای مجموعه مقابل همسایه نباشد گراف دو بخشی کامل نیست.
مفهوم شهودی
مثالی از یک گراف دو بخشی
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می‌باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده‌اند. حال این سوال مطرح می‌شود که آیا می‌توان به هر متقاضی شغلی متناسب او اختصاص داد؟
برای حل چنین مسئله‌ای که به مسئله تخصیص موسوم است، با استفاده از گراف می‌توان وضعیت‌های خاص را پیاده‌سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه‌ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه‌ای به نام Y قرار می‌دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال‌ها وصل می‌نماید.
به عبارت دیگر گراف بوجود آمده دارای یالهای xy است که هر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل می‌نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متقاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمی‌باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می‌گویند.
تعریف
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه‌ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می‌نامند.
یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آن‌ها برابر مجموعه A باشد؛ و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: X Y = V و X Y =
مثال
به عنوان مثال گراف زیر یک گراف دو بخشی است:
گراف ساده
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را راسهای G و اعضای E را یالهای G می‌نامیم. به بیان ساده‌تر بین دو راس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که راس را به خودش وصل می‌کند) نیز وجود نداشته باشد.
گراف همیلتونی
گراف ساده G از مرتبه V هرگاه دوری به طول V در آن یافت شود.
گراف چرخ
هر گراف G که دارای n راس باشد کهn≥۴ و یکی از رئوس از درجه n-۱ و بقیه از درجه سه باشند، را یک گراف چرخ می‌نامیم- مانند مثال‌های زیر:
گراف چرخn راسی را با n W نمایش می‌دهیم.
گراف چندگانه
گراف چندگانه: هرگاه بین دو راس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.
گراف مکعبی
یک گراف «k مکعب» (k-Cube) گرافی است که رئوس آنk تایی از «صفر» و «یک» هستند که دو راس آن به یکدیگر متصل هستند اگر و فقط اگر دو راسشان دقیقا در یک مولفه با یکدیگر تفاوت داشته باشند.
به‌عبارت دیگر اگر kعددی طبیعی باشد منظور از «kمکعب» گرافی است که راس‌های آن همه دنباله‌های رقمی از «صفر» و «یک» هستند و دو راس در این گراف مجاور بوده هرگاه دنباله‌های متناظرشان دقیقا در یک مولفه اختلاف داشته باشند (شکل ۱).
می‌توان نشان داد که یک گراف «k مکعب» (k-Cube) دارای ویژگی‌هایی نظیر ذیل است:
تعداد رووس =۲ k
تعداد یال‌ها=k*۲ (k-1)
گرافی «دوبخشی» (Bipartite) است.
گراف جهت دار
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعه تمام زوج مرتب‌های متشکل از اعضای V است.
گراف جهت‌دار و کاربردهای آن
گراف جهت دارو کاربردهای آن گراف جهت دار 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 نامیده می‌شود.
گراف مسطح
گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند.
به این گراف هامنی نیز گفته می‌شود.
در بین گراف‌های کامل فقط گراف‌هایی با تعداد راس مساوی یا کمتر از 5 (p≤۵) را، می‌توان به صورت مسطح رسم کرد.
گراف وزن دار
گراف وزن دار: در یک گراف وزن دار، به هر یال یک وزن (عدد) نسبت داده می‌شود. معمولا اعداد حقیقی به عنوان وزن یال‌ها استفاده می‌شوند. اما بسیاری از الگوریتم‌های پر کاربرد فقط برای گراف‌هایی که دارای وزن صحیح یا مثبت هستند طراحی شده‌اند.
گراف‌های تماس تلفنی
می‌توان از گراف‌های تماس تلفنی رای مدل کردن تماس‌های تلنفی برقرار شده در یک شبکه مانند شکبه تلفن راه دور استفاده کرد؛ که در ان راس‌ها شماره تلفن‌ها و یال‌ها ارتباط‌های برقرار شده بین شماره تلفن‌ها است
گراف همپوشانی منابع غذایی در بوم‌شناسی
گراف همپوشانی منابع غذایی در بوم شناسی یکی از کاربردهای گراف در رشته‌های دیگر مانند زیست‌شناسی است، در این گراف منابع غذایی یک اکوسیستم مدل می‌شوند و آگاهی مناسبی از رقابت‌های میان هر گونه اراعه می‌دهند
گراف‌های روابط آشنایی
گراف روابط آشنایی : از این مدل گراف می‌توانیم برای نمایش روابط متعدد بین افراد استفاده کنیم.
برای مثال، می‌توانیم از یک گراف ساده برای نمایش این که آیا دو نفر همدیگر را می‌شناسنند، یعنی آیا آشنا هستند، استفاده کنیم.
گراف‌های همکاری
گراف‌های همکاری برا مدل کردن همکاری نویسندگان در نوشتن مقالات علمی، می‌توان از یک گراف همکاری استفاده کرد. در یک گراف همکاری، رئوس، افراد (شاید محدود به اعضای یک انجمن دانشگاهی خاص) را نمایش می‌دهند و یال‌ها در صورتی دو نفر را بهم وصل می‌کند که آن دو نفر، مقاله‌ای را به‌طور مشترک نوشته باشند.
گراف نقشه راه‌ها
گراف نقشه راه‌ها از گراف‌ها می‌توان برای مدل کردن نقشه راه‌ها استفاده کرد. در این گونه مدل‌ها، رئوس، نمایش دهنده تقاطع‌ها و یال‌ها، نمایش دهنده جاده‌ها هستند. یال‌های بدون جهت، جاده‌های دو طرفه و یال‌های جهت دار، جاده‌های یک طرفه را نشان می‌دهند.
گراف تقدم و پردازش هم‌زمان
با اجرای هم‌زمان جملات مشخص یک برنامه کامپیوتری، می‌توان آن برنامه را سریع‌تر اجرا کرد. مهم است که جمله‌ای که نتایج جملاتی که هنوز اجرا نشده‌اند، نیاز دارد، اجرا نشود. وابستگی جملات به جملات پیشین را می‌توان با یک گراف جهت دار نمایش داد. هر جمله با یک راس نمایش داده می‌شود و در صورتی یالی بین یک راس و راس دوم در نظر گرفته می‌شود که جمله نشان داده می‌شود با راس دوم نتواند قبل از اجرای جمله نشان داده شده‌است با راس اول اجرا شود. این گراف یک گراف تقدم نامیده می‌شود.
مثال
در شکل زیر یک برنامه کامپیوتری و گراف ان نشان داده شده‌است. برای مثال این گراف نشان می‌دهد که جمله S_5 نمی‌تواند قبل از جملات S_2 , S_3 و S_1 اجرا شود.
خصوصیات گراف‌های خاص
اگر درجه همه راس‌ها در گراف ساده با هم برابر و برابر بزرگترین درجه ممکن (یعنی p-۱) باشد، گراف مورد نظر منتظم کامل است. در این گونه گراف‌ها، رابطه میان راس‌ها و یال‌ها چنین است:
که در آن تعداد راسها، و تعداد یالها است.
اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطه بعدی نرسد) می‌گویند گراف درختی است. در این‌گونه گراف‌ها فرمول زیر صدق می‌کند (شرط لازم):
که در آن تعداد راس‌ها، و تعداد یال‌ها است.
گراف اویلری و همیلتونی:گاهی اوقات ما می‌خواهیم در یک گراف حرکت کنیم. به اینصورت که از راسی به راسی دیگر برویم. در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم (مشابه مسئله فروشنده دوره گرد). این مسئله در صرفه جویی زمان و هزینه هم مهم است. (یعنی مبحث بهینه‌سازی ). دراینجا دو موضوع گرافهای اویلری (دور زدن در گراف بدون یال تکراری) و همیلتونی (دور زدن بدون راس تکراری) مطرح می‌شود. براحتی می‌توان بررسی کرد که راسهای گراف اویلری باید درجه زوج داشته باشند. اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده‌است.
گراف‌های کاربردی
گراف بازه‌ها
کاربردها
از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل می‌کنیم و در صورتی‌که در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم.
از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و… استفاده می‌شود. مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. در این جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.
کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد.
درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاه‌های معادلات خطی مربوط به شبکه‌های الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد وقتی مثلا می‌گوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقی‌مانده یک است. اگر هزینه کشیدن مثلا راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه‌ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مسئله مربوط به راه آهن می‌توان وضعیت مربوط به شبکه‌های برق‌رسانی و لوله کشی نفت و لوله کشی گاز و ایجاد کانال‌های آبرسانی را در نظر گرفت. برای تعیین یک شبکه با نازلترین هزینه از قاعده‌ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد. از گرافها می‌توان به عنوان کدهای کمکی نام برد که به DVB Playerها در بالا بردن قابلیت‌های آن‌ها کمک می‌کنند. گراف‌ها دارایی مزایای مختلفی هستند که شفاف‌تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلی‌ترین مزایای آن‌ها به‌شمار می‌رود.
نظریه گراف
یکریختی گراف