در نظریه گراف‌ها، دور به مسیر بسته‌ای گفته می‌شود که در آن هیچ رأسی تکراری نیست، به غیر از رئوس ابتدا و انتهای دور که یکسان هستند. دور جهت‌دار در گراف جهت‌دار را هم به همین‌ شکل تعریف می‌کنند. یعنی دنباله جهت‌دار غیرتهی که در آن فقط رئوس اول و آخر با یکدیگر مساوی هستند. گرافی که هیچ دوری در آن تشکیل نشود به نام «گراف غیرمدوّر» (Acyclic Graph) نامیده می‌شود. گراف متصل بهم و غیر جهت‌داری که هیچ دوری در آن تشکیل نشود را هم با نام درخت معرفی می‌کنند. دور یکی از مهم‌ترین مفاهیم مربوط به گراف‌ها است. در ادامه مطلب به بررسی دور در گراف پرداخته‌ایم. همچنین انواع دور را تعریف کرده‌ایم.

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

دور در گراف چیست؟

به مسیری که از یکی از رأس‌های گراف شروع شده و در انتها در همان رأس به پایان می‌رسد، دور گفته می‌شود. دور شامل مجموعه‌ای از گره‌های مجزا و در همسایگی همدیگر است. تنها استثنا مربوط به یکسان بودن گره‌های ابتدا و انتهای دور است. در تصویر زیر می‌توانیم ببینیم که گره‌های (3-4-5-6-3) یک دور تشکیل داده‌اند.

به همین ترتیب گرافی که شامل دور باشد را «گراف دوری» (Cyclic Graph) و گرافی را که هیچ دوری در آن وجود نداشته باشد را گراف بدون دور می‌نامیم. در نهایت هم گراف همبندی را هیچ دوری در آن نیست، درخت می‌نامیم.

در تصویر پایین گراف دوری و گراف بدون دور از نوع درخت را مشاهده می‌کنید.

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

• (v2-e2-v3-e4-v5-e5-v4-e3-v2)
• (v2-e2-v3-e6-v4-e3-v2)
• (v3-e4-v5-e5-v4-e6-v3)

مدار و دور جهت دار

مدار جهت‌دار به دنباله جهت‌داری گفته می‌شود که نقاط ابتدا و انتهای آن یکسان باشند. فرض کنیم که $$G = (V, E, Φ)$$

آشنایی با انواع نمودارها در فرادرس

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

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

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

دور بدون وتر

به «دور بدون وتر» (Chordless Cycle) در گراف‌ها «چاله» (Hole) یا «دور القایی» (Induced Cycle) گفته می‌شود. در این نوع از دور‌ها هیچ دو رأسی وجود ندارند که بتوانند توسط یالی به غیر از یال‌های مسیر دور به یکدیگر متصل شوند. «ضد چاله» (Antihole) به حالت برعکس گراف چاله گفته می‌شود.

در تصویر زیر، دور سبز رنگ (A–B–C–D–E–F–A)، «دور بدون وتر» است. در حالی که دور قرمز رنگ (G–H–I–J–K–L–G)، از نوع دور‌های Chordless نیست. زیرا در این دور، یال {K, I} نقش وتر را بازی می‌کند.

دور‌های بدون وتر برای توصیف «گراف‌های تام» (Perfect Graphs) نیز به کار برده می‌شوند. طبق قضیه گراف‌ تام، به گرافی که در آن هیچ‌ چاله یا ضد‌چاله‌ای، با تعداد رئوس فرد بزرگتر از ۳ وجود نداشته باشد، گراف تام گفته می‌شود.

در فهرست زیر چند مورد از اصطلاحات مربوط به دور را تعریف کرده‌ایم.

