موضوع مقاله: گراف (ریاضی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف (ریاضی) | مقدمه: در ریاضیات پایه گراف اشاره به نمودار تابع دارد، و در اصطلاح ریاضی‌دانان گراف مجموعه‌ای از نقاط و خطوط به هم پیوسته است. | ## بخش 1: گراف (ریاضی) | در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضایش به گونه‌ای با هم پیوند دارند. اعضای این مجموعه می‌توانند چند انسان باشند و ارتباط میان آن‌ها دست دادن با یکدیگر باشد. اعضا می‌توانند اتم‌ها در یک مولکول باشند و ارتباطشان پیوندهای شیمیایی باشد یا این که اعضا می‌توانند بخش‌های گوناگون یک زمین و ارتباط میانشان، پل‌هایی باشد که آن‌ها را به هم می‌پیوندند (همانند مسئله کونیگسبرگ). نظریه گراف یکی از موضوع‌های مهم در ریاضیات گسسته است که به شناخت گراف‌ها و مدل‌بندی مسایل با آن‌ها می‌پردازد. لئونارد اویلر در سال ۱۷۳۶ با حل مسئله پل‌های کونیگسبرگ نظریهٔ گراف‌ها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ این مدل‌های ریاضی را گراف نامید. تعریف گراف ساده: یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با نمایش می‌دهیم. گراف جهت دار G زوج مرتب (V,E) است که V مجموعه‌ای ناتهی و اعضای E زوجهای مرتب از اعضای V هستند. به این صورت که به ازای هر راس 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) نمایش می‌دهیم. گراف K ـ منتظم: گرافی را که درجهٔ تمام رئوس آن با هم مساوی و برابر با عدد k باشند، گراف k - منتظم می‌نامیم. رأس تنها: به رأسی که درجهٔ آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها (یا ایزوله) می‌گوییم. گراف تهی: گرافی را که تمام رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد، گراف تهی می‌نامیم؛ بنابراین منظور از گراف تهیِ n رأسی، گرافی شامل n رأسِ تنها و بدون یال است. دو رأس مجاور (همسایه): دو رأس u و v را دو رأسِ همسایه یا مجاور گوییم هرگاه توسط یالی به هم وصل شده باشند، یعنیuv ∈ E(G). مجموعهٔ همسایه‌های یک رأس: فرض کنیم v ∈ V(G)، به مجموعهٔ رأس‌هایی از گراف G که به رأس v متصل هستند، "همسایگی باز رأسv " می‌گوییم و با NG(v) نمایش می‌دهیم. اضافه کردنِ خودِ رأسِ v به NG(v) "همسایگی بستهٔ رأسv " را به دست می‌دهد که آن را با NG[v] نمایش می‌دهیم. بزرگ‌ترین و کوچک‌ترین درجهٔ یک گراف: بزرگ‌ترین عدد در بین درجات رئوس گراف G را با∆ (G) و کوچک ترینِ آنها را با δ (G) نمایش می‌دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می‌نامیم. زیرگراف: یک زیرگراف از گراف G گرافی است که مجموعهٔ رئوس آن زیرمجموعه ای از مجموعهٔ رئوس گراف G، و مجموعهٔ یال‌های آن زیرمجموعه ای از مجموعهٔ یال‌های G باشد. مکمل یک گراف: مکمل گرافی مانند G که آن را با G^c یا G ̅ نمایش می‌دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از G^cیک یال است اگر و تنها اگر بین همان دو رأس درG یالی وجود نداشته باشد. گراف کامل: گرافی را که هر رأس آن با تمام رئوسِ دیگرِ، مجاور باشد گراف کامل می‌نامیم. مسیر: اگر u و v دو رأس از گراف G باشند، یک مسیر از u به v (یک v ــ u مسیر) در G دنباله ای از رئوس دوبه دو متمایز در G است که از u شروع و به v ختم می‌شود به طوری که هر دو رأس متوالی این دنباله در G مجاور هم باشند. طول یک مسیر برابر است با تعداد یال‌های موجود در آن مسیر (یکی کمتر از تعداد رئوس موجود در آن مسیر). قرارداد می‌کنیم که دنبالهٔ متشکل از تنها یک رأسِv، یک مسیر است با طول صفر از رأس v به خودش. دور: دنبالهٔ (n ≥ 3) v1 v2 v3 … vn v1 از رئوس دو به دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول n می‌نامیم. (گرافی را که تنها از یک دورِ n رأسی تشکیل شده باشد را با Cn نمایش می‌دهیم) همبندی و ناهمبندی یک گراف: گراف G را همبند می‌نامیم هرگاه بین هر دو رأسِ آن حداقل یک مسیر وجود داشته باشد، در غیر این صورت آن را ناهمبند می‌نامیم. درجه رأس‌ها در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. | ## بخش 2: گراف (ریاضی) | به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه رأس‌های یک گراف با دو برابر تعداد یال‌های ان گراف برابر است. گونه‌های گراف گراف همبند گرافی است که بین همهٔ راس‌های آن مسیری وجود داشته باشد. ¬¬¬ کِیلی در سال ۱۸۵۷ میلادی درخت‌ها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربن‌ها کشف کرد. وقتی مثلاً می‌گوییم دو ایزومر مختلف C4H10 وجود دارند منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجهٔ ۴ راس از این ۱۴ راس چهار و درجهٔ هریک از ۱۰ راس باقی‌مانده یک است. گراف‌های کاملی که p≥۳ و p فرد باشد (p=2k+۱) اویلری هستند، چون درجهٔ هر راس زوج است. اگر حتی یکی از رئوس با همهٔ اعضای مجموعهٔ مقابل همسایه نباشد گراف دو بخشی کامل نیست. برای حل چنین مسئله‌ای که به مسئلهٔ تخصیص موسوم است، با استفاده از گراف می‌توان وضعیت‌های خاص را پیاده‌سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه‌ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه‌ای به نام Y قرار می‌دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال‌ها وصل می‌نماید. به عبارت دیگر گراف به وجود آمده دارای یال‌های xy است که هر متقاضی x را از مجموعه X به شغل‌های مناسب y از مجموعه Y متصل می‌نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متقاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمی‌باشند. تعریف گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه‌ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آن‌ها برابر مجموعه A باشد؛ و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: XY = V و XY = مثال به عنوان مثال گراف زیر یک گراف دو بخشی است: گراف ساده گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. به بیان ساده‌تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که رأس را به خودش وصل می‌کند) نیز وجود نداشته باشد. گراف چرخ هر گراف G که دارای n راس باشد کهn≥۴ و یکی از رئوس از درجهٔ n-۱ و بقیه از درجهٔ سه باشند، را یک گراف چرخ می‌نامیم- مانند مثال‌های زیر: گراف چرخn راسی را با nW نمایش می‌دهیم. گراف چندگانه گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم. گراف مکعبی یک گراف «k مکعب» (k-Cube) گرافی است که رئوس آنk تایی از «صفر» و «یک» هستند که دو رأس آن به یکدیگر متصل هستند اگر و فقط اگر دو رأسشان دقیقاً در یک مؤلفه با یکدیگر تفاوت داشته باشند. به‌عبارت دیگر اگر kعددی طبیعی باشد منظور از «kمکعب» گرافی است که رأس‌های آن همهٔ دنباله‌های رقمی از «صفر» و «یک» هستند و دو رأس در این گراف مجاور بوده هرگاه دنباله‌های متناظرشان دقیقاً در یک مؤلفه اختلاف داشته باشند (شکل ۱). گراف جهت دار گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است. گراف جهت‌دار و کاربردهای آن گراف جهت دارو کاربردهای آنگراف جهت دار D، یک سه تایی مرتب(O(D) و A(D) و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راس‌ها ویک مجموعه (D) A مجزای از V(D)از کمان‌ها و یک تابع وقوع O(D)که به هر کمان D یک زوج مرتب از راس‌های D- که الزاماً متمایز نیستند- را نسبت می‌دهد. گراف مسطح گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در رأس‌ها قطع کنند. در بین گراف‌های کامل فقط گراف‌هایی با تعداد راس مساوی یا کمتر از 5 (p≤۵) را، می‌توان به صورت مسطح رسم کرد. گراف وزن‌دار گراف وزن‌دار: در یک گراف وزن دار، به هر یال یک‌وزن (عدد) نسبت داده می‌شود. اما بسیاری از الگوریتم‌های پر کاربرد فقط برای گراف‌هایی که دارای وزن صحیح یا مثبت هستند طراحی شده‌اند. گراف‌های تماس تلفنی می‌توان از گراف‌های تماس تلفنی رأی مدل کردن تماس‌های تلفنی برقرار شده در یک شبکه مانند شبکه تلفن راه دور استفاده کرد؛ که در ان رأس‌ها شماره تلفن‌ها و یال‌ها ارتباط‌های برقرار شده بین شماره تلفن‌ها است. برای مثال، می‌توانیم از یک گراف ساده برای نمایش این که آیا دو نفر همدیگر را می‌شناسند، یعنی آیا آشنا هستند، استفاده کنیم. گراف‌های همکاری گراف‌های همکاری برا مدل کردن همکاری نویسندگان در نوشتن مقالات علمی، می‌توان از یک گراف همکاری استفاده کرد. در یک گراف همکاری، رئوس، افراد (شاید محدود به اعضای یک انجمن دانشگاهی خاص) را نمایش می‌دهند و یال‌ها در صورتی دو نفر را بهم وصل می‌کند که آن دو نفر، مقاله‌ای را به‌طور مشترک نوشته باشند. | ## بخش 3: گراف (ریاضی) | گراف نقشه راه‌ها گراف نقشه راه‌ها از گراف‌ها می‌توان برای مدل کردن نقشه راه‌ها استفاده کرد. در این گونه مدل‌ها، رئوس، نمایش دهنده تقاطع‌ها و یال‌ها، نمایش دهنده جاده‌ها هستند. یال‌های بدون جهت، جاده‌های دو طرفه و یال‌های جهت دار، جاده‌های یک طرفه را نشان می‌دهند. گراف تقدم و پردازش هم‌زمان با اجرای هم‌زمان جملات مشخص یک برنامه کامپیوتری، می‌توان آن برنامه را سریع تر اجرا کرد. هر جمله با یک راس نمایش داده می‌شود و در صورتی یالی بین یک راس و راس دوم در نظر گرفته می‌شود که جمله نشان داده می‌شود با راس دوم نتواند قبل از اجرای جمله نشان داده شده است با راس اول اجرا شود. برای مثال این گراف نشان می‌دهد که جمله S_5 نمی‌تواند قبل از جملات S_2 , S_3 و S_1 اجرا شود. ویژگی‌های گراف‌های ویژه اگر درجهٔ همهٔ رأس‌ها در گراف ساده با هم برابر و برابر بزرگ‌ترین درجهٔ ممکن (یعنی p-۱) باشد، گراف مورد نظر منتظم کامل است. در این گونه گراف‌ها، رابطهٔ میان رأس‌ها و یال‌ها چنین است: که در آن تعداد راسها، و تعداد یالها است. اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطهٔ بعدی نرسد) می‌گویند گراف درختی است. در این‌گونه گراف‌ها فرمول زیر صدق می‌کند (شرط لازم): که در آن تعداد رأس‌ها، و تعداد یال‌ها است.کتاب ریاضیات گسسته پیش دانشگاهی رشته ریاضی فصل اول گراف اویلری و همیلتونی:گاهی ما می‌خواهیم در یک گراف حرکت کنیم. در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم (مشابه مسئلهٔ فروشندهٔ دوره‌گرد). دراینجا دو موضوع گراف‌های اویلری (دور زدن در گراف بدون یال تکراری) و همیلتونی (دور زدن بدون راس تکراری) مطرح می‌شود. اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده است. گراف‌های کاربردی گراف بازه‌ها کاربردها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل می‌کنیم و در صورتی‌که در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم. از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و… استفاده می‌شود. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتم‌های مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. در این‌جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل رأس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود. کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاه‌های معادلات خطی مربوط به شبکه‌های الکتریکی درخت‌ها را کشف و نظریه درخت‌ها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درخت‌ها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربن‌ها کشف کرد وقتی مثلاً می‌گوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقی‌مانده یک است. اگر هزینه کشیدن مثلاً راه‌آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه‌ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مسئله مربوط به راه‌آهن می‌توان وضعیت مربوط به شبکه‌های برق‌رسانی و لوله‌کشی نفت و لوله‌کشی گاز و ایجاد کانال‌های آبرسانی را در نظر گرفت. برای تعیین یک شبکه با نازلترین هزینه از قاعده‌ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد. | ## جمع‌بندی | گراف‌ها دارایی مزایای مختلفی هستند که شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلی‌ترین مزایای آن‌ها به‌شمار می‌رود.