گراف دوبخشی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مثالی از يک گراف دو بخشی بدون دور

در نظریه‌ی گراف (یکی از شاخه‌های ریاضیات) ، گراف دوبخشی گرافی است که راس‌هایش را می‌توان به دو مجموعه‌ی مجزا مثل U و V تقسیم کرد، طوری که هر یال از آن گراف، یک راس از U را به یک راس از V متصل می‌کند. معادلا، گراف دوبخشی گرافی است که دور به طول فرد ندارد.

می‌توان به U و V به چشم یک رنگ‌آمیزی مجاز گراف نگاه کرد: اگر همه‌ی راس‌های مجموعه‌ی U را آبی و همه‌ی راس‌های مجموعه‌ی V را سبز کنیم، دو راس‌ انتهایی هر یال رنگ‌های متفاوتی خواهند داشت که نشان‌دهنده‌ی یک رنگ‌آمیزی مجاز برای گراف است. از طرف دیگر، این نوع رنگ‌آمیزی برای گراف‌های غیر دوبخشی (مثل مثلث) غیر ممکن است. مثلا در مثلث، اگر یک راس را به رنگ آبی و دیگری را به رنگ سبز در‌آوریم، راس سوم را نمی‌توانیم با هیچ‌کدام از این رنگ‌ها رنگ کنیم، چون این راس به هر دو راس دیگر متصل است.

گراف دو بخشی را معمولا به صورت G=(U,V,E) نشان می‌دهیم که U و V دو بخش گراف و E مجموعه‌ی یال‌های گراف است. اگر یک گراف دوبخشی همبند نباشد، ممکن است بتوان راس‌های آن را به شیوه‌های مختلف به دو بخش تقسیم نمود (یعنی ممکن است U و V یکتا نباشند). در این صورت نمایش G=(U,V,E) سودمند واقع می‌شود؛ چون به کمک آن می‌توان یک حالت خاص تقسیم رئوس گراف به دو بخش را از بقیه‌ی حالات متمایز کرد. اگر |U|=|V| ، گراف G را گراف دوبخشی متوازن می‌نامیم. اگر درجه‌ی تمام راس‌های U با هم و نیز درجه‌ی تمام راس‌های V با هم برابر باشد، گراف G را گراف دوبخشی شبه منتظم می‌نامیم.

مثال‌ها[ویرایش]

وقتی رابطه‌ی بین دو گروه مختلف از اشیا را مدل‌سازی می‌کنیم، معمولا گراف‌های دوبخشی به طور طبیعی ظاهر می‌شوند. به عنوان مثال، فرض کنید یک گراف داشته باشیم که راس‌های آن نمایانگر بازیکنان فوتبال و باشگاه‌ها باشند. یک بازیکن را به یک باشگاه وصل می‌کنیم، اگر آن بازیکن برای آن باشگاه بازی کرده باشد. این گراف نمونه‌ای از شبکه‌های وابستگی (affiliation network) است. این شبکه‌ها نوعی گراف دوبخشی هستند و از آن‌ها در آنالیز شبکه‌ی اجتماعی (social network analysis) استفاده می‌شود.

مثال دیگری که در آن، گراف دوبخشی به طور طبیعی ظاهر می‌شود، مساله‌ی بهینه‌سازی راه‌آهن است (NP-complete) که در آن، ورودی برنامه‌ی حرکت زمانی قطار‌ها و توقف آن‌ها است و هدف یافتن کوچکترین مجموعه‌ی ممکن از ایستگاه‌های قطار است، طوری که هر قطار در حداقل یکی از این ایستگاه‌ها توقف کند. این مساله را می‌توان به صورت یافتن یک مجموعه‌ی غالب در یک گراف دوبخشی مدل‌سازی کرد که در این گراف برای هر قطار و هر ایستگاه یک راس وجود دارد و یک قطار به یک ایستگاه وصل می‌شود، اگر آن قطار در آن ایستگاه توقف کند.

