قضیه برژ

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از قضیه برگه)
پرش به: ناوبری، جستجو


در نظریه گراف، قضیه برگه بیان می‌کند که یک مچینگ 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' برابر استT در نتیجه مسیری وجود دارد که تعداد یال‌های آن از M' بیشتر از دیگری باشد که یک مسیر M-افزوده را نشان می دهد. تناقض

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

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

http://en.wikipedia.org/wiki/Berge's_lemma