Graph Theory - PDF
Document Details
Uploaded by Deleted User
Tags
Summary
These notes cover fundamental concepts of graph theory, including graph representations, graph search algorithms (DFS and BFS), spanning trees, and Dijkstra's algorithm. Key terms and ideas used in graph theory are defined and explained in detail. Useful for students in computer science, mathematics, and related fields.
Full Transcript
Graph Graph گراف یک ساختار داده غیر خطی است که از تعدادی راس و یال تشکیل شده است. رئوس گاهی اوقات به عنوان گره نیز شناخته می شوند و یال ها خطوط یا کمانی هستند که هر دو گره را در گراف به ه...
Graph Graph گراف یک ساختار داده غیر خطی است که از تعدادی راس و یال تشکیل شده است. رئوس گاهی اوقات به عنوان گره نیز شناخته می شوند و یال ها خطوط یا کمانی هستند که هر دو گره را در گراف به هم متصل می کنند. به طور رسمی تر ،نمودار از مجموعه ای از رئوس ( )Vو مجموعه ای از یال ها ( )Eتشکیل شده است.گراف با ) G(E, Vنشان داده می شود. از گراف ها برای حل بسیاری از مسائل زندگی واقعی استفاده می شود. از گCراف هCا بCرای نمCایش شCبکه هCا اسCتفاده می شCود.این شCبکه هCا ممکن اسCت شامل مسیرهایی در یک شهر یا شبکه تلفن یا شبکه مدار باشند. گراف هCا همچCنین در شCبکه هCای اجتمCاعی ماننCد لینکCدین ،فیسCبوک اسCتفاده می شCوند.بCه عنCوان مثCال ،در فیس بCوک ،هCر شCخص بCا یCک راس (یCا گCره) نشCان داده می شCود.هCر گCره یCک سCاختار اسCت و حCاوی اطالعCاتی ماننCد شناسCه شCخص ،نCام، جنسیت ،منطقه و غیره است. Types of Graphs گراف های غیر جهت دار ( :)Undirected GraphsگCرافی کCه در آن یCال هCا جهCتی ندارنCد ،یعCنی یCال هCا دارای فلش هCای نشCان دهنCده جهت پیمCایش نیسCتند.مثCال :گCراف شCبکه اجتمCاعی کCه در آن دوسCتی هCا جهت دار نیستند. گراف های جهت دار ( :)Directed GraphsگCرافی کCه در آن یCال هCا دارای جهت هسCتند ،یعCنی یCال هCا دارای فلش هCایی هسCتند کCه جهت پیمCایش را نشCان می دهCد.مثCال :گCراف صCفحه وب کCه در آن پیونCدهای بین صفحات جهت دار هستند. گراف ه ای وزن دار ( :)Weighted GraphsگCرافی کCه در آن یCال هCا دارای وزن یCا هزینCه هCای مرتبCط بCا آنهCا هسCتند.مثCال :گCراف شCبکه جCاده ای کCه در آن وزن هCا می تواننCد فاصCله بین دو شCهر را نشCان دهند. گراف های بدون وزن ( :)Unweighted GraphsگCرافی کCه در آن یCال هCا وزن یCا هزینCه ای مرتبCط با آنها ندارند.مثال :گراف شبکه اجتماعی که در آن لبه ها نشان دهنده دوستی هستند. گراف های کامل ( :)Complete GraphsگCرافی کCه در آن هCر رأس بCه تمCامی رئCوس دیگCر متصCل An undirected graph A directed graph Graph terminology Graph terminology Graph terminology Graph terminology Graph Representation دو روش زیر متداول ترین شیوه های نمایش گراف به شمار می روند. ماتریس مجاورت ()Adjacency Matrix ماتریس مجCاورت یCک آرایCه دو بعCدی بCه انCدازه V x VاسCت که VتعCداد رئCوس گCراف است. آرایCه دو بعCدی ][][adjرا در نظCر بگیریCد ،مقCدار یCک در خانCه iو jام ()adj[i][j] = 1 نشان می‌دهد که یک یال از راس iبه راس jوجود دارد. ماتریس مجاورت برای یک گراف بدون جهت همیشه متقارن است. ماتریس مجCاورت بCرای نمCایش گCراف هCای وزن دار اسCتفاده می شCود.اگCر ]adj[i][j ،= wآنگاه یک یال از راس iبه راس jبا وزن wوجود دارد. لیست مجاورت ()Adjacency List لیست مجاورت یک راه ساده برای نمایش یک نمودار به عنوان لیستی از Graph Representation Graph Search Depth-First-Search (DFS) : Follow Down Depth-First-Search (DFS) DFS(G,v) ( v is the vertex where the search starts ) Stack S := {}; ( start with an empty stack ) for each vertex u, set visited[u] := false; push S, v; while (S is not empty) do u := pop S; if (not visited[u]) then visited[u] := true; for each unvisited neighbour w of u push S, w; end if end while END DFS() Depth-First-Search (DFS) Depth-First-Search (DFS) Depth-First-Search (DFS) Depth-First-Search (DFS) Depth-First-Search (DFS) Depth-First-Search (DFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) Breadth-First-Searching (BFS) درخت پوشا Spanning Tree- درخت پوشCا زیرمجمCوعه‌ای از گCراف GاسCت کCه همCه رئCوس آن بCا کمCترین مقCدار یال‌هCای ممکن پوشCش یافتCه اسCت.از این رو یCک درخت پوشCا دور نCدارد و هیچ رأس ناهمبندی در آن دیده نمی‌شود. بر اسCاس تعریCف فCوق می‌تCوانیم نتیجCه بگCیریم کCه هCر گCراف کCامًال همبنCد و غCیر جهت‌دار GدسCت‌کم یCک درخت پوشCا دارد.یCک گCراف ناهمبنCد؛ هیچ درخت پوشCایی ندارد ،چون امکان پوشش همه رئوس آن میسر نیست. مشخصات کلی درخت پوشا اینک که دانستیم یک گراف می‌تواند بیش از یک درخت پوشا داشته باشد.در ادامه چند مورد از مشخصات درخت پوشای همبند با درخت Gرا بررسی می‌کنیم: یک گراف همبند Gمی‌تواند بیش از یک درخت پوشا داشته باشد. همه درخت‌های پوشای گراف Gتعداد یکسانی از یال‌ها و رئوس را دارند. درخت پوشا هیچ دوری ندارد. با حذف یک یال از درخت پوشا ،به گراف غیر همبند تبدیل می‌شود ،یعنی درخت پوشا دارای کمینه اتصال‌های ممکن است. افزودن یک یال به درخت پوشا موجب ایجاد یک مدار یا طوقه می‌شود ،یعنی درخت پوشا در حالت بیشینه غیر دوری ( ) maximally acyclicاست. درخت پوشا n-1یال دارد که nتعداد گره‌های (رأس‌های) آن است. Minimum Spanning Tree- خت پوشا کمینه در یCک گCراف وزن‌دار ،درخت پوشCای کمینCه ،آن درخت پوشCایی اسCت کCه کمCترین وزن تهCای دنیCای تهCای پوشCای همCان گCراف داشCته باشCد.در موقعی را نسCبت بCه دیگCر درخ واقعی این وزن می‌توانCد بCر اسCاس مسCافت ،ازدحCام ،بCار تCرافیکی ،یCا هCر مقCدار دلخواهی که به یال‌ها اختصاص می‌یابد اندازه‌گیری شود. دو مورد از مهم‌ترین الگوریتم‌های درخت پوشای کمینه به صورت زیر هستند: الگوریتم کروسکال kruskal الگوریتم پریم Prim هر دو این الگوریتم‌ها در دسته الگوریتم‌های حریصانه قرار الگوریتم کراسکال الگCوریتم کروسCکال بCرای یCافتن درخت پوشCای بCا کمCترین هزینCه از رویکCرد حریصCانه بهCره می‌گCیرد.این الگCوریتم بCا گCراف بCه صCورت یCک جنگCل برخCورد می‌کنCد کCه در آن هCر گCره یCک درخت منفCرد محسCوب یشCود اگCر و فقCط اگCر در میCان همCه گزینه‌هCای موجCود، یشCود.یCک درخت زمCانی بCه درخت دیگCر وصCل م م کمترین هزینه را داشته باشد و مشخصات درخت پوشای کمینه را نیز نقض نکند. الگوریتم کراسکال گام – 1حذف همه یال‌های طوقه و موازی همه یال‌های طوقه و یال‌های موازی را از گراف فوق حذف می‌کنیم. در مورد یال‌های موازی ،آن یالی را نگه می‌داریم که کمترین هزینه را دارد و بقیه را حذف می‌کنیم. الگوریتم کراسکال گام – 2چیدمان همه یال‌ها به ترتیب افزایش وزن در این مرحله مجموعه‌ای از یال‌ها و وزن‌هایشان ایجاد می‌کنیم و آنها را بر اساس ترتیب افزایش وزن (هزینه) می‌چینیم. الگوریتم کراسکال – 3یالی که کمترین وزن را دارد اضافه می‌کنیم اینک برای افزودن یال‌ها به گراف ،کار خود را از یالی آغاز می‌کنیم که کمترین وزن را دارد.در تمام طول این فرایند بررسی می‌کنیم که مشخصات پوشا بودن همچنان برقرار باشد.در موردی که با افزودن یک یال مشخصات درخت پوشا نقض شود، نمی‌بایست این یال را وارد گراف کنیم. الگوریتم کراسکال کمCترین هزینCه 2اسCت و یال‌هCای مربCوط بCه آن B,Dو D,TهسCتند.آنهCا را بCه گCراف اضCافه می‌کCنیم.بCا افCزودن این دو یCال ،مشخصCات درخت پوشCا نقض نمی‌شCود ،بنCابراین کCار خCود را ادامCه داده و یال‌هCای بعCدی را انتخCاب می‌کCنیم.در مرحلCه بعCد هزینCه 3اسCت و یال‌های مربوطه A,Cو C,Dهستند.آنها را نیز اضافه می‌کنیم. الگوریتم کراسکال هزینه بعدی در جدول 4 ،است و می‌بینیم که با افزودن یال مربوط به این وزن ،یک دور در گراف ایجاد می‌شود. این یال را نادیده می‌گیریم ،چون قرار است در این فرایند همه یال‌هایی که باعث ایجاد دور در گراف می‌شوند را نادیده بگیریم. الگوریتم کراسکال اینک مشاهده می‌کنیم که یال‌های مربوط به وزن‌های 5و 6نیز دور ایجاد می‌کنند و آنها را نیز نادیده گرفته و به کار خود ادامه می‌دهیم در این زمان تنها یک گره مانده است که باید اضافه شود.بین دو یال با کمترین هزینه 7 و 8میبایست یالی که وزن 7دارد را اضافه کنیم. افزودن یال S,Aهمه گره‌ها در گراف شامل شده‌اند و اینک درخت پوشای با کمترین هزینه را داریم. الگوریتم کراسکال الگوریتم پریم الگCوریتم پCریم بCرای یCافتن درخت پوشCای بCا کمCترین هزینCه (هماننCد الگCوریتم کروسCکال که در بخش قبل بررسی کردیم) از رویکرد حریصانه بهره می‌گیرد. الگCوریتم پCریم شCباهت‌هایی بCا الگوریتم‌هCای «کوتCاه‌ترین مسCیر ،اول» shortest path firstدارد. الگCوریتم پCریم در تضCاد بCا الگCوریتم کروسCکال اسCت ،چCون بCا گره‌هCا بCه عنCوان یCک درخت منفCرد برخCورد می‌کنCد و بCه افCزودن گره‌هCا بCه یCک درخت پوشCا از گCراف مفروض ادامه می‌دهد. الگوریتم پریم م – 1حذف همه یال‌های طوقه و موازی همه یال‌های طوقه و همچنین یال‌های موازی را از گراف مفروض حذف می‌کنیم.در مورد یال‌های موازی ،یال‌هایی را حفظ می‌کنیم که کمترین هزینه را دارند و بقیه را حذف می‌کنیم. الگوریتم پریم م – 2یک گره دلخواه را به عنوان ریشه انتخاب کنید در این مCورد مCا گCره Sرا بCه عنCوان گCره ریشCه درخت پوشCای پCریم در نظCر می‌گCیریم.این گCره بCه طCور دلخCواه انتخCاب شCده اسCت و هCر گCره دیگCری بCه جCای آن می‌تCوان انتخCاب کCرد.ممکن اسCت تعجب کنیCد کCه چطCور ممکن اسCت هCر گCرهی بCه عنCوان گCره ریشCه ههCا در یCک گCراف گنجانCده انتخCاب شCود ،پاسCخ این اسCت کCه در درخت پوشCا ،همCه گر می‌شCوند و از آن جCا کCه گCراف ،همبنCد اسCت ،در این صCورت می‌بایسCت دسCت‌کم یCک یCال برای هر گره باشد که آن را به بقیه درخت متصل سازد. الگوریتم پریم – بررسی یال‌های خروجی و انتخاب یالی که کمترین هزینه را دارد پس از انتخCاب گCره SبCه عنCوان ریشCه می‌بیCنیم کCه یCال S,Aو S,Cدو یCالی هسCتند کCه بCه ترتیب وزن‌های 7و 8دارند.یال S,Aانتخاب می‌شود چون کوچکتر از یال دیگر است. اینCک بCا درخت S-7-AبCه صCورت یCک گCره رفتCار می‌شCود و همCه یال‌هCایی کCه از آن خCارج می‌شCوند را بررسCی می‌کCنیم.یCالی را انتخCاب می‌کCنیم کCه کمCترین هزینCه را دارد و آن را در درخت می‌گنجانیم. الگوریتم پریم پس از این مرحله ،درخت S-7-A-3-Cتشکیل می‌یابد.اینک بار دیگر با آن به صورت یک گره برخورد می‌کنیم و همه یال‌ها را مجددًا بررسی می‌کنیم.با این حال ،مجددًا تنها یالی که کمترین هزینه را دارد انتخاب می‌کنیم.در این مورد C-3-D،یک یال جدید است که هزینه آن کمتر از یال‌های دیگر است. پس از افزودن گره Dبه درخت پوشا اینک دو یال داریم که از آن خارج می‌شوند و هزینه یکسانی دارند، یعنی D-2-Tو D-2-Bبنابراین می‌توانیم هر یک از آنها را که می‌خواهیم به درخت اضافه کنیم.اما در مرحله بعد یال 2کمترین هزینه را دارد.از این رو یک درخت پوشا را با گنجاندن هر دو یال نشان می‌دهیم. بدین ترتیب درمی‌یابیم که خروجی درخت پوشای گراف با استفاده از هر دو الگوریتم یکسان خواهد بود. الگوریتم دایکسترا الگوریتم دایجسترا در گراف ،یCک روش حریصانه بCرای یCافتن کوتCاه تCرین مسCیر از لهCا غCیر منفی یCک مبCداء واحCد اتخCاذ می‌کنCد.در این الگCوریتم الزم اسCت کCه وزن تمCامی یا باشد چرا که در غیر این صورت الگوریتم قادر به حل مسأله نیست. الگوریتم دایکسترا در با فCرض این کCه مسCأله مCورد نظCر یCافتن کوتCاه تCرین مسCیر از گCره مبCداءs گCراف) G=(V,EباشCد الگCوریتم دایجسCترا بCا شCروع از رأس sکوتCاه تCرین مسCیرها را از مبCداء sبCه تم امی رئ وس دیگ ر پیCدا می‌کنCد.بCرای درک بهCتر مراحCل اجCرای این الگوریتم به مثال زیر توجه کنید. الگوریتم دایکسترا همCان‌طور کCه از شCکل مشCخص اسCت ابتدا تمCامی رئCوس بCه غCیر از منبع sبCا ∞ عالمت‌گCذاری شCده‌اند. یعCنی هنCوز مسCیری از sبCه آنهCا کشCف نشCده اسCت.در مرحله بعد کوتCاه‌ترین مسCیر بین رأس sو تمCامی یشCود همCان رئوسCی کCه از sمسCتقیمًا یCالی بCه آنهCا وجCود دارد محاسCبه م یشCود.رأس بعCدی کCه انتخCاب م رأسCی اسCت کCه کوتCاه‌ترین مسCیر را به sداشCته (انتخCاب حریصCانه) و مراحCل ذکCر شCده بCرای رأس منبCع اکنCون بCرای این رأس تکCرار شCده و کوتCاه‌ترین مسCیرها از رأس فعلی بCه تمCامی رئوسCی کCه از رأس مCذکور مسCتقیمًا یCالی وجCود دارد محاسCبه می‌شCود.لیسCتی بCه صCورت زیCر کCه فاصCله گر ههCا تCا منبCع sرا نمCایش می‌دهد تهیه می‌کنیم. الگوریتم دایکسترا ههCای مجCاور آن را محاسCبه در مرحلCه اول گCره sرا انتخCاب و کوتCاه‌ترین فاصCله از این گCره تCا هCر یCک از گر یکCنیم و سCپس بعCد از محاسCبه ،گCره sرا از لیسCت حCذف می‌کCنیم.بCه عنCوان مثCال در ابتCدا فاصCله sتCا م گCره aبرابCر بینهCایت اسCت.در گCراف داده شCده بCا عبCور از مسCیر بCا وزن 10می‌تCوان از گCره sبCه گCرهa رسCید و از آنجCایی کCه 10کوچکCتر از ∞ (فاصCله فعلی گCره sتCا گCره )aاسCت پس کوتCاه‌ترین فاصCله از ههCای bو dنCیز کCه مجCاور بCا sهسCتند رخ گCره sتCا گCره aدر لیسCت فCوق ،بCروز می‌شCود.این امCر بCرای گر می‌دهد.در نهایت پس از پایان این مرحله به لیست زیر می‌رسیم: الگوریتم دایکسترا گراف اولیه نیز به صورت زیر بروز می‌شود: داخل هر نود میزان فاصله تا مبدا نوشته شده است الگوریتم دایکسترا حال در لیسCت جدیِCد بدسCت آمCده (مرحلCه )2گCره بCا فاصCله ( minکCه در اینجCا گCره aاسCت )،را انتخCاب کCرده و مراحCل فCوق را روی آن انجCام می‌دهیم.یعCنی گCره aرا انتخCاب و کوتCاه‌ترین فاصCله از این گCره تCا هCر یCک از گره‌هCای مجCاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه ،گره aرا از لیست حذف می‌کنیم. تنهCا گCره مجCاور aنCود cاسCت کCه بCا هزینCه 50می‌تCوان بCه آن رفت.همچCنین بCر اسCاس لیسCت ،فاصCله گCره منبCع تCا c برابCر بینهCایت اسCت.بCا گCذر از یCال بCا وزن 50کCه بین دو گCره aو cاسCت ،می‌تCوان بCا مجمCوع )50 + 10( 60از گCرهs بCه گCره aو سCپس بCه گCره cرسCید.از آنجCایی کCه 60از ∞ کوچکCتر اسCت می بایسCت لیسCت و گCراف داده شCده را بCروز کرد. الگوریتم دایکسترا حال در لیسCت جدCیِد بدسCت آمCده (مرحلCه )3گCره بCا فاصCله ،minکCه در اینجCا گCره dاسCت ،را انتخCاب کCرده و مراحCل فCوق را روی آن انجCام می‌دهیم.یعCنی گCره dرا انتخCاب و کوتCاه‌ترین فاصCله از این گCره تCا هCر یCک از گره‌های مجاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه ،گره dرا از لیست حذف می‌کنیم. ههCای مجCاور dهسCتند.از گCره منبCع تCا گCره dبCه انCدازه 30تCا هزینCه دارد.حCال اگCر بخCواهیم در cو bگر ادامه‌اش از گCره dبCه گCره bبCرویم بCا توجCه بCه اینکCه هCزینه dتCا bبرابCر 60اسCت ،در نتیجCه هزینCه مسCیر s->d->bبرابCر 60 + 30یعCنی 90اسCت.این هزینCه کمCتر از هزینCه مسCیر فعلی‌اش یعCنی مسCیرs- >bاست.در نتیجه مسیر با هزینه کمتر را در لیست و گراف‌مان بروز می‌کنیم. حال اگCر بخCواهیم بعCد از اینکCه از گCره منبCع بCه گCره dآمCدیم ،از dبه cبCرویم ،بCا توجCه بCه اینکCه هCزینه dتCاc برابCر 20اسCت در نتیجCه هزینCه مسCیر s->d->cبرابCر 20 + 30یعCنی 50اسCت.این هزینCه کمCتر از هزینCه مسCیر فعلی‌اش یعCنی مسCیر s->a->cاسCت.در نتیجCه مسCیر بCا هزینCه کمCتر را در لیسCت و گراف‌مCان بCروز الگوریتم دایکسترا الگوریتم دایکسترا حال در لیسCت جدیِCد بدسCت آمCده (مرحلCه )4گCره بCا فاصCله ،minکCه در اینجCا گCرهc اسCت ،را انتخCاب کCرده و مراحCل فCوق را روی آن انجCام می‌دهیم.یعCنی گCره cرا انتخCاب و کوتCاه‌ترین فاصCله از این گCره تCا هCر یCک از گره‌هCای مجCاور آن را محاسCبه می‌کCنیم و سپس بعد از محاسبه ،گره cرا از لیست حذف می‌کنیم. تنهCا گCره مجCاور cنCود bاسCت کCه بCا هزینCه 10می‌تCوان بCه آن رفت.حCال بCا توجCه بCه اینکCه کوتCاه‌ترین مسCیر از منبCع تCا نCود cبرابCر 50اسCت (بCر اسCاس آخCرین بCروز رسCانی لیسCت) در نتیجCه می‌تCوان بCا رفتن از گCره cبCه ،bیعCنی بCا هزینCه ،60 = 10 + 50از گCره منبCع به گره bرفتs->d->c->b. از آنجایی که 60از 90کوچکتر است میبایست لیست و گراف داده شده را بروز کرد. اکنCون بCا حCذف گCره cاز لیسCت فاصCله‌ها ،الگCوریتم دایجسCترا خاتمCه میابCد و در نهCایت گراف و لیست زیر را خواهیم داشت. الگوریتم دایکسترا الگوریتم دایکسترا در گراف بدست آمده یال‌های قرمز رنگ کوتاه‌ترین مسیرها از گره منبع تا هر یک از گره‌های گراف هستند.
