تمرینات سری سوم (ترم 2-96-95)

تاریخ تحویل : 10 اردیبهشت ماه

(26) 1.2.3 (راهنمایی : گراف یالی G را در نظر بگیرید.)

(27) 2.2.3

(28) 6.2.3 (راهنمایی : دو راس x و y را به رئوس گراف اضافه کنید. اولی را به رئوس X و دومی را به رئوس Y وصل کنید. حال ثابت کنید گراف جدید 2-همبند است.)

(29) 4.1.4 (راهنمایی : از گشت بسته اویلری استفاده کنید.)

(30) جند درخت فراگیر در گراف کامل n رأسی وجود دارد که از یال e نمیگذرد؟ (راهنمایی : آنهایی که شامل این یال هستند بشمارید. البته تو کلاس این کار را انجام دادیم!)

(31) تعداد درختهای فراگیر گراف کامل دوبخشی K_2,n را بدست آورید. (راهنمایی : توجه کنید که دقیقا یک راس از بخش n تایی به هر دو راس بخش 2 تایی وصل است.)

(32) در گراف همبند G، راس v راسی از درجه یک در هر درخت فراگیر است. ثابت کنید درجه این راس در G نیز برابر است با یک. (راهنمایی : از برهان خلف استفاده کنید.)

(33) ثابت کنید یال e یک یال برشی است اگر و تنها اگر e روی هر درخت فراگیر G باشد. (راهنمایی : از قضیه 3.2 در صفحه 34 استفاده کنید.)

(34) یک گراف 2-همبند از مرتبه n حداقل چند یال دارد؟ ادعای خود را ثابت کنید. (راهنمایی : حل مساله از راهنمایی کردن ساده تر است!)

(35) ثابت کنید عدد همبندی راسی و یالی ابرمکعب Qn برابر است با n. (راهنمایی : با توجه به قضیه 1.3 در صفحه 52 کافی است ثابت کنید عدد همبندی راسی برابر است با n. برای هر دو راس دلخواه نشان دهید د مسیر درون مجزا وجود دارد.)

شماره های رنگی تمرین های تحویلی و بقیه پیشنهادی هستند که در آزمونها استفاده خواهند شد.

+ نوشته شده در یکشنبه بیست و هفتم فروردین ۱۳۹۶ساعت 10:52 توسط |