قضیه برژ

در نظریه گراف، قضیه برگه بیان می‌کند که یک تطابق (Matching) M از گراف G ماکسیمم است، اگر و تنها اگر مسیر M-افزوده(مسیری که یال‌هایش یکی در میان در تطابق باشد و همچنین اولین و آخرین یال هم جزء تطابق نباشد) نداشته باشیم. قضیه ایست که Claude Berge ریاضیدان فرانسوی در سال 1957 آن را به اثبات خود در آورد.

اثبات

ابتدا به اثبات طرف اول رابطه بالا می پردازیم: از برهان خلف استفاده کرده و فرض می کنیم که مسیر M-افزوده داشته باشیم و تطابق ماکسیمم باشد. به سادگی می‌توان گفت، در تطابق M از G با مسیر M-افزوده P، تطابق M` با تعداد یال‌های بیشتر وجود خواهد داشت به‌طوری‌که $M'=M\Delta \,P$

(یال‌هایی که دقیقاً یک بار در یکی از M و P آمده اند)

اثبات عکس رابطه نیز بدین صورت است: فرض کنید M' یک تطابق بزرگتر از تطابق M) M-افزوده ندارد) است. در نتیجه $M'\Delta \,M$

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

منابع

کتاب مقدمه‌ای بر نظریه گراف (نگارش دوم2)، نوشته دووگلاس بی وست.

http://en.wikipedia.org/wiki/Berge%27s_lemma