تطابق (گراف)

درنظریه گراف، به مجموعه‌ای از یال‌های یک گراف که با هم راس مشترک و منطبق بر یکدیگر ندارند، تطابق یا مجموعه‌ای مستقل از یال‌ها گفته می شود. همچنین تطابق می تواند کل گراف که فقط شامل یال‌های بدون راس مشترک است باشد.

تعریف

در گراف داده‌شدۀ G با مجموعه‌ی یال‌ها و رئوس مشخص که می توان آنرا به صورت (G(V,E نشان داد، به مجموعه‌ای از یال‌های غیر مجاور که هیج یک از دو یال آن راس مشترک نداشته باشند، یک تطابق در G می گویند و آنرا با M نشان می دهند.

در صورتی که راسی در یکی از دو انتهای یکی از یال‌ها در تطابق گراف G واقع شده باشد، به آن راس منطبق شده (یا اشباع) می گویند.در غیر این صورت، آن راس منطبق نشده است.

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

تصاویر زیر، تطابق ماکسیمال را برای 3 گراف نشان میدهد(گراف تطابق بیشینه با رنگ قرمز نشان داده شده است).

تطابق بیشینه تطابقی است که شامل بیشترین تعداد ممکن از یال‌هاست. بنابراین ممکن است تعداد تطابقهای بیشینه برای یک گراف، بیشتر از یکی باشد. عدد تطابق گراف G، اندازه‌ی تطابق بیشینه آن گراف است که با (ν(G نشان داده می شود. با توجه به تعاریف بالا برای تطابق بیشینه و ماکسیمال، می توان نتیجه گرفت که هر تطابق بیشینه، یک تطابق ماکسیمال نیز هست، اما همۀ تطابق‌های ماکسیمال لزوما تطابق بیشینه نیستند.

تصاویر زیر تطابق بیشینه را برای سه گراف نشان می دهد:

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

همچنین تطابق کامل، همان کوچکترین مجموعه‌ی پوشش یال است. پس (ν(G) ≤ ρ(G که در آن، (ν(G سایز تطابق بیشینه است که هیچ‌گاه بیشتر از کمترین سایز برای گراف پوشش یال‌ها نیز نمی‌شود.

تطابق نزدیک به کامل به تطابقی گفته می شود که در آن دقیقا یک راس، مطابقت داده نشده‌است و این تنها زمانی اتفاق می افتد که تعداد رئوس گراف فرد باشد و تطابقی که به دنبال آن هستیم، تطابق بیشینه باشد. در شکل‌های بالا، شکل (ج) یک تطابق نزدیک به کامل را نشان میدهد. اگر برای همۀ رئوس یک گراف، یک تطابق نزدیک به کامل وجود داشته باشد که تنها همان راس را در نظر نمی گیرد، به آن گراف factor-critical هم گفته می شود.

در یک گراف تطابقی M:

• یک مسیر متناوب مسیری است که در آن، یال‌ها یک در میان یال‌های تطابقی و غیر تطابقی باشند.
• یک مسیر افزایشی مسیر متناوبی است که از یک راس آزاد(اشباع نشده) شروع و به راس آزاد دیگری ختم می شود.

می توان ثابت کرد که یک تطابق بیشینه است اگر و تنها اگر در آن مسیر افزایشی وجود نداشته باشد(این نتیجه گیری به قضیه برژ^*[۱]) هم مشهور است).

خواص

در هر گرافی که در آن راس ناهمبند وجود نداشته باشد، مجموع عدد تطابق و عدد پوشای یال، برابر تعداد رئوس است. چنانچه یک تطابق کامل وجود داشته باشد، عدد تطابق و عدد پوشش یال، برابر یکیدیگر و هر دو برابر V|/2| است. اگر A و B هر دو تطابق ماکسیمال باشد همواره داریم: |A| ≤ 2|B| و |B| ≤ 2|A. برای اثبات، توجه کنید که چون B تطابق است، هر یال در A می تواند حداکثر با دو یال در B مجاور باشد.همچنین با توجه به بیشینه بودن تطابق، هر یال در B مجاور یک یال در A است.(این استدلال را می توان برای گراف Aهم به کار برد و به نتایج مشابه رسید). بنابراین خواهیم داشت:

$|A \setminus B| \le 2|B \setminus A|.$

بنابراین:

$|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.$

به طور خاص، نامساوی بالا نشان می دهد که هر تطابق ماکسیمال، 2 برابر تقریبی از تطابق بیشینه و همچنین 2 برابر تقریبی از کوچکترین تطابق ماکسیمال است.به عنوان مثال، اگر G یک مسیر با 3 یال و4 گره باشد، اندازۀ کوچکترین گراف تطابق ماکسیمال 1 است و سایز تظابق بیشینه 2 است.

چند جمله‌ای تطابق

تابع مولد تعداد تطابق‌های k یالی در یک گراف، چندجمله‌ای تطابق نامیده می‌شود.

فرض کنید G گرافی است که برای آن می‎خواهیم تعداد تطابق‌ها را پیدا کنیم و m_k، تعداد تطابق‎های k-یالی برای آن باشد. یکی از چند جمله‌ای های تطابق برای G، تابع مولد زیر است.

$\sum_{k\geq0} m_k x^k.$

تعریف دیگری، چندجمله‌ای تطابق دیگری را به صورت زیر می دهد:

$\sum_{k\geq0} (-1)^k m_k x^{n-2k},$

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

الگوریتم‌ها و پیچیدگی محاسباتی آنها

تطابق بیشینه در گراف های دو بخشی

اغلب اوقات مسئلۀ تطابق برای گراف دوبخشی مطرح می شود.شاید پیدا کردن یک تطابق دو بخشی بیشینه (که اغلب به آن تطابق دو بخشی با سایز بیشینه گفته می‌شود) در یک گراف دو بخشی( G = (V = (X,Y),E، ساده‌ترین مساله در قسمت تطابق باشد. الگوریتم مسیر افزایشی، در صورتی که بین هر راس مانند x ∈ X به هر راس مانند y مسیر اقزایشی وجود داشته باشد، آنرا پیدا می کند و به تطابق اضافه می کند. از آنجا که هر یک از این مسیرهای افزایش می تواند در زمان (O(E پیدا شود، زمان اجرا برای کل این الگوریتم از مرتبه ی (O(VE می شود. این راه حل معادل این است که یک منبع مانند s که به همۀ رئوس در X یال دارد و همچنین یک گودال مانند t که از همۀ رئوس در Y به آن یال وجود دارد، به گراف اضافه کنیم و سپس شار بیشینه را از s به t حساب کنیم. بااین کار، همۀ یال‌هایی که از X به Y جریان دارند، تطابق بیشینه را تشکیل می دهند.

این الگوریتم، در الگوریتم هاپ کرافت-کارپ ^*[۲])، بهبود داده شده‌است و می تواند در زمان $O( \sqrt{VE})$ اجرا شود.

راه حل دیگر برای پیدا کردن تطابق بیشینه در گراف دو بخشی، بر پایۀ الگوریتم ضرب سریع ماتریس هاست و دارای پیچیدگی زمانی $O(V^{2.376})$ است که از نطر تئوری برای گراف‌هایی که تا حد امکان فشرده هستند، کارآمد تر است.اما در عمل این الگوریتم کندتر است. در گراف دوبخشی وزن‌دار، هر یال دارای یک وزنی است که به آن نسبت داده شده است. تطابق بیشینۀ وزن‌دار برای گراف‌های دو بخشی، تطابق کاملی است که در آن مجموع مقادیر(وزن‌ها) روی یال‌های تطابق، بیشترین مقدار را داشته باشد.اگر گراف دو بخشی کامل نباشد، یال‌هایی که برای دوبخشی کامل شدن لازم است را با وزن 0 به گراف اضافه می کنیم. پیدا کردن این تطابق به مسالۀ انتساب مشهور است. این مساله را می توان با استفاده از روش اصلاح شدۀ یافتن کوتاه‌ترین مسیر در الگوریتم مسیر افزایشی، حل کرد.اگر از الگوریتم بلمن فورد استفاده کنیم، زمان اجرا، $O(V^2 E)$ می‌شود. اما چنانچه از الگوریتم دیکسترا و هیپ فیبوناتچی استفاده کنیم، زمان اجرا به $O(V^2 \log{V} + V E)$ کاهش می یابد. یک الگوریتم قابل توجه بلغاری، برای حل مسالۀ انتساب ارائه شده است که از نخستین الگوریتم‌های بهینه‌سازی ترکیبی بود. راه حل اصلی این الگوریتم، نیاز به زمان اجرای $O(V^2E)$ دارد اما با استفاده از صف اولویت، می توان زمان اجرای آن را به $O(V^2 \log{V} + V E)$ بهبود بخشید.

تطابق بیشینه

یک راه حل چند جمله‌ای برای پیدا کردن تطابق بیشینه و یا تطابق با وزن بیشینه در یک گراف غیر دوبخشی وجود دارد.این روش با توجه به jack Edmonds که بنیانگذار آن بود، روش راهها، درخت‌ها و گل‌ها یا به طور مختصر الگوریتم Edmonds نامگذاری شد. این الگوریتم از یال‌های دو سویه استفاده می کند. این الگوریتم متعاقبا بهبود بخشیده شد تا در زمان O(الگو:RadicalE) اجرا شود که از مرتبۀ زمان لازم برای پیدا کردن تطابق بیشینه در گراف‌های دو بخشی است. همچنین الگوریتم دیگری برای پیدا کردن تطابق ماکسیمال وجود دارد که بر پایۀ ضرب سریع ماتریس‌هاست و به الگوریتم Mucha و Sankowski مشهور است. اجرای این الگوریتم از مرتبۀ $O(V^{2.376})$ زمان می‌برد.

تطابق ماکسیمال

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

با این وجود هنوز هیچ الگوریتم چند جمله‌ای برای پیدا کردن کوچکترین گراف تطابق ماکسیمال که بزرگ‌ترین تطابق بیشینه با کمترین تعداد یال ممکن است، وجود ندارد.

توجه کنید که تطابق ماکسیمال با kیال، یک مجموعۀ غالب یال‌ها^*[۳]) با k یال است.در مقابل، اگر کوچک‌ترین مجموعۀ غالب یال‌ها با k یال را در اختیار داشته باشیم، می توان در زمان چند جمله‌ای تطابق ماکسیمال با k یال را ساخت. بنابراین مسالۀ یافتن کوچکترین گراف تطابق ماکسیمال، معادل مسالۀ یافتن کوچکترین مجموعۀ غالب یال‌هاست.هر دوی این مسائل بهینه سازی ان‌پی-سخت است.نسخه‌های تصمیم گیری از این مسائل، از جمله مثال‌های کلاسیک مسائل ان پی (کامل) هستند.هر دوی این مسائل را می توان تا جملۀ دوم در زمان چندجمله‌ای تقریب زد: پیدا کردن تطابق بیشینه دلخواه به سادگی.

مسالۀ شمارش

مسالۀ پیدا کردن تعداد تطابق‌های کامل برای بک گراف مساله‌ای #پی-کامل است.هر چند که نظریۀ قابل توجه Kasteleyn نشان می دهد که تعداد تطابق‌های بیشینه در یک گراف مسطح را می توان با استفاده از الگوریتم FKT دقیقا در زمان چند جمله‌ای محاسبه کرد. همچنین یک تقریب تصادفی اما چند جمله‌ای برای شمارش تعداد تطابق های دوبخشی وجود دارد.

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

منابع

• http://en.wikipedia.org/w/index.php?title=Matching_(graph_theory)&oldid=464266371)

جستارهای وابسته

• نظریه گراف
• الگوریتم حریصانه
• رنگ‌آمیزی گراف

پانویس

1. ^  Berge's lemma.
2. ^  Hopcroft-Karp algorithm
3. ^  Edge dominating set.