اجزای قویاً همبند

موضوعوعات مرتبط با
همبندی (نظریه گراف)

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

تعاریف

[ویرایش]

یک گراف جهت دار قویا همبند نامیده می‌شود اگر مسیری در هر دو جهت بین هر جفت از رئوس گراف وجود داشته باشد. در گراف جهت‌دار G که ممکن است خودش قویا همیند نباشد، جفت رئوس u و v قویا همبند اند اگر مسیری در هر دو جهت بین آن‌ها وجود داشته باشد.

رابطه دوتایی «قویا همبند بودن»، یک رابطه هم‌ارزی است و زیرگراف‌های کامل کلاس‌های هم‌ارزی آن، اجزای قویا همبند نامیده می‌شوند. به همین شکل، یک بخش قویا همبند از گراف جهت دار G زیرگرافی است که قویا همبند است، و غیرقابل گسترش (ماکسیمال) است با این ویژگی که: هیچ یال یا راس اضافی از G را نمی‌توان بر زیرگراف، بدون از دست دادن ویژگی قویا همبند بودن اضافه کرد. مجموعهٔ اجزای قویا همبند به شکل یک پارتیشن از مجموعه‌ای از رئوس G است.

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

الگوریتم‌ها

[ویرایش]

چندین الگوریتم وجود دارد که اجزای قویا همبند را در زمان خطی محاسبه کند.

  • الگوریتم Kosaraju از دو مسیر از DFS استفاده می‌کند. اولی، در گراف اصلی، برای تعیین ترکیبی استفاده می‌شود که حلقهٔ بیرونی DFS دوم از آن برای بررسی دیده شدن یا نشدن راس‌ها استفاده می‌کند. DFSدوم در گراف مکمل گراف اصلی، و در هر جستجوی بازگشتی یک جزء قویا همبند می‌یابد. این الگوریتم را S. Rao Kosaraju در سال ۱۹۷۸ توصیف کرد اما نتایج خود را منتشر نکرد؛ پس از آن، MichaSharir در سال ۱۹۸۱ منتشر کرد.
  • الگوریتم Tarjan's strongly connected components، توسط Robert Tarjan در سال ۱۹۷۲ منتشر شده‌است و یک مسیر از DFS را می‌دهد. در این روش، در یک پشته، رئوسی که توسط جستجو کاوش شده اما هنوز به یک بخش اختصاص داده نشده‌اند نگهداری می‌شوند، و سپس «تعداد کم» (عدد شاخص از بالاترین جد قابل دسترسی در یک مرحله از یک نسل از راس) از هر راس محاسبه می‌شود. از آن برای تعیین زمانی که یک مجموعه از رئوس باید از پشته به یک بخش جدید pop شوند استفاده می‌کنیم.
  • الگوریتم path-based strong component، با استفاده از DFS، مانند الگوریتم Tarjan است، اما با دو پشته. یکی از پشته‌ها برای پیگیری رئوسی که هنوز به جزئی اختصاص داده نشده‌اند استفاده می‌شود، دومی مسیر فعلی در درخت DFS را نگه می‌دارد. اولین نسخه خطی از این الگوریتم توسط Edsger W. Dijkstra در سال ۱۹۷۶ منتشر شد.

اگرچه الگوریتم Kosaraju به لحاظ مفهومی ساده است، اما Tarjan و الگوریتم path-based strong component، در عمل نیاز به تنها یک DFS دارند و نه دو تا.

کاربرد

[ویرایش]

الگوریتم‌های موجود برای یافتن اجزای قویا همبند، ممکن است برای حل مسائل 2-satisfiability (سیستمی از متغیرهای دوحالتی، به همراه قیودی بر مقادیرِ جفتهای متغیرها) نیز مورد استفاده واقع شوند. همان‌طور که Aspvall, Plass، Tarjan (1979) در سال نشان دادند، یک نمونه مسئلهٔ 2-satisfiability، ارضا شدنی است اگر و تنها اگر، متغیری مثل v موجود باشد که v و مکمل آن هر دو در یک جزء قویا همبند از گراف مفهوم (implication graph)آن نمونه باشند.

اجزای قویا همبند همچنین برای محاسبهٔ تجزیهٔ Dulmage–Mendelsohn نیز بکار می‌روند، که یک طبقه‌بندی یال‌های یک گراف دوبخشی (bipartite graph) است، با توجه به اینکه آیا آن‌ها می‌توانند بخشی از یک تطابق کامل (perfect matching) در یک گراف باشند یا خیر.

نتایج مرتبط

[ویرایش]

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

با توجه به قضیه رابینز، یک گراف بدون جهت می‌تواند به گونه‌ای جهت‌دار کرد که قویا همبند شود، اگر و تنها اگر خود گراف ۲-همبند باشد. یک راه برای اثبات این نتیجه این است که یک تجزیه گوشی از گراف بدون جهت پیدا کنیم و پس از آن هر گوش را جهت دهی کنیم.

منابع

[ویرایش]