تبلیغات
الف مثل المپیاد - سوال گراف
در این درگه که گه گه که که و که که شود ناگه/مشو غره به امروزت که از فردا نه ای آگه
درباره وبلاگ

آرشیو

طبقه بندی

آخرین پستها

پیوندها

پیوندهای روزانه

صفحات جانبی

نویسندگان

آمار وبلاگ


سلام
سه تا سوال گراف قشنگ دیدم تصمیم گرفتم بذارم این جا که یه کم از این سوت کوری هم در بیاد...
اولیش آسون تره دومیش هم واقعا سوال خوبیه سومیش هم از این سوالایی که حلش بهتون انزژی میده.

1) یک گراف را در نظر بگیرید در هر مرحله دو راس که مجموع درجه هایشان از n-1 بیشتر است و همسایه نیستند را انتخاب می کنیم و یک یال بین آنها قرار می دهیم .
نشان دهید که اگر گراف در ابتدا دور همیلتونی نداشته باشد در پایان کار هم نمی تواند دور همیلتونی داشته باشد.

2) گراف H را از رو G  که یک دور است این گونه می سازیم که برای هر مسیر در این دور یک راس در H قرار می دهیم و هر دو مسیری که در حداقل  یک یال در G  مشترک باشند را در H با یک یال به هم وصل می کنیم.
عدد رنگی H (رنگ آمیزی راسی) را به دست آورید و گفته خود را ثابت کنید.

3) یه بنده خدایی یه گراف رو برداشته به ازای هر کدوم از n تا راسش اون راس رو از گراف حذف کرده و از گرافه عکس گرفته حالا n تا عکس به شما میده و از شما دنباله گرافیکی گراف اصلی رو می خواد حالا باید بگید که چه جوری می شه این کارو کرد ؟

در ضمن عید همه تون هم پیشاپیش مبارک  انشاالله سال خیلی خیلی خوبی داشته باشید.
موفق باشید 


نوشته شده توسط :محمد مهدی طاهری
بیست و نهم اسفند 91-17:58