• «گراف وتری» (Chordal Graph): گراف وتری، نوع خاصی از گراف‌های تام است. در این گراف هیچ چاله‌ای با بیشتر از سه‌ رأس تشکیل نشده‌ است.
• «کمر گراف» (Girth Of Graph): به طول کمترین دور در گراف، کمر گراف گفته می‌شود. این دور حتما باید بدون وتر باشد.
• «قفس» (Cage): به کوچک‌ترین گراف‌ منظم که درجه و کمر مشخصی داشته باشد، «قفس» (Cage) گفته می‌شود.
• «دور جانبی» (Peripheral Cycle): دور جانبی به دوری در گراف گفته می‌شود که هر دو یال خارج از دور بتوانند به وسیله مسیری به یکدیگر متصل شوند. به این شرط که این مسیر از هیچ کدام از رأس‌های دور عبور نکند.

فضای دوری

با کلمه «دور» می‌توان به بخشی از «فضای دوری» (Cycle Space) در گراف هم اشاره کرد. فضاهای دور زیادی وجود دارند. هر کدام وابسته به نوع خاصی از دستگاه اعداد هستند. مشهور‌ترین آن‌ها «فضای دور باینری» (Binary Cycle Space) نام دارد. که معمولا نام آن را ساده کرده و با عنوان فضای دوری شناخته می‌شود. فضای دوری، شامل مجموعه‌ای از یال‌ها است که به صورت زوج به تمام رئوس متصل شده‌اند. یعنی اینکه هر رأس به تعداد زوجی یال – ۲، ۴، ۶ یا سایر اعداد زوج – متصل می‌شود. در نتیجه فضای برداری باینری را با دو عنصر «۰ و ۱» تشکیل می‌دهد.

مطابق با قضیه «وبلن» ( Veblen)، هر عنصری در فضای دوری را می‌توان به وسیله متصل کردن دور‌های ساده‌ای ایجاد کرد که یال مشترک ندارد. «Cycle Basis» در گراف، مجموعه‌ای از دور‌های ساده‌ است. این دور‌های ساده در کنار هم کل فضای دوری را تشکیل می‌دهند.

با استفاده از نظریات «توپولوژی جبری» (Algebraic Topology)، «فضای دور باینری» را می‌توان برای کار با «فضای برداری» (Vector Space) یا ماژول‌هایی از سایر دستگاه‌های عدد مانند اعداد صحیح، اعداد گویا یا اعداد حقیقی گسترش داد.

شناسایی دور

با استفاده از الگوریتم «جست‌وجوی اول عمق» (Depth-First Search | DFS) به سادگی می‌توانیم وجود دور را در گراف‌های جهت‌دار یا بدون جهت تشخیص دهیم. اگر الگوریتم DFS یالی پیدا کند که به یکی از گره‌های پدر رأس فعلی منتهی شده، به معنای آن است که حداقل یک دور در این گراف موجود است. تمام یال‌‌های برگشتی که DFS از روی آن‌ها عبور کرده جزئی از دور هستند. «یال برگشت» (Back Edge) به یالی گفته می‌‌شود که گره‌ها به کمک آن‌ به والد خود دسترسی پیدا می‌کنند.

نکته: در گراف‌های بدون جهت، یالی که گره‌ای را به پدر خود متصل کند به عنوان یال برگشت شناخته نمی‌شود.

همین‌ که DFS مسیری از گره به خودش پیدا کند به معنای وجود دور در گراف است. در گراف‌های بدون جهت، پیدا کردن دور در گرافی با n گره، زمانی برابر با O(n) صرف می‌کند. زیرا در این نوع از گراف‌ها در بیشترین حالت ممکن است «n-1» یال در درخت وجود داشته باشند.

بسیاری از «الگوریتم‌های مرتب‌سازی توپولوژیکی» (Topological Sorting Algorithms) می‌توانند دور‌ها را هم شناسایی کنند. زیرا وجود دور در گراف، مرتب‌سازی آن را غیر ممکن می‌سازد. اگر گراف‌های جهت‌دار را به «مولفه‌های قویا همبند» (Strongly Connected Components) تقسیم کنیم، دورها فقط می‌توانند درون این مولفه‌ها وجود داشته باشند، نه بین آن‌ها. زیرا دور‌ها قویا همبند هستند.

