ریاضیات

نمونه ای از نمودار دو بخشی ، با حداکثر تطبیق (آبی) و حداقل پوشش راس (قرمز) هر دو با اندازه شش.

در ریاضی منطقه از نظریه گراف ، نظریه کونیگ ، ثابت شده توسط دینش کونیگ  ( 1931 )، توصیف یک هم ارزی بین مسئله تطابق بیشینه  و حداقل مسئله پوشش راسی در گرافهای دوبخشی . آن را به طور مستقل ، همچنین در سال 1931 ، توسط Jenő Egerváry در مورد کلی تر از نمودارهای وزنی کشف شد .

فهرست

• 1تنظیمات
• 2بیان قضیه
  • 2.1مثال
• 3اثبات
  • 3.1اثبات سازنده
  • 3.2اثبات استفاده از دوگانه برنامه نویسی خطی
• 4الگوریتم
  • 4.1مثال
• 5نمودارهای غیر دو بخشی
• 6تاریخ
• 7قضیه های مرتبط
• 8اتصالات با نمودارهای عالی
• 9انواع توزین شده
  • 9.1قضیه اگوراری برای نمودارهای با وزن لبه
  • 9.2قضیه برای نمودارهای راس وزن
• 10همچنین ببینید
• 11یادداشت
• 12منابع

تنظیم [ ویرایش ]

پوشش راسی در یک گراف مجموعه ای از رئوس که شامل حداقل یک نقطه پایانی هر لبه است، و یک پوشش راسی است حداقل اگر بدون پوشش راس دیگر است راس کمتر. [1] تطبیق در یک گراف مجموعه ای از لبه بدون که دو به اشتراک گذاشتن یک نقطه پایانی است، و تطبیق است حداکثر اگر هیچ منطبق دیگر دارای لبه است. [2]

از تعریف بدیهی است که هر مجموعه پوشش راس باید حداقل به اندازه مجموعه مطابقت باشد (زیرا برای هر لبه تطبیق ، حداقل یک راس در پوشش لازم است). به طور خاص ، حداقل مجموعه پوشش راس حداقل به اندازه مجموعه حداکثر تطبیق بزرگ است . قضیه Kőnig بیان می کند که ، در هر نمودار دو بخشی ، حداقل مجموعه پوشش راس و حداکثر مجموعه تطبیق در واقع همان اندازه هستند. [3]

بیان قضیه [ ویرایش ]

در هر نمودار دو بخشی ، تعداد لبه ها در حداکثر تطبیق برابر است با تعداد رئوس در حداقل پوشش راس . [3]

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

نمودار دو بخشی نشان داده شده در تصویر بالا دارای 14 رئوس است. یک تطبیق با شش لبه با رنگ آبی نشان داده شده است ، و یک راس با شش رئوس با قرمز نشان داده شده است. هیچ پوشش راس کوچکتری وجود ندارد ، زیرا هر پوشش راس باید حداقل یک نقطه انتهایی از هر لبه همسان (و همچنین از هر لبه دیگر) را شامل شود ، بنابراین این حداقل پوشش راس است. به همین ترتیب ، هیچ تطابق بزرگتری وجود ندارد ، زیرا هر لبه همسان باید حداقل یک نقطه انتهایی را در پوشش راس شامل شود ، بنابراین این حداکثر تطبیق است. قضیه Kőnig می گوید که برابری بین اندازه های تطبیق و پوشش (در این مثال ، هر دو عدد شش است) به طور کلی برای هر نمودار دو بخشی اعمال می شود.

اثبات [ ویرایش ]

اثبات سازنده [ ویرایش ]

