مسئله تطابق سه‌بعدی

مسئله تطابق سه‌بعدی

تطابق سه‌بعدی در نظریه گراف تعمیم تطابق دوبخشی (تطابق دوبعدی) به ۳ ابرگراف یک‌شکل است. پیدا کردن بزرگ‌ترین تطابق سه‌بعدی یک مسئلۀ ان‌پی-سخت مشهور در نظریه پیچیدگی محاسباتی است.

تعریف

فرض کنید $X$، $Y$ و $Z$ مجموعه‌های متناهی مجزا باشند و $T$ یک زیرمجموعه از $Z$ × $Y$ × $X$ باشد. یعنی $T$ شامل ۳ تایی‌های $(x,y,z)$ است به طوری که $X$ ∋ $x$، $Y$ ∋ $y$ و $Z$ ∋ $z$.$T$ ⊇ $M$ یک تطابق سه‌بعدی است در صورتی که به ازای هر دو سه‌تایی مجزا $M$ ∋ (${x_{1}},{y_{1}},{z_{1}}$) و $M$ ∋ (${x_{2}},{y_{2}},{z_{2}}$) داشته باشیم: ${x_{2}}$≠${x_{1}}$ ، ${y_{2}}$≠${y_{1}}$ و ${z_{2}}$≠${z_{1}}$ .

مثال

شکل سمت چپ صفحه تطابق‌های سه‌بعدی را نشان می‌دهد. $X$ با نقاط قرمز، $Y$ با نقاط آبی و $Z$ با نقاط سبز نشان داده شده‌است. شکل الف مجموعۀ $T$ (نواحی خاکستری) را نشان می‌دهد. شکل ب یک تطابق سه‌بعدی $M$ با ۲ = |$M$| را نشان می‌دهد و شکل پ یک تطابق سه‌بعدی $M$ با ۳ = |$M$| را نشان می‌دهد.

تطابق $M$ که در شکل پ نشان داده‌شده‌است یک تطابق سه‌بعدی بیشینه است، یعنی |$M$| را بیشینه می‌کند. تطابق‌های نشان داده‌شده در شکل‌های ب و پ تطابق‌های سه‌بعدی ماکسیمال هستند، یعنی نمی‌توان با افزودن عضوهای بیش‌تری از $T$ آن‌ها را گسترش داد.

مقایسه با مسئله تطابق دو بخشی

یک تطابق دوبعدی را می‌توان به‌طور کاملاً مشابه تعریف کرد. فرض کنید $X$ و $Y$ مجموعه‌های متناهی مجزا باشند و $T$ یک زیرمجموعه از $X$ × $Y$ باشد. $T$ ⊇ $M$ یک تطابق دوبعدی است در صورتی که برای هر دو زوج مجزای $M$ ∋ (${x_{1}},{y_{1}}$) و $M$ ∋ (${x_{2}},{y_{2}}$) داشته باشیم: ${x_{2}}$ ≠ ${x_{1}}$ و ${y_{2}}$ ≠ ${y_{1}}$.

در تطابق دوبعدی، مجموعۀ $T$ را می‌توان به صورت مجموعۀ یال‌ها در یک گراف دوبخشی ($X,Y,T$) = $G$ تعبیر کرد؛ هر یال $T$ یک رأس از $X$ را به یک رأس از $Y$ متصل می‌کند و یک تطابق دوبعدی یک تطابق در گراف $G$ است، یعنی مجموعه‌ای از یال‌های دوبه‌دو غیرمجاور.

از این رو تطابق‌های سه‌بعدی را می‌توان به صورت تعمیم تطابق به ابرگراف‌ها تعبیر کرد: مجموعه‌های $X$، $Y$ و $Z$ شامل یال‌ها هستند، هر عضو $T$ یک ابرگراف است و مجموعۀ $M$ شامل یال‌های دوبه‌دو غیرمجاور است (یال‌هایی که رأس مشترک ندارند).

مقایسه با مسئله بسته‌بندی مجموعه

یک تطابق سه‌بعدی حالت خاصی از یک بسته بندی مجموعه است: می‌توانیم هر عضو ($x,y,z$) از $T$ را به عنوان یک زیرمجموعۀ {$x,y,z$} از $Z$ ∪ $Y$ ∪ $X$ تعبیر کنیم؛ پس یک تطابق سه‌بعدی $M$ شامل زیرمجموعه‌های دوبه‌دو مجزا است.

مسئله تصمیم

در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله تصمیم زیر است:

با داشتن مجموعۀ $T$ و عدد صحیح $k$، آیا یک تطابق $T$ ⊇ $M$ با $k$ ≤ |$M$| وجود دارد؟ این مسئلۀ تصمیم ان‌پی-کامل است؛ یکی از ۲۱ مسئله ان‌پی-کامل کارپ است.

این مسئله حتی در حالت خاص |$Z$| = |$Y$| = |$X$| = $k$ هم ان‌پی-کامل است. در این حالت یک تطابق سه‌بعدی نه تنها یک مسئله بسته‌بندی مجموعه است بلکه یک مسئله پوشش دقیق نیز هست: مجموعۀ $M$ هر عضو $X$، $Y$ و $Z$ را دقیقاً یک بار پوشش می‌دهد.

مسئله بهینه‌سازی

یک تطابق سه‌بعدی بیشینه یک بزرگترین تطابق سه‌بعدی است. در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله بهینه‌سازی زیر است:

با داشتن مجموعۀ $T$، یک تطابق سه‌بعدی $T$ ⊇ $M$ که |$M$| را بیشینه می‌کند پیدا کنید.

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

الگوریتم‌های تقریبی

این مسئله APX-کامل است، یعنی به سختی می‌توان آن را در حدود یک عدد ثابت تقریب زد. برای هر عدد مثبت ثابت ε>0، یک الگوریتم چندجمله‌ای (ε + ۳/۲)-تقریب برای تطابق سه‌بعدی وجود دارد.

یک الگوریتم خیلی سادۀ چندجمله‌ای ۳-تقریب برای تطابق سه‌بعدی وجود دارد: یک تطابق سه‌بعدی ماکسیمال بیابید. همان‌گونه که یک تطابق ماکسیمال در حدود عامل ۲ یک تطابق بیشینه است، یک تطابق سه‌بعدی ماکسیمال نیز در حدود عامل ۳ یک تطابق سه‌بعدی بیشینه است.

منابع

• http://en.wikipedia.org/wiki/3-dimensional_matching