مثال‌های انتزاعی‌تر به شرح زیر می‌باشند:

  • هر درخت دوبخشی است.
  • دور به طول زوج دوبخشی است.
  • هر گراف مسطح که طول تمام وجه‌هایش زوج است، دوبخشی می‌باشد. حالت‌های خاص این مورد، گراف‌های شبکه‌ای (grid graph) و گراف‌های مربعی (squaregraph) هستند که در آن‌ها هر وجه داخلی 4 یال دارد و هر راس داخلی 4 یا تعداد بیشتری همسایه دارد.
  • گراف کامل دوبخشی که از دو بخش با تعداد راس‌های m و n تشکیل شده‌ است و با Km,n نمایش داده می‌شود، گراف دوبخشی G=(U,V,E) است که U و V مجموعه‌های متمایز از راس‌های گراف، به ترتیب با اندازه‌های m و n هستند و E هر راس از U را به تمام راس‌های V وصل می‌کند. پس نتیجه می‌شود که Km,n ، mn یال دارد. گراف‌های تاجی شکل (crown graph) ارتباط نزدیکی با گراف‌های کامل دوبخشی دارند و در واقع با حذف یال‌های یک تطابق کامل از گراف کامل دوبخشی به دست می‌آیند.
  • گراف‌های k-مکعب ، partial cube و گراف‌های میانه (median graphs) دوبخشی هستند. در این گراف‌ها، راس‌ها را می‌توان با رشته‌هایی از 0 و 1 به طول برابر برچسب‌گذاری کرد، طوری که دو راس مجاور باشند، اگر و تنها اگر رشته‌های متناظر با آن‌ها فقط در یک بیت با هم اختلاف داشته باشند. یک روش تقسیم رئوس این‌گونه گراف‌ها به دوبخش، به این صورت است که رئوسی را که تعداد یک های موجود در رشته‌ی متناظر با آن‌ها فرد است، در یک دسته و رئوسی را که تعداد یک‌های موجود در رشته‌ی متناظر با آن‌ها زوج است، در دسته‌ای دیگر قرار می‌دهیم. درخت‌ها و گراف‌های مربعی (squaregraphs) نوعی از گراف‌های میانه‌ای (median graphs) هستند و هر گراف میانه‌ای (median graph) یک partial cube است.

خواص[ویرایش]

توصیف[ویرایش]

گراف‌های دوبخشی را به چند روش می‌توان توصیف کرد:

  • یک گراف دوبخشی است، اگر و تنها اگر شامل دور فرد نباشد.
  • یک گراف دوبخشی است، اگر و تنها اگر 2-رنگ‌پذیر باشد (یعنی عدد رنگی آن کمتر یا مساوی 2 باشد).
  • Spectrum یک گراف متقارن است، اگر و تنها اگر آن گراف دوبخشی باشد.

قضیه‌ی König و گراف‌های آرمانی[ویرایش]

در گراف‌های دوبخشی، اندازه‌ی کوچکترین پوشش راسی برابر با اندازه‌ی بزرگترین تطابق است:این قضیه‌ی König است. صورت دیگر و معادل این قضیه، این است که مجموع اندازه‌ی بزرگترین مجموعه‌ی مستقل و اندازه‌ی بزرگترین تطابق برابر با تعداد رئوس است. در هر گرافی که راس منزوی نداشته باشد، مجموع اندازه‌ی کوچکترین پوشش یالی و اندازه‌ی بزرگترین تطابق برابر با تعداد رئوس است. اگر این تساوی را با قضیه‌ی König ترکیب کنیم، به این نتیجه می‌رسیم که در گراف‌های دوبخشی، اندازه‌ی کوچکترین پوشش یالی برابر با اندازه‌ی بزرگترین مجموعه‌ی مستقل است، و مجموع اندازه‌ی کوچکترین پوشش یالی و اندازه‌ی کوچکترین پوشش راسی برابر با تعداد راس‌ها است.

نتایج دیگری که از قضیه‌ی König به دست می‌آیند، به گراف‌های آرمانی مربوط می‌شوند: هر گراف دوبخشی، مکمل هر گراف دوبخشی، line graph هر گراف دوبخشی و مکمل line graph هر گراف دوبخشی همگی آرمانی هستند. آرمانی بودن گراف‌های دوبخشی را به راحتی می‌توان بررسی کرد (عدد رنگی آن‌ها دو است و اندازه‌ی بزرگترین خوشه‌ی آن‌ها هم دو است) اما آرمانی بودن مکمل یک گراف دوبخشی چندان بدیهی نیست، و در واقع صورت دیگری از قضیه‌ی König است. این یکی از نتایجی بود که انگیزه‌ی تعریف گراف‌های آرمانی را به وجود آورد. آرمانی بودن مکمل line graph گراف‌های آرمانی هم نتیجه‌ی دیگری است که از قضیه‌ی König به دست می‌آید، و آرمانی بودن خود line graph ها بیان دیگری از قضیه‌ای قدیمی‌تر، از König می‌باشد که هر گراف دوبخشی یک رنگ‌آمیزی یالی با استفاده از تعدادی رنگ که تعداد آن‌ها برابر با بیشترین درجه‌ی گراف است، دارد.

