نمایش مبدأ برای قضیه برژ

{{ویکی‌سازی}}

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

== اثبات ==
ابتدا به اثبات طرف اول رابطه بالا می پردازیم: از [[برهان خلف]] استفاده کرده و فرض می کنیم که مسیر M-افزوده داشته باشیم و تطابق ماکسیمم باشد. به سادگی می‌توان گفت، در  تطابق M از G با مسیر M-افزوده P،  تطابق M` با تعداد یال‌های بیشتر وجود خواهد داشت به‌طوری‌که <math> M'=M\Delta\,P </math> (یال‌هایی که دقیقاً یک بار در یکی از M و P آمده اند)

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

== منابع ==
{{پانویس}}
کتاب مقدمه‌ای بر [[نظریه گراف]] (نگارش دوم2)، نوشته دووگلاس بی وست.

http://en.wikipedia.org/wiki/Berge%27s_lemma
[[رده:تطابق]]
[[رده:لم‌ها]]
[[رده:قضیه‌ها در نظریه گراف]]