گراف (ریاضی)

گراف ساده: یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با ${\displaystyle V}$ نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با ${\displaystyle E}$ نمایش می‌دهیم. یک چنین گرافی را با ${\displaystyle G=(V,E)}$ نشان می‌دهیم. اگر یال ${\displaystyle y}$ دو رأس ${\displaystyle v_{1}}$ و ${\displaystyle v_{2}}$ را به هم وصل کند می‌نویسیم ${\displaystyle y=\lbrace v_{1},v_{2}\rbrace }$.[3]

گراف جهت‌دار: منظور از گراف جهت دار گرافی است که یال‌ها در آن دارای جهت هستند. گراف جهت دار G زوج مرتب (V,E) است که V مجموعه‌ای ناتهی و اعضای E زوجهای مرتب از اعضای V هستند. همانند گرافهای ساده، به اعضایV، راسهای G و به اعضای E، یال‌های G می‌گوییم. همچنین به هر گراف جهت‌دار نموداری در صفحه نسبت می‌دهیم. به این صورت که به ازای هر راس G نقطه‌ای در صفحه در نظر می‌گیریم و به ازای هر یال مانند (u,v) کمانی بین u و v رسم می‌کنیم و روی این کمان فلشی از u به v می‌گذاریم.

گراف مخلوط: گرافی است که در آن ممکن است برخی یال‌ها جهت داشته باشند و برخی بدون جهت باشند. گراف مخلوط G، سه‌تایی مرتب G = (V, E, A) است که در آن V مجموعه‌ی رئوس، E یال‌های بدون جهت و A یال‌های جهت دارمی‌باشند. گراف ساده و گراف جهت‌دار حالت خاصی از گراف جهت دار می باشند.

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

قرارداد‌ها:

مرتبه و اندازۀ یک گراف: تعداد رأس های گراف G یعنی |V(G)| را مرتبهٔ آن گراف می گوییم و باp(G) نمایش می دهیم و تعداد یال های گراف یعنی |E(G)| را اندازهٔ گراف G می گوییم و با q(G) نمایش می دهیم. معمولاً برای راحتی کار به جای p(G) از p و به جای q(G) از q استفاده می کنیم.

درجۀ یک رأس: درجهٔ رأس v در گراف G برابر است با تعداد یال هایی از گراف G که به رأس v متصل اند و آن را با degG (v) یا به طور ساده تر با deg (v) یا d (v) نمایش می دهیم. اگر درجهٔ یک رأس فرد باشد آن را رأس فرد و اگر زوج باشد آن را رأس زوج می نامیم.

گراف K ـ منتظم: گرافی را که درجهٔ تمام رئوس آن با هم مساوی و برابر با عدد k باشند ،گراف k - منتظم می نامیم.

رأس تنها: به رأسی که درجهٔ آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها (یا ایزوله) می گوییم.[4]

گراف تهی: گرافی را که تمام رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد ،گراف تهی می نامیم. بنابراین منظور از گراف تهیِ n رأسی، گرافی شامل n رأسِ تنها و بدون یال است.

دو رأس مجاور (همسایه): دو رأس u و v را دو رأسِ همسایه یا مجاور گوییم هرگاه توسط یالی به هم وصل شده باشند، یعنیuv ∈ E(G).

مجموعهٔ همسایه های یک رأس: فرض کنیم v ∈ V(G)، به مجموعهٔ رأس هایی از گراف G که به رأس v متصل هستند، "همسایگی باز رأسv " می گوییم و با NG(v) نمایش می دهیم. اضافه کردنِ خودِ رأسِ v به NG(v) "همسایگی بستهٔ رأسv " را به دست می دهد که آن را با NG[v] نمایش می دهیم. می توان این دو مجموعه را به صورت زیر نمایش داد: NG (v) = {u ∈ V (G )∶ uv ∈ E (G )} NG[v] =NG (v) ∪{v}

دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آنها به آن متصل باشند.

بزرگ ترین و کوچک ترین درجۀ یک گراف: بزرگ ترین عدد در بین درجات رئوس گراف G را با∆ ( G) و کوچک ترینِ آنها را با δ (G) نمایش می دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می نامیم.

زیرگراف: یک زیرگراف از گراف G گرافی است که مجموعهٔ رئوس آن زیرمجموعه ای از مجموعهٔ رئوس گراف G، و مجموعهٔ یال های آن زیرمجموعه ای از مجموعهٔ یال های G باشد.

مکمل یک گراف: مکمل گرافی مانند G که آن را با G^c یا G ̅ نمایش می دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از G^cیک یال است اگر و تنها اگر بین همان دو رأس درG یالی وجود نداشته باشد.

گراف کامل: گرافی را که هر رأس آن با تمام رئوسِ دیگرِ، مجاور باشد گراف کامل می نامیم. گراف کاملِ n رأسی را با Kn نمایش می دهیم. می توان گفت Kn یک گراف n رأسی وn-1 ــ منتظم است.

مسیر: اگر u و v دو رأس از گراف G باشند، یک مسیر از u به v (یک v ــ u مسیر) در G دنباله ای از رئوس دوبه دو متمایز در G است که از u شروع و به v ختم می شود به طوری که هر دو رأس متوالی این دنباله در G مجاور هم باشند. طول یک مسیر برابر است با تعداد یال های موجود در آن مسیر (یکی کمتر از تعداد رئوس موجود در آن مسیر). قرارداد می کنیم که دنبالهٔ متشکل از تنها یک رأسِv، یک مسیر است با طول صفر از رأس v به خودش. ( گرافی را که تنها از یک مسیرِ n رأسی تشکیل شده باشد با Pn نمایش می دهیم) .