بنابر نظریه‌ی قوی گراف‌های آرمانی (strong perfect graph theorem) ، گراف‌های آرمانی خاصیتی شبیه به گراف‌های دوبخشی دارند: یک گراف دوبخشی است، اگر و تنها اگر شامل هیچ زیرگرافی به شکل دور فرد نباشد، و یک گراف آرمانی است، اگر و تنها اگر هیچ زیرگراف القایی از آن به شکل دور فرد یا مکمل آن نباشد. گراف‌های دوبخشی، line graph گراف‌های دوبخشی، و مکمل آن‌ها، 4 رده از 5 رده‌ی اصلی گراف‌های آرمانی را که در اثبات قضیه‌ی قوی گراف‌های آرمانی (strong perfect graph theorem)از آن‌ها استفاده می‌شود، تشکیل می‌دهند.

ارتباط با ابرگراف‌ها (hyphergraphs) و گراف‌های جهتدار[ویرایش]

ماتریس مجاورت گراف دوبخشی (U,V,E) یک ماتریس شامل 0 و 1 با اندازه‌ی |U|\times|V| است که در هر خانه‌ی آن، اگر دو راس مربوط به آن خانه مجاور باشند، 1 و در غیر این صورت صفر قرار داده می‌شود. از ماتریس‌ مجاورت گراف‌های دوبخشی می‌توان برای نشان دادن هم‌ارزی بین گراف‌های دوبخشی، ابرگراف‌ها، و گراف‌های جهتدار استفاده کرد.

یک ابرگراف (hypergraph) یک ساختار ترکیبیاتی است که همانند گراف‌های غیر جهتدار، تعدادی راس و یال دارد، ولی هر یال می‌تواند مجموعه‌ی دلخواهی از رئوس باشد (به جای این که دقیقا از دو راس تشکیل شده باشد). از گراف دوبخشی (U,V,E) می‌توان برای مدل‌سازی ابرگراف‌ها استفاده نمود که در آن U مجموعه‌ی راس‌های ابرگراف و V مجموعه‌ی ابریال‌ها (hyperedges) است و E شامل یک یال از یک راس ابرگراف مثل v به یک ابریال مثل e است، اگر v یکی از نقاط انتهایی e باشد. با این تناظر، ماتریس‌ مجاورت یک گراف‌ دوبخشی دقیقا همان ماتریس وقوع ابرگراف متناظر با آن‌ است. به عنوان یک حالت خاص از این تناظر بین گراف‌های دوبخشی و ابرگراف‌ها، هر گراف چندگانه (گرافی که ممکن است بین دو راس از آن دو یا چند یال وجود داشته باشد) را می‌توان به صورت یک ابرگراف در نظر گرفت که در آن برخی ابریال‌ها مجموعه‌ی یکسانی از راس‌ها را دارند و این ابرگراف را می‌توان با یک گراف دوبخشی نشان داد که یال چندگانه ندارد و همه‌ی راس‌های یک طرف آن از درجه‌ی 2 هستند.

تفسیر مشابهی از ماتریس‌های مجاورت برای برقراری تناظر یک به یک بین گراف‌های جهتدار (که در آن‌ها راس‌ها برچسب‌گذاری شده‌اند و طوقه مجاز است) و گراف‌های دوبخشی متوازن (balanced bipartite graphs) که در آن‌ها تعداد رئوس موجود در دو بخش با هم برابر است، به کار می‌رود. ماتریس مجاورت یک گراف جهتدار با n راس می‌تواند هر ماتریس n\times n شامل 0 و 1 باشد که آن را می‌توان به عنوان ماتریس مجاورت یک گراف دوبخشی با n راس در هر بخش در نظر گرفت. در این فرآیند، گراف دوبخشی به دست آمده را bipartite double cover گراف جهتدار می‌نامیم.

الگوریتم‌ها[ویرایش]

بررسی دو بخشی بودن یک گراف[ویرایش]

