زمان کنونی: ۲۵ شهریور ۱۳۹۸, ۱۲:۳۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بخش گراف: محاسبه ماکزیمم طول دور یک گراف

ارسال:
  

ashena1 پرسیده:

Tongue بخش گراف: محاسبه ماکزیمم طول دور یک گراف

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

۰
ارسال:
  

fatemeh69 پاسخ داده:

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] که همان طول مدار اویلری است



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال : گسسته - گراف - قضیه اویلر Morris ۲ ۱,۹۸۷ ۱۳ مرداد ۱۳۹۳ ۰۹:۴۸ ب.ظ
آخرین ارسال: Morris
  سوال تعداد مسیرها در یک گراف دوبخشی amir2930 ۱ ۱,۲۱۸ ۱۳ مرداد ۱۳۹۳ ۰۷:۳۳ ب.ظ
آخرین ارسال: Morris
  گردایه ای همه ی رشته های به طول ۱۰ Doctorwho ۱ ۶۹۰ ۱۶ تیر ۱۳۹۳ ۰۳:۱۷ ق.ظ
آخرین ارسال: Jooybari
  نامساوی در گراف با دوری به طول ۵ amir2930 ۳ ۱,۲۴۱ ۲۷ خرداد ۱۳۹۳ ۰۸:۲۰ ق.ظ
آخرین ارسال: amir2930
  سوال تعداد یالهای گراف amir2930 ۴ ۱,۴۲۸ ۲۶ خرداد ۱۳۹۳ ۰۱:۳۹ ب.ظ
آخرین ارسال: amir2930
  سوال زوج مرتب در گراف همبند amir2930 ۴ ۱,۱۵۱ ۲۶ خرداد ۱۳۹۳ ۱۰:۰۰ ق.ظ
آخرین ارسال: amir2930
  سوال افراز گراف به مثلث amir2930 ۱ ۹۶۲ ۲۵ خرداد ۱۳۹۳ ۰۳:۴۰ ب.ظ
آخرین ارسال: Jooybari
  سوال از تطابق در گراف دوبخشی amir2930 ۳ ۱,۲۸۳ ۲۴ خرداد ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: Jooybari
  محاسبه لگاریتم ۱۲۳۴۵//////۲۹۳۰ ana9940 ۷ ۱,۵۲۲ ۱۹ خرداد ۱۳۹۳ ۰۹:۳۳ ق.ظ
آخرین ارسال: ana9940
  تست گسسته موضوع گراف hana.rahmati ۱ ۱,۰۲۸ ۲۰ اسفند ۱۳۹۲ ۰۳:۱۲ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close