۰
subtitle
ارسال: #۱
  
بخش گراف: محاسبه ماکزیمم طول دور یک گراف
طول ماکسیمم را که یک پیگرد و یک مدار میتواند در (برای مثالK6)داشته باشد
وبابسط کلی در K2nکهnعضو اعداد صحیح باشد ،را چجوری باید محاسبه کنیم لطفا توضیح غیر فرمولی وتشریحی باشه ممنون میشم
وبابسط کلی در K2nکهnعضو اعداد صحیح باشد ،را چجوری باید محاسبه کنیم لطفا توضیح غیر فرمولی وتشریحی باشه ممنون میشم
۰
ارسال: #۲
  
RE: بخش گراف:
بزرگترین مدار و پیگردها ، مدار و پیگردهای اویلری هستند.
طول مدار و گذر اویلری برابر است با تعداد یال ها ی گراف اما وجود مدار و گذر اویلری در گراف یه سری شرایط داره که باید اون شرایط رو تو گرافمون مهیا کنیم.
اما می دانیم که برای گذر اویلری نیاز به دو راس با درجه فرد داریم و باید درجه سایر رئوس زوج باشد اما در گراف کامل k2n درجه همه رئوس ۲n-1 است. پس ما باید دو راس را با درجه ۲n-1 نگهداریم و با حذف یک سری یال ها از گرافمان درجه ی بقیه رئوس را به ۲n-2 برسانیم.
پس باید برای هر یک از ۲n-2 تا راس دیگر یکی از یال هایی که به اون راس وارد شده رو حذف کنیم تا درجه هر راس بشه ۲n-2 . ولی باید بدانیم که حذف هر یال در درجه ی دو راس تاثیر می ذاره پس نیازی به حذف ۲n-2 تا یال نیست و کافی ست نصف این تعداد یال حذف کنیم.
پس ما از کل یال ها که برابر بود با [tex]\binom{2k}{2}[/tex] تعداد [tex]\frac{1}{2}(2k-2)[/tex] یال رو حذف کردیم پس تعداد یال های باقی مانده برابر است با :
[tex]\binom{2k}{2}-\frac{1}{2}(2k-2)[/tex]
که همان طول گذر یا پیگرد اویلری ماست.
به طور مشابه برای داشتنمدار اویلری باید درجه رئوس همگی زوج باشد پس ما باید از هر راس یک یال حذف کنیم اما چون هر یال در درجه ی دو راس تاثیر گذارست به تعداد نصف رئوس یال حذف می کنیم پس تعداد یال های باقی مانده برابر است با [tex]\binom{2k}{2}-\frac{1}{2}(2k)[/tex] که همان طول مدار اویلری است
طول مدار و گذر اویلری برابر است با تعداد یال ها ی گراف اما وجود مدار و گذر اویلری در گراف یه سری شرایط داره که باید اون شرایط رو تو گرافمون مهیا کنیم.
اما می دانیم که برای گذر اویلری نیاز به دو راس با درجه فرد داریم و باید درجه سایر رئوس زوج باشد اما در گراف کامل k2n درجه همه رئوس ۲n-1 است. پس ما باید دو راس را با درجه ۲n-1 نگهداریم و با حذف یک سری یال ها از گرافمان درجه ی بقیه رئوس را به ۲n-2 برسانیم.
پس باید برای هر یک از ۲n-2 تا راس دیگر یکی از یال هایی که به اون راس وارد شده رو حذف کنیم تا درجه هر راس بشه ۲n-2 . ولی باید بدانیم که حذف هر یال در درجه ی دو راس تاثیر می ذاره پس نیازی به حذف ۲n-2 تا یال نیست و کافی ست نصف این تعداد یال حذف کنیم.
پس ما از کل یال ها که برابر بود با [tex]\binom{2k}{2}[/tex] تعداد [tex]\frac{1}{2}(2k-2)[/tex] یال رو حذف کردیم پس تعداد یال های باقی مانده برابر است با :
[tex]\binom{2k}{2}-\frac{1}{2}(2k-2)[/tex]
که همان طول گذر یا پیگرد اویلری ماست.
به طور مشابه برای داشتنمدار اویلری باید درجه رئوس همگی زوج باشد پس ما باید از هر راس یک یال حذف کنیم اما چون هر یال در درجه ی دو راس تاثیر گذارست به تعداد نصف رئوس یال حذف می کنیم پس تعداد یال های باقی مانده برابر است با [tex]\binom{2k}{2}-\frac{1}{2}(2k)[/tex] که همان طول مدار اویلری است
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close