سلام... کی میتونه این موضوع رو اثبات کنه که اگه مجموع بزرگترین و کوچکترین درجه در یک گراف از حاصل تعداد رئوس منهای 2 بزرگتر باشه اون گراف همبنده؟؟
در مورد سوال اول باید بگم حتمأ این موضوع درست نیست مثال نقضشم یه گراف به شکل پنج ضلعیه که مجموع بزرگترین درجه و کوچکترین درجه میشه 2+2 یعنی 4 که از 5 کوچکتره ولی همبنده.
2015-09-04 04:28:06 -0600 شجاعی فرولی فک کنم دوتا سوال گذاشته بودین :| که من برا اویش مثال نقض دادم.... . :|
2015-09-04 07:28:40 -0600 شجاعی فرسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:02:56 -0600 امیر شکریسلام
اثبات این موضوع زیاد سخت نیست ، دو راس مینیممم و ماکسیمم رو در نظر بگیرید به غیر از این دو راس ما $n-2$ راس دیگر داریم ولی مجموع درجه این دو راس بیشتر مساوی $n-1$ است پس یا بین این دو راس یال داریم ، یا طبق اصل لانه کبوتری راسی وجود دارد که به هردو آنها ( یعنی 2 راس مینیمم و ماکسیمم ) راه دارد ، به این ترتیب می توانید برای هر راس دلخواه و راس ماکسیمم این استدلال را بکنید و نتیجه بگیرید همه رئوس به راس ماکسیمم راه (که یا شامل 1 یال است یا مسیری وجود دارد ) دارند پس گراف همبند است .