می‌توانیم در زمان خطی (با استفاده از الگوریتم جستجوی عمق-اول (depth-first search)) تشخیص دهیم که یک گراف دوبخشی است یا نه و یک 2-رنگ‌آمیزی از آن گراف را برگردانیم (اگر دوبخشی است) یا یک دور فرد از آن گراف را برگردانیم (اگر دوبخشی نیست). ایده‌ی اصلی این است که در جهت پیمایش درخت جستجوی عمق-اول حرکت کنیم و به هر راس رنگی را نسبت دهیم که با رنگ پدرش متفاوت است. این کار قطعا یک 2-رنگ‌آمیزی از یک زیر درخت فراگیر گراف، که شامل یال‌هایی است که راس‌ها را به پدرانشان وصل می‌کنند، به دست می‌دهد ولی این رنگ‌آمیزی ممکن است باعث شود دو راس انتهایی یکی از یال‌های گراف که در این زیر درخت فراگیر نیامده، همرنگ شوند. در درخت جستجوی عمق-اول، یکی از دو راس انتهایی هر یالی که در درخت نیامده، جد راس دیگر می‌باشد و وقتی الگوریتم جستجوی عمق-اول یالی از این دست را پیدا می‌کند، باید چک کند که دو راس انتهایی آن همرنگ نباشند. اگر همرنگ باشند، مسیر درون درخت از راس جد به راس نوه به همراه یالی که راس‌هایش اشتباه رنگ شده‌اند، تشکیل یک دور به طول فرد می‌دهند که به همراه این نتیجه که گراف دوبخشی نیست، توسط الگوریتم بازگردانده می‌شود. اما اگر الگوریتم بدون پیدا کردن چنین دور فردی متوقف شود، در این صورت تمام رئوس باید به طور مجاز رنگ‌آمیزی شده باشند و الگوریتم، رنگ‌آمیزی انجام شده را به همراه این نتیجه که گراف دوبخشی است، بازمی‌گرداند.

می‌توان به جای استفاده از الگوریتم جستجوی عمق-اول، از الگوریتم جستجوی سطح-اول (breadth-first search) هم استفاده کرد. باز هم مثل قبل، به هر راس در درخت جستجوی سطح-اول، رنگی را نسبت می‌دهیم که با رنگ پدرش در این درخت متفاوت باشد. اگر وقتی که یک راس رنگ می‌شود، یالی در گراف موجود باشد که این راس را به یک راس قبلا رنگ شده با رنگ مشابه وصل کند، این یال به همراه مسیرهایی در درخت جستجوی سطح-اول که این دو راس را به کوچکترین جد مشترکشان (lowest common ancestor) وصل می‌کنند، تشکیل یک دور به طول فرد می‌دهند. اگر الگوریتم بدون پیدا کردن دور فردی با این روش متوقف شود، رنگ‌آمیزی انجام شده مجاز است و می‌توان نتیجه گرفت که گراف دوبخشی است.

برای گراف برخورد n پاره‌خط یا دیگر شکل‌های ساده در صفحه‌ی اقلیدسی، می‌توان در زمان O(n\log n) بررسی کرد که گراف دوبخشی است یا نه و یک 2-رنگ‌آمیزی گراف یا یک دور فرد از آن را برگرداند، با این که ممکن است خود گراف حتی \Omega(n^2) یال داشته باشد.

Odd cycle transversal[ویرایش]

Odd cycle transversal یک مساله‌ی الگوریتمیک NP-Complete است که به عنوان ورودی یک گراف G=(V,E) و یک عدد k دریافت می‌کند و بررسی می‌کند که آیا مجموعه‌ای از k راس از G وجود دارند که حذف آن‌ها از G باعث دوبخشی شدن گراف حاصل شود یا نه. این مساله fixed-parameter tractable است، یعنی الگوریتمی وجود دارد که زمان اجرای آن می‌تواند به حاصل‌ضرب یک تابع چندجمله‌ای از اندازه‌ی گراف و یک تابع بزرگتر با متغیر k محدود شود. به طور دقیق‌تر، زمان اجرای این الگوریتم O(3^k .mn) است.

گرافی که اندازه ی odd cycle transversal آن 2 است: حذف دو راس آبی یک گراف دوبخشی به وجود می‌آورد.

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

مساله‌ی دوبخشی کردن یالی (edge bipartization) یک مساله‌ی الگوریتمیک است که در آن به دنبال حذف‌ کردن کمترین تعداد یال‌های ممکن از گراف هستیم، طوری که گراف حاصل دوبخشی شود.

تطابق[ویرایش]

