کنکور کامپیوتر

نظریه گراف (Graph Theory)

هدف این مقاله ارائه یک مقدمه جامع در رابطه با نظریه گراف است و سعی داریم نشان دهیم که دانستن برخی از مبانی نظریه گراف تا چه میزان می­‌تواند مفید و موثر باشد.

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

تاریخچه نظریه گراف

تئوری گراف برای اولین بار، در سال 1735 میلادی (قرن هجدهم) توسط آقای لئونارد اویلر، ریاضیدان سوئیسی ، یکی از برجسته­‌ترین ریاضیدانان قرن هجدهم (یا شاید بهتر است بگوییم تمام دوران!) در رابطه با حل مسئله معروف پل کوئینزبرگ معرفی شد.

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

" شهر کونیگسبرگ در پروس (کالینینگراد کنوی در روسیه) به دلیل عبور رودخانه پرگل (Pregolya) به دو قسمت تقسیم شده بود و دو جزیره بزرگ  نیز در میان رودخانه قرار داشت، که این چهار بخش از طریق هفت پل به یکدیگر متصل بودند."

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

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

در نظریه گراف دور اویلری یا مدار اویلری (Eulerian circuit)  به مسیری گفته می‌شود که از یک رأس شروع شود و از تمامی یال‌ها یکبار (و فقط یکبار) بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یال‌ها عبور کند ولی به جای اولش بازنگردد به آن مسیر اویلری (Eulerian path) می‌گویند.

معرفی نظریه گراف

واژه گراف در ترجمه تحت الفظی به معنای نمودار است اما با نمودارهای خطی یا میله­‌ای که اغلب ما میشناسیم متفاوت است. گراف­‌ها نوعی از داده ساختارهای غیرخطی هستند و یکی از اصلی ترین ویژگی­‌های آن‌­ها این است که  داده‌­های آن­ها از یک ترتیب خاص پیروی نمی‌­کنند. در واقع تئوری گراف بعنوان یک شبکه با مجموعه‌ای از نقاط و خطوط شناخته می‌شود که در آن اشیاء یا افراد را می‌­توان بعنوان نقاط و ارتباط میان آن­‌ها را خطوط شبکه در نظر گرفت.

تعریف گراف به زبان ریاضی عبارتست از: G=(V,E) که V (Vertices or Nodes) مجموعه­‌ای ناتهی از رئوس و E (Edge) مجموعه یال‌هاست.

معرفی نودها و یال‌ها در گراف

طوقه:  اگر از یک رأس به خودش یال وجود داشته باشد، طوقه می­‌نامند.

یال چندگانه: اگر بین دو رأس چندین یال وجود داشته باشد، یال چندگانه گویند.

درجه یک رأس: تعداد یال‌های متصل به یک رأس را درجه آن رأس می‌­نامیم. به دلایلی، طوقه را دو بار در درجه حساب می‌کنیم. اگر خود راس را با V نمایش دهیم درجه آن را با dV نمایش می‌دهیم. تعداد یال­‌های متصل به یک رأس را درجه آن رأس می­‌نامیم.

مجاورت:

  • در یک گراف دو رأس را مجاور گویند، اگر یک یال بین آن­‌ها وجود داشته باشد.
  • در یک گراف دو یال را مجاور گویند، اگر یک رأس مشترک بین آن­‌ها وجود داشته باشد.

تفاوت گراف با درخت

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

هر درخت فقط می‌­تواند در یک جهت جریان داشته باشد، از گره ریشه به گره­‌های برگ یا گره­‌های فرزند، همچنین یک درخت می‌تواند فقط اتصالات یک طرفه داشته باشد، یعنی یک گره فرزند فقط می‌تواند یک والد داشته باشد؛ درنهایت درخت نمی‌تواند هیچ حلقه یا دوری داشته باشد.

درخت­‌ها دارای یک ساختار سلسله مراتبی هستند زیرا می‌توان آن‌ها را در سطوح مختلف بازآرایی کرد که در نهایت منجر به ایجاد یک سلسله مراتب می‌شود.

graph vs tree

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

انواع گراف