در گراف‌های جهت‌دار می‌توانیم از «الگوریتم‌های مبتنی بر پیام» (Message-Based Algorithms) برای پیدا کردن دور استفاده کنیم. «الگوریتم‌های مبتنی بر پیام» بر اساس ایده ساده‌ای کار می‌کنند. این ایده بیان می‌کند که اگر یکی از گره‌ها پیامی را در گراف بفرستد و این پیام بعد از چرخیدن در گراف دوباره به همان گره برگردد، به معنای آن است که حداقل یک دور در گراف وجود دارد. «الگوریتم‌های شناسایی دور توزیع شده» (Distributed Cycle Detection Algorithms) به درد استفاده بر روی گراف‌های بسیار بزرگ می‌خوردند. این گراف‌ها بر روی خوشه‌ای از کامپیوتر‌ها یا سوپرکامپیوتر‌ها قرار گرفته‌اند.

شناسایی دور کاربرد‌های گسترده‌ای دارد. برای نمونه از «گراف‌های انتظار» (Wait-For Graphs) برای تشخیص «بن‌بست‌ها» (Deadlocks) در «سیستم‌های همروند» (Concurrent Systems) استفاده می‌شوند. معمولا در این سیستم‌ها وظایف بسیار زیادی به صورت همزمان کار می‌کنند.

الگوریتم پیدا کردن دور در گراف

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

For every vertex v: visited(v) = finished(v) = false
For every vertex v: DFS(v)

در کدهای بالا دو عبارت بر روی هم قرار گرفته‌اند. این دو عبارت می‌گویند که:

1. برای تمام رئوس گراف دو پرچم «ملاقات شده» – visited  - و «به‌پایان رسیده» – finished - تعریف کن.
2. مقدار این دور پرچم را به ازای تمام رأس‌های گراف برابر با false قرار بده.
3. سپس الگوریتم DFS را بر روی تمام رأس‌ها یک به یک اجرا کن.

اجرای عملیات DFS به شکل زیر است.

DFS(v) =
  if finished(v): return
  if visited(v):
    "Cycle found"
    return
  visited(v) = true
  for every neighbour w: DFS(w)
  finished(v) = true

در گراف‌های بدون جهت، به تمام رأس‌های متصل به رأس v «همسایه» (Neighbour) گفته می‌شود. به غیر‌ از آن‌هایی که DFS(v) را به صورت بازگشتی فراخوانی کرده‌اند. این روش از شناسایی «دور بدیهی» (Trivial Cycle) یا بی‌اهمیتی، مانند v→w→v  توسط الگوریتم، جلوگیری می‌کند. زیرا چنین دور‌ی در تمام گراف‌های بدون جهتی که حداقل یک یال دارند، وجود دارد.

از الگوریتم «جست‌وجوی اول سطح» (Breadth-First Search | BFS) هم می‌توان برای پیدا کردن کوتاه‌ترین دور در گراف استفاده کرد.

چگونه با کمک فرادرس ساختمان داده یاد بگیریم؟

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

اثبات وجود دور در گراف

«لئونارد اویلر» (Leonhard Euler) در حل مسئله «هفت پل کونیگسبرگ» (Seven Bridges of Königsberg) ثابت کرده است که در گراف بدون جهت متناهی برای داشتن «گام بسته» (Closed Walk)، طوری که هر یال فقط یک‌بار طی شود، باید دو شرط زیر برقرار باشند.

1. گراف باید همبند باشد: یعنی اینکه تمام یال‌ها متعلق به یک گراف باشد.
2. هر رأس باید درجه زوج داشته باشد: یعنی اینکه به تعداد زوج یال به هر رأس متصل شده باشند.

برای درک بهتر موضوع بالا، بهتر است نکات زیر را در نظر داشته باشیم.

• نکته اول: گام بسته به معنی مسیری است که شروع و پایانش یکسان است.
• نکته دوم: به گام بسته‌ای که هر یال آن فقط یکبار طی شده، «دنباله بسته» (Closed Trail) گفته می‌شود.

در گراف‌های جهت‌دار شرایط کمی فرق می‌کنند. به این صورت است که:

1. گراف باید قویا همبند باشد: یعنی هر رأس به بقیه رأس‌ها متصل شده باشد.
2. درجه زوج داشته باشد: یعنی اینکه هر رأس باید به تعداد مساوی یال ورودی و خروجی داشته باشد.

