ثابت کنین اگر در گرافی مجموع بزرگترین و کوچکترین درجه از حاصل تعداد رئوس منهای 2 بیشتر باشه میتونیم نتیجه بگیریم که اون گراف همبنده اما الزاما عکس اون صحیح نیست...
سلام
لطفا عنوان سوالو درست کن، عنوان باید یه چیزی باشه که گویای سوال باشه
2015-09-05 12:00:23 -0600 توفیقیسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:02:15 -0600 امیر شکریبا استقرا روی تعداد رئوس حکم رو اثبات میکنیم.
راستی تعداد رئوس رو هم n میگیریم.
قبلش میپذیریم که برای n > 1 اگر راسی با درجه صفر وجود داشته باشه مجموع بزرگترین و کوچکترین درجه حداکثر n - 2 هست. (اثباتش به عهده خودتون)
پس ما در کل اثبات (به جز پایه) فرض میگیریم درجه هر راس حداقل 1 هست
پایه n=1 که مجموع بزرگترین و کوچکترین درجه 0 و تعداد رئوس منهای دو برابر -1 هست و گراف همبنده.
فرض کنیم برای تمام گراف های n راسی حکم درسته یه گراف n + 1 راسی در نظر بگیر که مجموع بزرگترین و کوچکترین درجه بزرگتر از تعداد رئوس منهای 2 باشه و راس دلخواه x رو توش در نظر بگیر. حالا به ازای هر دو راس مانند y و z که به x متصلند یال yz رو در صورت عدم وجود رسم میکنیم. حالا راس x رو حذف میکنیم. با این کار از مجموع بزرگترین و کوچکترین درجه حداکثر یک واحد کم میشه (چون اگه هر دوشون به x متصل بودند یک یال بینشون گذاشته بودیم) و از تعداد رئوس هم یک واحد کم میشه بنابراین شرایط فرض استقرا برقراره و گرافی که به وجود آوردیم با حذف راس x همبند هست. حالا اگه گراف رو به حالت اولیه برگردونیم همه ی مسیرهای قبلی وجود داره (اینم نیاز به اثبات داره ولی خیلی راحته دیگه!) و همچنین درجه x حداقل یک هست پس از x به بقیه هم مسیر وجود داره و کل گراف همبنده.
