تالار گفتمان مانشت
بخش گراف: محاسبه ماکزیمم طول دور یک گراف - نسخه‌ی قابل چاپ

بخش گراف: محاسبه ماکزیمم طول دور یک گراف - ashena1 - 04 شهریور ۱۳۹۳ ۱۲:۱۹ ق.ظ

طول ماکسیمم را که یک پیگرد و یک مدار میتواند در (برای مثالK6)داشته باشد
وبابسط کلی در K2nکهnعضو اعداد صحیح باشد ،را چجوری باید محاسبه کنیم لطفا توضیح غیر فرمولی وتشریحی باشه ممنون میشمSmile

RE: بخش گراف: - fatemeh69 - 04 شهریور ۱۳۹۳ ۰۵:۰۷ ب.ظ

بزرگترین مدار و پیگردها ، مدار و پیگردهای اویلری هستند.
طول مدار و گذر اویلری برابر است با تعداد یال ها ی گراف اما وجود مدار و گذر اویلری در گراف یه سری شرایط داره که باید اون شرایط رو تو گرافمون مهیا کنیم.
اما می دانیم که برای گذر اویلری نیاز به دو راس با درجه فرد داریم و باید درجه سایر رئوس زوج باشد اما در گراف کامل 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] که همان طول مدار اویلری است