این نوع مسیر مشهور به مسیر یا «گذر اویلری» (Eulerian trail) است.

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

وقتی که گراف همبندی، شرایط اویلر را تامین نکند، هنوز هم با استفاده از «مسئله مشاهده مسیر» ( Route Inspection Problem) می‌توانیم «کوتاه‌ترین گام» (Shortest Walk) را پیدا کنیم. طوری که تمام یال‌ها را پوشش دهد. این مسئله را می‌توان در زمان «چند جمله‌ای» (Polynomial Time) حل کرد.

مسئله پیدا کردن دوری که هر رأس را دقیقا یکبار طی کند – به‌جای پوشش دادن یال‌ها – بسیار سخت‌تر است. به این نوع دور، «دور همیلتونی» (Hamiltonian Cycle) گفته می‌شود. کشف این مسئله بسیار مشکل بوده و به نام NP-Complete شناخته می‌‌شود.

دسته‌ بندی گراف های مختلف بر اساس دور

چندین نوع مهم گراف‌ها را می‌توان با استفاده از ویژگی‌های دور در آن‌ها تعریف کرد.

این کلاس‌ها شامل موارد زیر هستند.

1. «گراف دوبخشی» (Bipartite Graph): گرافی که «دور فرد» (Odd Cycle) ندارد. دور فرد به دور‌هایی گفته می‌‌شود که تعداد رأس‌هایشان فرد است.
2. «گراف کاکتوس» (Cactus Graph): گراف ساده و همبندی است که هر یال آن در بیشترین حالت به یک دور ساده تعلق دارد.
3. «گراف دوری» (Cycle Graph): گرافی که از فقط از یک دور تشکیل شده است.
4. «گراف وتری» (Chordal Graph): به گرافی گفته می‌‌شود که تمام دور‌های القایی درون آن مثلث هستند.
5. «گراف جهت‌دار غیر مدور» (Directed Acyclic Graph): گراف جهت‌داری که هیچ دور جهت‌داری ندارد.
6. «جنگل» (Forest): گرافی که هیچ دوری ندارد.
7. «گراف خط تام» (Line Perfect Graph): گرافی که در آن تمام «دور‌های فرد» مثلث هستند.
8. «گراف تام» (Perfect Graph): گرافی که در آن هیچ دور القایی یا مکمل دور القایی با طول فرد و بزرگتر از سه وجود ندارد.
9. «شبهه جنگل» (PseudoForest): گرافی که در آن تمام مولفه‌های همبند، در بیشترین حالت شامل یک دور است.
10. «گراف فشرده» (Strangulated Graph): گرافی که در آن تمام «دورهای جانبی» (Peripheral Cycles) مثلث هستند.
11. «گراف قویا همبند» (Strongly Connected Graph): گراف جهت‌داری که در آن هر یال عضوی از یک دور است.

کاربرد دور در گراف چیست؟

دورها نقش بسیار حیاتی در شناخت صفات مشخصات گراف بازی می‌کنند. همچنین کاربردهای متنوع و زیادی هم دارند.

1. کشف کوتاه‌ترین مسیر: الگوریتم‌هایی مانند الگوریتم «دایجسترا» (Dijkstra) برای پیدا کردن کوتاه‌ترین مسیر بین رأس‌های مختلف در گراف‌ از دورها استفاده می‌کند.
2. مسیریابی در شبکه: شناخت صحیح دورهای موجود در شبکه به بهینه‌سازی مسیریابی برای داده‌ها و جریان ارتباطات کمک می‌کند.
3. زمان‌بندی و بهینه‌سازی: از دور‌ها برای حل کردن مسائل مربوط به زمان‌بندی هم استفاده می‌شود. برای مثال می‌توان به کشف مسیرهای بهینه برای انجام عملیات تحویل، اشاره کرد.
4. تحلیل شبکه‌های اجتماعی: دور در شبکه‌های اجتماعی، الگوی تعاملات و اثرگذاری بین افراد را کشف می‌کند.

جمع‌بندی

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

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