اثبات زیر راهی برای ساخت حداقل پوشش راس از حداکثر تطبیق ارائه می دهد. اجازه دهید یک نمودار دو بخشی باشید و اجازه دهید  دو قسمت از مجموعه راس باشد. فرض کنید که حداکثر تطبیق برای . هیچ راس در یک راس نمی تواند بیش از یک لبه را پوشش دهد (زیرا نیمه همپوشانی لبه مانع می شود  از یک تطبیق (در وهله اول) ، بنابراین اگر یک راس با رئوس می تواند ساخته شود ، باید حداقل پوشش باشد. [4]

برای ساخت چنین پوششی ، اجازه دهید  مجموعه راسهای بی همتا در باشد  (احتمالاً خالی است) ، و بگذارید مجموعه رأسهایی است که در داخل هستند  یا به آن متصل هستند با مسیرهای متناوب (مسیرهایی که بین لبه هایی که در تطبیق هستند و لبه هایی که در تطبیق نیستند متناوب هستند). اجازه دهید

هر لبه  که در  یا به یک مسیر متناوب تعلق دارد (و دارای یک نقطه پایانی مناسب در است ) ، یا یک نقطه پایانی سمت چپ در دارد . برای ، اگر مطابقت دارد اما در یک مسیر متناوب نیست ، پس نقطه انتهایی سمت چپ آن نمی تواند در یک مسیر متناوب باشد (زیرا دو لبه همسان نمی توانند یک راس را به اشتراک بگذارند) و بنابراین متعلق به . متناوباً ، اگر غیرقابل مقایسه است اما در یک مسیر متناوب نیست ، پس نقطه انتهایی سمت چپ آن نمی تواند در یک مسیر متناوب باشد ، زیرا چنین مسیری را می توان با اضافه کردن به آن بدین ترتیب،یک پوشش راس تشکیل می دهد. [5]

علاوه بر این ، هر راس در یک نقطه انتهایی یک لبه همسان است. برای ، هر راس در مطابقت دارد زیرا  فوق العاده است از ، مجموعه رئوس چپ بی همتا. و هر راس درهمچنین باید مطابقت داده شود ، زیرا اگر یک مسیر متناوب به یک راس بی همتا وجود داشته باشد ، تغییر مطابقت با حذف لبه های همسان از این مسیر و اضافه کردن لبه های بی همتا در محل آنها ، اندازه مطابقت را افزایش می دهد. با این حال ، هیچ لبه همسان نمی تواند هر دو نقطه انتهایی خود را داشته باشد. بدین ترتیب، یک پوشش راس از کاردینالیت برابر است با ، و باید حداقل پوشش راس باشد. [5]

اثبات استفاده از دوگانه برنامه ریزی خطی [ ویرایش ]

برای توضیح این اثبات ، ابتدا باید مفهوم تطبیق را به مفهوم تطبیق کسری گسترش دهیم - تخصیص وزن در [0،1] به هر لبه ، به گونه ای که مجموع وزن نزدیک هر راس حداکثر 1 باشد (تطبیق انتگرال یک مورد خاص از تطبیق کسری است که در آن وزنها در {0،1} قرار دارند). به همین ترتیب ما یک پوشش راس کسری تعریف می کنیم - اختصاص یک وزن غیر منفی به هر راس ، به این ترتیب که مجموع وزنها در هر لبه حداقل 1 است (پوشش راس انتگرال یک مورد خاص از یک راس کسری است که در آن وزنها در {0،1} قرار دارند).

حداکثر اندازه تطبیق کسری در نمودار راه حل برنامه خطی زیر است :

1 E · x را به حداکثر برسانید

موضوع: x ≥ 0 E

__________ G · X ≤ 1 V .

که در آن x یک بردار از اندازه است | E | که در آن هر عنصر نشان دهنده وزن یک لبه در تطبیق کسری است. 1 E یک بردار از | است E | یکی ، بنابراین خط اول اندازه مطابقت را نشان می دهد. 0 E یک بردار از | است E | صفر ، بنابراین خط دوم نشان دهنده این است که وزن منفی نیست. 1 V بردار از | است V | آنهایی که و G است ماتریس وقوع از G، بنابراین خط سوم این محدودیت را نشان می دهد که مجموع وزنهای نزدیک به هر راس حداکثر 1 باشد. به همین ترتیب ، حداقل اندازه پوششی راس کسری در  راه حل LP زیر است:

به حداقل رساندن 1 V · Y

موضوع: y ≥ 0 ولت

__________ G T · Y ≥ 1 E .

که y بردار اندازه است | V | که در آن هر عنصر نشان دهنده وزن یک راس در پوشش کسری است. در اینجا ، خط اول اندازه پوشش است ، خط دوم نشان دهنده منفی نبودن وزن ها و خط سوم نشان دهنده این الزام است که مجموع وزن های نزدیک به هر لبه باید حداقل 1 باشد. اکنون ، حداقل کسری cover LP دقیقاً برنامه دو خطی حداکثر تطبیق کسری LP است. بنابراین ، با توجه به قضیه دوگانگی LP ، هر دو برنامه راه حل یکسانی دارند. این واقعیت نه تنها در نمودارهای دو بخشی بلکه در نمودارهای دلخواه صادق است:

در هر نمودار ، بزرگترین اندازه یک تطبیق کسری برابر است با کوچکترین اندازه یک راس کسری.

آنچه نمودارهای دوتکه را خاص می کند این است که در نمودارهای دوتکه ، هر دو برنامه خطی دارای راه حل های بهینه هستند که در آنها تمام مقادیر متغیر به صورت عدد صحیح هستند. این از این واقعیت ناشی می شود که در پلی استوپ تطبیق کسری نمودار دو بخشی ، تمام نقاط شدید فقط مختصات عدد صحیح را دارند ، و همین امر برای پلی استوپ پوششی راس کسری نیز صادق است. بنابراین قضیه فوق دلالت دارد: [6] : 270

در هر نمودار دو بخشی ، بزرگترین اندازه تطبیق برابر است با کوچکترین اندازه پوشش راس.

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

اثبات سازنده ای که در بالا توضیح داده شد ، الگوریتمی برای تولید حداقل پوشش راس با حداکثر مطابقت ارائه می دهد. بنابراین ، از الگوریتم Hopcroft – Karp برای یافتن حداکثر تطابق در نمودارهای دو بخشی نیز ممکن است برای حل کارآمد مسئله پوشش راس در این نمودارها استفاده شود. [7]

با وجود معادل سازی دو مسئله از نظر راه حل های دقیق ، آنها برای الگوریتم های تقریب معادل نیستند . حداکثر تطابق دو طرفه را می توان به دلخواه و در زمان ثابت با الگوریتم های توزیع شده تقریبی داد . در مقابل ، تقریب حداقل پوشش راس یک نمودار دو بخشی حداقل به زمان لگاریتمی نیاز دارد. [8]

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

در نمودار نشان داده شده در مقدمه ،  به مجموعه رئوس در لایه پایین نمودار و مجموعه راسها در لایه بالایی نمودار است. از چپ به راست رئوس لایه پایین را با اعداد 1 ،… ، 7 برچسب بزنید و رئوس را در لایه بالایی با اعداد 8 ،… ، 14 برچسب بزنید. از رئوس بی همتا از {1} است. مسیرهای متناوب از 1–10–3–13–7 ، 1–10–3–11–5–13–7 ، 1–11–5–13–7 ، 1–11–5–10–3–13–7 ، و تمام زیر مسیرهای این از 1 شروع می شود  بنابراین {1،3،5،7،10،11،13} است ، در نتیجه ،  و حداقل پوشش راس .

نمودارهای غیر دو طرفه [ ویرایش ]

برای نمودارهایی که دو بخشی نیستند ، حداقل پوشش راس ممکن است از حداکثر تطبیق بزرگتر باشد. علاوه بر این ، دو مشکل از نظر پیچیدگی بسیار متفاوت هستند: حداکثر مطابقت را می توان در زمان چند جمله ای برای هر نمودار یافت ، در حالی که حداقل پوشش راس NP کامل است .

مکمل پوشش راس در هر نمودار یک مجموعه مستقل است ، بنابراین حداقل پوشش راس مکمل یک مجموعه حداکثر مستقل است. یافتن حداکثر مجموعه های مستقل یکی دیگر از مشکلات کامل NP است. معادل سازی بین تطبیق و پوشش بیان شده در قضیه Kőnig اجازه می دهد تا حداقل پوشش های راس و حداکثر مجموعه های مستقل در زمان چند جمله ای برای نمودارهای دو بخشی محاسبه شود ، علی رغم NP کامل بودن این مشکلات برای خانواده های نمودارهای عمومی تر. [9]

تاریخچه [ ویرایش ]

قضیه کونیگ به نام ریاضیدان مجارستانی Dénes Kőnig نامگذاری شده است . کونیگ در سال 1914 اعلام کرده و در سال 1916 نتایج را منتشر کرده است که هر نمودار منظم دو بخشی دارای یک تطابق کامل است ، [10] و به طور کلی شاخص رنگی هر نمودار دو بخشی (یعنی حداقل تعداد مطابقت هایی که می توان در آن تقسیم شود) ) برابر است با حداکثر درجه آن [11] - جمله اخیر به عنوان قضیه رنگ آمیزی خط Kőnig شناخته می شود . [6] : قضیه 1.4.17 ، صص 37 به بعد. با این حال ، بوندی و مورتی (1976) قضیه کنیگ را به مقاله بعدی کنیگ (1931) نسبت می دهند.

