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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
پرونده:تطابق سه‌بعدی.png
تطابق‌های سه بعدی. (الف) ورودی T. (ب)-(پ) راه‌حل‌ها

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

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

فرض کنید X، Y و Z مجموعه‌های متناهی مجزا باشند و T یک زیرمجموعه از Z × Y × X باشد. یعنی T شامل ۳ تایی‌های (x, y, z) است به طوری که Xx، Yy و Zz.TM یک تطابق سه‌بعدی است در صورتی که به ازای هر دو سه‌تایی مجزا 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 باشد. TM یک تطابق دوبعدی است در صورتی که برای هر دو زوج مجزای 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} از ZYX تعبیر کنیم؛ پس یک تطابق سه‌بعدی M شامل زیرمجموعه‌های دوبه‌دو مجزا است.

مسئله تصمیم[ویرایش]

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

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

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

مسئله یهینه‌سازی[ویرایش]

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

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

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

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

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

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

منابع[ویرایش]