همانطور که در بخش قبل گفته شد، هیچ قانون واقعی برای اتصال یک گره به گره دیگر در یک گراف وجود ندارد. یال­‌ها (گاهی اوقات به آن‌ها پیوند گفته می‌شود) می­‌توانند گره­‌ها را به هر طریق ممکن به هم متصل کنند.

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

گراف بدون جهت (Undirected Graph)

همانطور که از نام آن مشخص است، هیچ جهتی بین دو نود یا رأس در این نوع از گراف وجود ندارد. بنابراین یال متصل از گره 1 به 2 با یال خروجی از گره 2 به گره 1 یکسان است.

گراف بدون جهت

گراف جهت دار (Directed Graphs or DiGraphs)

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

گراف بدون جهت

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

مثالی از گراف جهت‌دار

کاربردهای گراف

 گراف­‌ها در اطراف ما هستند اما همیشه آن‌ها را آن طور که هستند نمی‌بینیم. شما در حال حاضر با خواندن این مقاله، به معنای واقعی کلمه روی یک گراف قرار گرفته­‌اید. وب یک ساختار گراف عظیم است! وقتی بین وب‌سایت‌ها کلیک می‌کنیم و بین URL‌ها به جلو و عقب حرکت می‌کنیم، در واقع در حال حرکت بر روی یک گراف هستیم. گاهی اوقات این گراف­‌ها دارای گره‌هایی با یال‌­های غیرجهت­‌دار هستند و ما می‌توانیم از یک صفحه وب به صفحه‌ی دیگر به عقب و جلو برویم و گاهی دارای صفحاتی جهت‌دار هستند که تنها می‌توان از صفحه وب A به صفحه وب B  رفت و حرکت برعکس آن ممکن نخواهد بود. اما یک مثال بهتری وجود دارد که تعاملات روزانه ما با گراف­‌ها را به زیبایی نشان می‌­دهد: شبکه‌های اجتماعی.

فیس‌بوک بعنوان یک شبکه اجتماعی عظیم، نوعی گراف است. و اگر بیشتر در مورد عملکرد واقعی آن فکر کنیم، بهتر متوجه می‌شویم که دقیقاً چه نوع گرافی است. در فیس‌بوک، اگر شخصی شما را به عنوان دوست اضافه کند، باید درخواست او را بپذیرید و امکان ندارد که این تعامل بصورت یک طرفه صورت پذیرد. بنابراین رابطه بین دو کاربر (گره‌ها یا رئوس در قالب گراف!) دو طرفه است و هیچ مفهومی از گره "مبدا" و "مقصد" وجود ندارد.

آیا می توانید حدس بزنید که فیس‌بوک با چه نوع نموداری پیاده سازی شده است؟ بله کاملاً درست است ، گراف بدون جهت!

نمونه ای دیگر از گراف جهت دار با برچسب

از طرف دیگر توییتر با فیس‌بوک بسیار متفاوت عمل می‌کند. شما می‌توانید فردی را دنبال کنید، اما او ممکن است شما را دنبال نکند. بعنوان مثال، شما ممکن است یک بازیگر یا سیاستمدار و یا هر فرد معروف دیگری را دنبال کنید، اما او قطعاً شما را دنبال نمی‌کند (متاسفانه!). بنابراین ما می­‌توانیم توییتر را به‌عنوان یک گراف جهت‌دار نمایش دهیم. هر یالی که ایجاد می‌­کنیم نشان دهنده یک رابطه یک طرفه است. وقتی فردی را در توییتر دنبال می‌کنید، یک یال در گراف با حساب خود به عنوان گره مبدا و حساب فرد مقابل به عنوان گره مقصد ایجاد می­‌کنید.

ارتباط افراد در فضای مجازی یک گراف جهت‌دار است.

 

الگوریتم­ های معروف گراف