طبق گفته های بیگز ، لوید و ویلسون (1976) ، كونیگ ایده مطالعه تطابق را در نمودارهای دو بخشی به پدرش ، ریاضیدان گیولا كونیگ نسبت داد . به مجارستانی، نام KONIG دارای لهجه حاد دو ، اما او قضیه است که معمولا در شخصیت آلمان املای، با ادغام دو حرف صدادار .

قضیه های مرتبط [ ویرایش ]

نظریه کونیگ معادل دیگر قضایای MIN-MAX متعدد در نظریه گراف و ترکیبیات، مانند قضیه هال و نظریه دیلورث . از آنجا که تطبیق دو بخشی مورد خاصی از حداکثر جریان است ، قضیه نیز از قضیه حداکثر جریان برش حداقل حاصل می شود . [12]

اتصالات با نمودارهای کامل [ ویرایش ]

اگر در هر زیرگراف القایی ، عدد رنگی برابر با بزرگترین دسته باشد ، یک نمودار کامل می شود . هر نمودار دو بخشی کامل است ، [13] زیرا هر یک از زیرگرافهای آن دو بخشی یا مستقل است. در یک نمودار دو بخشی که مستقل نباشد ، تعداد رنگی و اندازه بزرگترین دسته هر دو دو هستند در حالی که در یک مجموعه مستقل ، عدد رنگی و تعداد دسته هر دو یکی هستند.