دور: دنبالهٔ (n ≥ 3) v1 v2 v3 ... vn v1 از رئوس دو به دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول n می نامیم. (گرافی را که تنها از یک دورِ n رأسی تشکیل شده باشد را با Cn نمایش می دهیم)

همبندی و ناهمبندی یک گراف: گراف G را همبند می نامیم هرگاه بین هر دو رأسِ آن حداقل یک مسیر وجود داشته باشد، در غیر این صورت آن را ناهمبند می نامیم.[5]

اندازه گراف تعداد یال‌های یک گراف است و به صورت ${\displaystyle |E(G)|\,}$ بیان می‌شود.

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

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

درخت: گراف هم‌بندى را که هیچ دوری نداشته باشد درخت مى‌نامیم نامیم. گراف‌های K1 و K2 درخت اند و به ترتیب "تنها" درخت‌های با یک و دو راس هستند. ثابت می‌شود که در هر درخت بین هر دو راس دقیقا یک مسیر وجود دارد. در شکل زیر تمام درخت‌های از مرتبه‌ی 1 تا 5 رسم شده‌اند.

¬¬¬ کِیلی در سال 1857 میلادی درخت‌ها را در ارتباط با شمارش ایزومر‌های مختلف هیدرو‌کربن‌ها کشف کرد. وقتی مثلا می‌گوییم دو ایزومر مختلف C4H10 وجود دارند منظورمان این است که دو درخت متفاوت با 14 راس وجود دارند که درجه‌ی 4 راس از این 14 راس چهار و درجه‌ی هریک از 10 راس باقی‌مانده یک است.[6]

گراف کامل

گراف کامل ۵ رأسی

در نظریه گراف، یک گراف کامل، گرافی‌است که بین هر دو راس آن دقیقاً یک یال وجود داشته باشد. یک گراف کامل از مرتبه n، دارای n راس و ${\displaystyle {\frac {n(n-1)}{2}}}$ یال است که آن را با ${\displaystyle \,k_{n}}$ نشان می‌دهند. یک گراف کامل یک گراف منتظم از درجه n-۱ است.

گراف‌های کاملی که p≥۳ قطعاً همیلتونی هستند.

گراف‌های کاملی که p≥۳ و p فرد باشد (p=2k+۱) اویلری هستند، چون درجهٔ هر راس زوج است.

گراف دو بخشی کامل (Complete Bipartite Graph)

نمایی از گراف‌های دو بخشی کامل

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

مفهوم شهودی

مثالی از یک گراف دو بخشی

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

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

${\displaystyle q=p(p-1)/2\!}$

که در آن ${\displaystyle p\!}$ تعداد راسها، و ${\displaystyle q\!}$ تعداد یالها است.

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

${\displaystyle p=q+1\!}$

که در آن ${\displaystyle p\!}$ تعداد رأس‌ها، و ${\displaystyle q\!}$ تعداد یال‌ها است.[9]

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

گراف بازه‌ها

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

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

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

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

• نظریه گراف

یکریختی گراف

• بابلیان، اسماعیل (۱۳۸۶). مباحثی در ریاضیات گسسته. تهران: مبتکران. شابک ۹۷۸-۹۶۴-۵۹۹۳-۳۲-۸.
• بهزاد، مهدی؛ رجالی، علی؛ عمیدی، علی؛ محمودیان، عبادالله (۱۳۸۵). ریاضیات گسسته. تهران: شرکت چاپ و نشر کتاب‌های درسی ایران. شابک ۹۶۴-۰۵-۰۱۰۳-۴.
• کتاب آشنایی با نظریهٔ گراف نوشتهٔ علیرضا علیپور، انتشارات فاطمی
• گریمالدی، رالف پ. (۱۳۷۹). ریاضیات گسسته و ترکیبیاتی. ۳. ترجمهٔ دکتر محمدعلی رضوانی و دکتر بیژن شمس. تهران: انتشارات فاطمی. شابک ۹۶۴-۳۱۸-۲۵۶-۸.
• وست، داگلاس بی. (۱۳۸۶). آشنایی با نظریهٔ گراف. ترجمهٔ دکتر بیژن شمس. تهران: گسترش علوم پایه. شابک ۹۶۴-۷۸۱۷-۲۶-۶.
• کتاب نظریه گراف‌ها و کاربردهای آن نوشته باندی و مورتی، ترجمه حمید ضرابی زاده، مؤسسه دیباگران تهران
• کتاب ریاضیات گسسته نوشته ر. پ. گریمالدی، مرکز نشر دانشگاهی
• کتاب نظریهٔ الگوریتمی و کاربردی گراف‌ها نوشته گری چارتراند، آرترود اولرمن، ترجمه دکتر سید مهدی تشکری هاشمی، انتشارات دانشگاه امیرکبیر
• Graph Theory Software نرم‌افزارهای گراف تولید شده در دانشگاه صنعتی شریف
• . دنیای ریاضیات http://mathworld.wolfram.com/Graph.html. Retrieved 6 March 2014. Missing or empty |title= (help)

Kenneth H, Rosen (1998). "Number Theory and Cryptography". Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. Check date values in: |بازبینی= (help)