یک تطابق در گراف، زیر مجموعه‌ای از یال‌های آن است که در آن هیچ دو یالی راس مشترک ندارند. برای بسیاری از مساله‌های مربوط به تطابق مثل تطابق بیشینه (یافتن تطابقی که بیشترین تعداد یال‌های ممکن را شامل می‌شود)، تطابق با وزن بیشینه و ازدواج پایدار (stable marriage)، الگوریتم‌هایی با زمان چندجمله‌ای وجود دارند. در بسیاری از موارد مسائل تطابق را می‌توان با استفاده از گراف‌های دوبخشی راحت‌تر حل کرد (تا این که بخواهیم از گراف‌های غیر دوبخشی استفاده کنیم) و بسیاری از الگوریتم‌های تطابق مثل الگوریتم Hopcroft-Karp برای یافتن تطابق با اندازه‌ی بیشینه فقط روی ورودی‌های دوبخشی درست کار می‌کنند.

به عنوان یک مثال ساده، فرض کنید مجموعه‌ی P شامل تعدادی فرد، به دنبال یافتن شغل بین مجموعه‌ی J از تعدادی شغل هستند و همه‌ی افراد برای همه‌ی شغل‌ها مناسب نیستند. این وضعیت را می‌توان با گراف دوبخشی (P,J,E) مدل‌سازی کرد که در آن هر یال، یک جوینده‌ی شغل را به شغل‌های مناسبش وصل می‌کند. تطابق کامل معادل با این است که همزمان برای همه‌ی افراد شغل پیدا کنیم و همچنین همه‌ی شغل‌ها را پر کنیم. قضیه‌ی ازدواج ویژگی‌ای را برای گراف‌های دوبخشی مطرح می‌کند که در گراف‌های دوبخشی دارای آن ویژگی می‌توان تطابق کامل پیدا کرد.

روش تجزیه‌ی Dulmage-Mendelsohn یک تجزیه‌ی ساختاری گراف‌ دو بخشی است که در یافتن تطابق‌های بیشینه مفید می‌باشد.

سایر کاربردها[ویرایش]

گراف‌های دوبخشی به طور گسترده‌ای در نظریه‌ی کد‌گذاری مدرن مورد استفاده قرار می‌گیرند، مخصوصا برای رمزگشایی کد‌های (codewords) دریافت‌شده از کانال. گراف‌های Factor و گراف‌های Tanner مثال‌هایی از این مورد هستند. گراف Tanner ، یک گراف دوبخشی است که در آن راس‌های یکی از دو بخش نشان‌دهنده‌ی ارقام یک کلمه از کد (codeword) هستند و راس‌های بخش دیگر ترکیب‌هایی از ارقام را نشان می‌دهند که انتظار می‌رود در کد (codeword) بدون خطا مجموع آن‌ها صفر شود.

در علوم کامپیوتر، شبکه‌ی Petri net) Petri) یک ابزار مدل‌سازی ریاضی است که در آنالیز و شبیه‌سازی سیستم‌های همزمان استفاده می‌شود. یک سیستم به صورت یک گراف دوبخشی جهتدار با دو بخش مدل‌سازی می‌شود: یک بخش از راس‌های "مکان" که شامل منابع هستند و یک بخش از راس‌های "رخداد" که منابع را مصرف و/یا تولید می‌کنند. محدودیت‌های بیشتری روی راس‌ها و یال‌ها وجود دارند که رفتار سیستم را محدود می‌کنند. شبکه‌ی Petri از ویژگی‌های گراف‌های دوبخشی جهتدار و سایر ویژگی‌ها استفاده می‌کند تا امکان ارائه‌ی اثبات‌های ریاضی برای رفتار سیستم‌ها و در عین حال پیاده‌سازی ساده‌ی شبیه‌سازی‌های سیستم‌ها را فراهم کند.

در هندسه‌ی تصویری، گراف‌های Levi نوعی گراف دوبخشی هستند که برای مدل‌سازی واقع شدن نقاط و خط‌ها بر هم در یک پیکره (configuration) از آن‌ها استفاده می‌شود. بنابر ویژگی هندسی خطوط و نقاط که هر دو خط حداکثر در یک نقطه یکدیگر را قطع می‌کنند و هر دو نقطه را فقط با یک خط می‌توان به هم متصل کرد، گراف‌های Levi شامل هیچ دوری به طول 4 نیستند، پس طول کوتاهترین دور آن‌ها باید 6 یا بیشتر باشد.

جستارهای وابسته[ویرایش]

پیوند به بیرون[ویرایش]