نحوه تشخیص گراف دو بخشی و پیاده سازی آن

به منظور تایید گراف دو بخشی (که در مبحث تئوری گراف آموختیم) میخواهیم بررسی کنیم آیا میتوان رأس‌های گراف را به دو بخش افراز کرد به گونه‌ای که تمام یال‌ها بین این دو بخش بیافتد. بنابر قضیه‌های گراف، شرط دو‌بخشی بودن با دور فرد نداشتن متناظر است، پس کافیست این شرط را چک کنیم.
برای تست این شرط و افراز به دو مجموعه، میتوانیم از هر دو الگوریتم جست‌و‌جوی عمق‌اول و جست‌و‌جوی سطح‌اول استفاده کنیم. کافیست نحوه علامت گذاری مزاعفی در این دو الگوریتم را به گونه ای اضافه کنیم که از رأس‌های با رنگ ۰ به رأس‌های با رنگ ۱ برویم و برعکس. حال اگر به رأسی با علامت ۱ رسیدیم که همسایه‌ای از آن از قبل رنگ ۱ را داشت، پس در نتیجه دور فرد پیدا شده است و نمیتوان این کار را کرد؛ برای علامت ۰ نیز به همین ترتیب است. حال اگر هیچ یک از این دو حالت اتفاق نیافتد، در نتیجه میتوان این کار را کرد و رأس‌هایی که علامت ۱ را دارند در یک دسته و بقیه را در دسته مقابل قرار می‌دهیم.
دقت کنید که ممکن است گراف نا‌همبند باشد در نتیجه برای تمام رأس‌های دیده نشده این الگوریتم را تکرار میکنیم.
برای این کار از جست‌و‌جوی اول‌سطح (Breadth First Search) که به bfs مشهور است استفاده نموده ایم، روشی برای پیمایش گراف است که بعد از جست‌وجوی عمق‌اول مهم‌ترین و پرکاربرد‌ترین الگوریتم پیمایش گراف است. این الگوریتم معمولا در گراف‌ها‌ی وزن دار کاربرد خاصی ندارد و عمده نقش آن در گراف‌های بی‌وزن و برای پیدا کردن کوتاه‌ترین فاصله بین یک راس تا بقیه‌ی راس‌هااست.

گراف دو بخشی
تشخیص گراف دو بخشی

الگوریتم گراف دو بخشی
این الگوریتم ابتدا یک راس ریشه مانند v را به عنوان شروع میگیرد. سپس راس‌ها را سطح بندی میکند. سطح بندی به این صورت است که تمام راس‌های مجاور v را در سطح اول قرار میدهیم، حال برای سطح i+1
، راس u که مجاور یکی از رئوس سطح i است را در این سطح قرار میدهیم به شرطی که u در هیچ سطح دیگری نیامده باشد. به عبارت دیگر راس هارا بر اساس کوتاه‌ترین فاصله از v سطح بندی میکنیم. حال برای پیمایش به ترتیب سطح، و در هر سطح به ترتیب دلخواه وارد راس‌ها میشویم. پس اولین زمانی که به هر راس می‌رسیم، با کمترین فاصله ممکن نسبت به v رسیده ایم.
پیچیدگی‌ الگوریتم
با توجه به اینکه به هر راس حداکثر یکبار وارد میشویم در نتیجه هر یالی هم حداکثر دوبار به ازای دو سر آن شمرده می‌شود، پس در کل هزینه الگوریتم از O(n+e) است که e تعداد یال‌ها و n تعداد راس‌ها است.bi
پیاده‌سازی
برای ایجاد سطح های مختلف و حرکت به ترتیب سطح ها نیاز به استفاده از صف داریم.
فرض کرده ایم که لیست مجاورت راس ها را داده اند و الگوریتم راس آغازین را نیز از ورودی می‌گیرد.

 

 

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

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

منبع:

https://s3.amazonaws.com/content.udacity-data.com/courses/gt-cs6505/bipartitematching.html

همچنین ببینید

تئوری گراف

تئوری گراف به صورت خلاصه (نظریه گراف ها)

نظریه گراف ها به صورت خلاصه در این مبحث به شرح تعاریف اولیه از نظریه …

دیدگاهتان را بنویسید