به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
569 بازدید
در دبیرستان و دانشگاه توسط OXIDE

ثابت کنید در یک گراف ساده، اگر $q>C(p-1,2)$ آنگاه همبند است و اگر $ q < p-1 $ ناهمبند است همچنین اگر $q \geq p$ حداقل یک دور دارد خصوصا اگر در گراف همبندی $q=p-1$ دور ندارد و اگر $q=p$ دقیقا یک دور دارد.

توسط erfanm
در فرض سوال تعداد رئوس برابر $p$ گرفته شده؟

آیا منظور از $C(p-1,2)$ همان ${p-1 \choose{2} }$ است؟
توسط OXIDE
+1
بله همان است منتها شیوه این گونه نوشتن را نمیدانم اگر توضیح دهید ممنون میشوم
توسط erfanm
از دستور {p \choose{2 برای نمایش ${p \choose{2} }$ استفاده میکنیم منتها باید درون دو تا دلار فرمول را بنویسیم

2 پاسخ

+1 امتیاز
توسط OXIDE
انتخاب شده توسط OXIDE
 
بهترین پاسخ

برای این یه اثبات شهودی دارم:

ابتدا میخواهیم برای گراف ناهمبند اندازه را ماکزیمم کنیم یک راس را کنار گذاشته و با $p-1$ راس دیگر گراف کامل میسازیم.در نتیجه اگر اندازه گرافی از این مقدار یعنی $p-1 \choose{2}$ بیشتر باشد همبند میشود. میدانیم درخت گراف همبندی است که دور ندارد. با استقرا ثابت میشود در یک درخت $q=p-1$ . از تعریف درخت بلافاصله نتیجه میشود بین هر دو راس درخت دقیقا یک مسیر وجود دارد حال اگر در درخت بین دو راس مشخص یال برداریم بین آن دو درخت مسیری باقی نمی ماند درنتیجه ناهمبند میشود. برای این که گراف فاقد دور، بیشترین اندازه را داشته باشد باید درخت باشد(چرا؟) در نتیجه با افزودن یک یال یک دور به وجود می آید.(چرا؟) حال اگر گراف، درخت نباشد دور بیشتری میتواند به وجود بیاید یا قبلا دور داشته باشد. $ \Delta $

+1 امتیاز
توسط erfanm
ویرایش شده توسط erfanm

فرض کنید که $q > {p-1 \choose{2} }$ از برهان خلف حکم را ثابت میکنیم فرض کنید گراف نا همبند باشد و $ G_{1} , G_{2} ,.., G_{r} $ مولفه های همبندی باشند پس $V(G)=V( G_{1})+V(G_{2})+...+V(G_{r}) $

زمانی گراف دارای بیشترین یال است که تک تک مولفه های همبندی یک گراف کامل باشندو در این حالت تعداد یالهابرابر می شود با ${V( G_{1}) \choose{2} } +{V( G_{2}) \choose{2} }+...+{V( G_{r}) \choose{2} } $ و به راحتی با استقرا می توان نشان داد که ${V( G_{1}) \choose{2} } +{V( G_{2}) \choose{2} }+...+{V( G_{r}) \choose{2} } < {V( G) \choose{2} }$و این تناقض است با فرض مساله

با استقرا حکم را ثابت می کنیم یعنی نشان میدهیم اگر گرافی همبند باشد آنگاه $q \geq p-1$

پایه استقرا: فرض کنیم که گرافی همبند با دو راس باشد چون گراف همبند است لذا بین این دو راس یک یال داریم.

حال فرض کنید که حکم برای هر گراف همبند با $k $ راس درست باشد نشان میدهیم حکم برای هر گراف همبند با $ k+1$ راس نیز برقرار است

فرض کنید گراف همبند $ k+1$ راس داشته باشد اگر زیر گراف با $ k$ راس دلخواه را در نظر بگیریم طبق فرض استقرا تعداد یالها بزرگتر مساوی با $k-1$ است و راس $ k+1$ ام را همراه زیر گراف در نظر میگیریم اگر یالی بین این دو وجود نداشته باشد گراف اولیه ناهمبند خواهد شد اما طبق فرض همبند است لذا حداقل راس $ k+1$ ام با یک راس از زیر گراف یالی تشکیل میدهد پس تعدادیال ها ی گراف حداقل $k $است و این حکم را ثابت میکند.

نشان میدهیم که اگر $q=p-1$ آنگاه گراف دارای دور نیست. از برهان خلف کمک میگیریم فرض کنید دارای دور باشد آنگاه بین دو راس دو مسیر متفاوت داریم که اگر یکی از یالهای یکی از مسیرها را حذف کنیم گراف باز همبند خواهد ماند و در گراف حاصل داریم $q=p-2 < p-1 $ اما طبق قسمت قبل گرافی با این خاصیت ناهمبند است و این تناقض است.

برای قسمت آخر چون گراف همبند است اگر دور نداشته باشد آنگاه گراف یک درخت خواهد شد و در درخت داریم $q=p-1 $ اما چون در اینجا $q=p $ لذا باید دور داشته باشد پس بین دو راس دو مسیر متفاوت داریم اگر یکی از یالها را حذف کنیم(از یکی از مسیرها) آنگاه $ q=p-1 $ پس طبق قسمت قبل دوری دیگر نداریم.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...