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

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

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  ازدواج دور از جوانان، جوانان دور از ازدواج (هرچه می خواهد دل تنگت بگو...) morweb ۲,۶۹۵ ۶۱۷,۰۴۹ ۲۱ مرداد ۱۴۰۲ ۰۷:۴۴ ب.ظ
آخرین ارسال: gogooli
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۹۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مصاحبه دکتری- بخش تدریس wskf ۱ ۲,۳۹۲ ۲۸ فروردین ۱۳۹۹ ۰۴:۳۰ ب.ظ
آخرین ارسال: Masoud05
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۸۹۹ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۱,۸۱۵ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۸۰,۰۱۱ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۲,۲۹۹ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux
  طراحی گرافیکی simaakbari ۰ ۲,۲۵۰ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  کوتاه ترین مسیر در گراف Sanazzz ۳ ۳,۶۵۳ ۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ
آخرین ارسال: Sanazzz
  تقسیم برای محاسبه کد افزونه چرخشی (CRC) Sanazzz ۴ ۶,۱۷۶ ۲۰ آذر ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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