یک نمودار کامل است اگر و فقط اگر مکمل آن کامل باشد ، [14] و قضیه Kőnig را می توان معادل این جمله دانست که مکمل یک نمودار دو بخشی کامل است. زیرا ، هر کلاس رنگی در رنگ آمیزی مکمل یک نمودار دو بخشی حداکثر دارای اندازه 2 و کلاسهای اندازه 2 نیز مطابقت دارند ، یک دسته در مکمل نمودار G یک مجموعه مستقل در G است ، و همانطور که ما قبلاً یک مجموعه مستقل را در یک نمودار دو بخشی توصیف کرده ایم G یک مکمل از یک راس در G است . بنابراین ، هر تطبیق M در نمودار G دو بخشی G با n رئوس مربوط به رنگ آمیزی مکمل G استبا n - | م | رنگها ، که با کمال مکمل نمودارهای دو بخشی مربوط به یک مجموعه مستقل در G با n - | م | رئوس ، که مربوط به یک راس پوشش G با رئوس M است . برعکس ، قضیه کونیگ کمال مکمل های نمودارهای دو بخشی را اثبات می کند ، نتیجه ای که توسط Gallai (1958) به شکل واضح تری ثابت شده است .

همچنین می توان قضیه رنگ آمیزی Kőnig را به کلاس متفاوتی از نمودارهای کامل ، نمودارهای نمودارهای نمودارهای دو بخشی متصل کرد. اگر G یک گراف، نمودار خط L ( G ) است یک راس برای هر لبه G و یک لبه برای هر جفت از لبه های مجاور در G . بنابراین ، عدد رنگی L ( G ) برابر با شاخص رنگی G است . اگر G دو بخشی باشد ، کلیک های موجود در L ( G ) دقیقاً مجموعه لبه های G هستنداشتراک یک نقطه پایان مشترک اکنون قضیه رنگ آمیزی Kőnig ، با بیان اینکه شاخص رنگی برابر است با حداکثر درجه راس در هر نمودار دو بخشی ، می تواند به این معنی باشد که نمودار خط یک نمودار دو بخشی کامل است. [15]