الگوریتم A*  (A-Star)

 *A یک الگوریتم جستجوی آگاهانه (Informed Search) یا بهترین جستجوی اول است که بر اساس گراف­‌های وزنی طراحی شده و با شروع از یک گره خاص و حرکت به سمت گره هدف معین، کوتاه‌ترین مسیر طی شده در کمترین زمان را در گراف می­‌یابد. این الگوریتم از یک مفهوم به نام تابع اکتشافی (Heuristic Function) برای یافتن یک هدف خاص با کوتاه‌­ترین مسیر بهره می‌­برد. در هر تکرار از حلقه اصلی خود، *A باید تعیین کند که کدام یک از مسیرهای خود را گسترش دهد و این کار را بر اساس هزینه مسیر و برآورد یا تخمین هزینه مورد نیاز (هیورستیک) برای رسیدن به هدف انجام می‌دهد. به طور خاص،*A  مسیری را انتخاب می‌کند که حداقل باشد. الگوریتم *A بااینکه یکی از بهترین الگوریتم­‌های مسیریابی است اما همیشه کوتاه‌ترین مسیر را ایجاد نمی­‌کند، زیرا به‌ شدت به تابع اکتشافی وابسته است.

الگوریتمی برای یافتن بهینه ترین مسیر بهینه از یک نود تا نود هدف

الگوریتم جستجوی عمق اول (DFS: Depth First Search)

الگوریتم جستجوی عمق اول برای پیمایش یا جستجو در ساختارهای داده درختی یا گرافی است. همانطور که در فصل گراف درس طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. می‌خوانیم، این الگوریتم از گره ریشه شروع می‌شود (انتخاب گره دلخواه به عنوان گره ریشه در مورد یک گراف) و تا آنجا که ممکن است در امتداد هر شاخه قبل از عقب‌نشینی کاوش می‌کند. یک جستجوی عمقی که از گره A شروع می‌شود، با فرض اینکه یال‌های چپ در نمودار نشان‌ داده‌ شده، قبل از یال‌های راست انتخاب شده‌اند و الگوریتم جستجو، گره‌های بازدید شده قبلی را به خاطر می‌آورد و آن‌ها را تکرار نمی‌کند، بازدید خواهد شد. گره‌ها به ترتیب زیر هستند: A,B,D,F,E,C,G. انجام همان جستجو بدون به‌خاطر سپردن گره‌های بازدید شده قبلی منجر به بازدید از گره‌ها به ترتیب ...,A,B,D,F,E,A,B,D,F,E برای همیشه می‌شود که در A,B,D، گرفتار می‌شوند. چرخه F وE هرگز به C یا G نمی‌رسد. یکی از مزیت‌های جستجوی عمق اول در ساختار گراف، اجتناب از حلقه بی‌نهایت است و به همه گره‌ها می‌رسد.

بهترین الگوریتم از نظر مرتبه حافظه و در عین حال غیربهینه برای یافتن پاسخ

الگوریتم جستجوی سطح اول (BFS: Breadth-first search)

الگوریتم جستجوی سطح اول، از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعیهوش مصنوعی (AI) چیست؟ انواع، کاربردها، مزایا و معایبهوش مصنوعی (AI) چیست؟ انواع، کاربردها، مزایا و معایبهوش مصنوعی یا Artificial Intelligence یا به اختصار AI، امروزه کاربردهای بسیاری پیدا کرده و به یکی از داغ‌ترین حوزه‌های بشر تبدیل شده است، اما با این وجود بسیاری از افراد با کاربردهای آن آشنایی کامل ندارند، به همین علت در این صفحه کاربردها، مزایا و معایب AI بطور کامل بررسی شده است کاربرد دارد. در یک گراف، پیمایش می‌تواند از هر گره‌­ای شروع شود و تمام گره‌ها را از نظر سطح پوشش دهد. الگوریتم BFS از ساختار داده صف برای پیاده‌سازی استفاده می‌­کند. در BFS، ما همیشه به حالت هدف نهایی می‌رسیم در حالی‌که همیشه برای الگوریتم DFS صدق نمی‌کند. الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌­کند:

  1. عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف می­‌کند.
  2. گره جاری را پردازش می‌کند.
  3. گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند را به این صف اضافه می‌­کند.

بهترین الگوریتم برای پیدا کردن کوتاه‌ترین مسیر در گراف‌های بدون وزن

جمع‌بندی

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی4.25 1 1 1 1 1 1 1 1 1 14.25 امتیاز (6 رای)
بارگذاری نظرات