از آنجا که نمودارهای خطی نمودارهای دو بخشی کامل هستند ، مکمل نمودارهای نمودارهای دو بخشی نیز عالی هستند. یک کلیک در مکمل نمودار خط G فقط مطابقت در G است . و یک رنگ آمیزی در نمودار نمودار G ، وقتی G دو بخشی است ، یک قسمت از لبه های G به زیر مجموعه های لبه ها است که یک نقطه انتهایی مشترک دارند. نقاط انتهایی به اشتراک گذاشته شده توسط هر یک از این زیر مجموعه ها یک راس راس برای G تشکیل می دهند . بنابراین ، قضیه Kőnig نیز می تواند به این معنا باشد که مکمل نمودارهای خطی نمودارهای دو بخشی کامل هستند. [15]

انواع توزین شده [ ویرایش ]

قضیه کونیگ را می توان به نمودارهای وزنی گسترش داد .

قضیه ایگوراری برای نمودارهای با وزن لبه [ ویرایش ]

دیگه Jenő Egerváry (1931) در نظر گرفته نمودار که در آن هر لبه الکترونیکی دارای وزن عدد صحیح غیر منفی W الکترونیکی . بردار وزن با w نشان داده می شود . W- وزن یک تطبیق مجموع وزن از لبه های شرکت کننده در تطبیق است. W- راس پوشش های MultiSet از رئوس ( "MultiSet به" بدان معنی است که هر راس ممکن است چندین بار به نظر می رسد)، که در آن هر یک از لبه است الکترونیکی مجاور به حداقل است W الکترونیکی راس. قضیه ایگوراری می گوید:

در هر نمودار دو طرفه با وزن لبه ، حداکثر وزن w تطبیق برابر است با کمترین تعداد رئوس در یک پوشش vertex w .

حداکثر وزن W تطبیق کسری توسط LP آورده می شود: [6] : 271

حداکثر w · x

موضوع: x ≥ 0 E

__________ G · X ≤ 1 V .

و حداقل تعداد رأس در یک پوشش راس W کسری توسط LP دوتایی داده می شود:

به حداقل رساندن 1 V · Y

موضوع: y ≥ 0 ولت

__________ A G T · y ≥ w .

همانطور که در اثبات قضیه کونیگ ، قضیه دوگانگی LP به این معنی است که مقادیر بهینه برابر هستند (برای هر نمودار) ، و دو بخشی بودن نمودار نشان می دهد که این برنامه ها دارای راه حل های بهینه هستند که تمام مقادیر به صورت عدد صحیح هستند.

قضیه نمودارهای راس وزن [ ویرایش ]

می توان گرافی را در نظر گرفت که در آن هر راس v دارای یک عدد صحیح غیر منفی b v باشد. بردار وزن با b نشان داده می شود . ب وزن از یک راس پوشش مجموع است ب V برای همه V در پوشش. ب -matching انتساب یک وزن جدایی ناپذیر غیر منفی به هر یک از لبه است، به طوری که مجموع وزن از لبه مجاور به هر راس V حداکثر ب V . قضیه اگرگاری را می توان با استفاده از یک استدلال مشابه به نمودارهایی گسترش داد که هم دارای وزن لبه w و هم راس b هستند : [6]: 271

در هر گراف دو بخشی راس-وزن لبه وزن، حداکثر W- وزن یک ب -matching برابر حداقل ب وزن از رئوس در یک W- راس پوشش.

همچنین به [ ویرایش ] مراجعه کنید

• دارایی Kőnig در هایپراگراف

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)