.::ماراتن گراف::.
اوّلا من نگفتم که نظر من اینه.
دوّما این که استاد گودرز ( دی ) راهنمایی می ذارند باعث می شه مغز بقیه قوی بشه ؟!!!!!!! ( مغز بیشتر در جهت یافتن راهنمایی ها قوی می شه)
سوما بحث داره شدیدا منحرف می شه. اگه می خواید یه پست راجع یه همین بذارید. ولی دیگه تو اینجا ادامه ندیم.
نمی دونستم. ممنون
دوّما این که استاد گودرز ( دی ) راهنمایی می ذارند باعث می شه مغز بقیه قوی بشه ؟!!!!!!! ( مغز بیشتر در جهت یافتن راهنمایی ها قوی می شه)
سوما بحث داره شدیدا منحرف می شه. اگه می خواید یه پست راجع یه همین بذارید. ولی دیگه تو اینجا ادامه ندیم.
نمی دونستم. ممنون
آخرین ویرایش توسط مدیر
پاسخ : ماراتون گراف
[HR][/HR]
سوال 8
ثابت کنید اعداد 1 ، 2 ، و ... و 4n+2 را میتوان روی رئوس و اضلاع یک 2n+1 ضلعی قرار داد به طوری که برای هر ضلع مجموع اعداد واقع بر آن ضلع و دو راس واقع بر آن عددی ثابت باشد.
پ.ن. اینو توی سوالای گراف دیدم. ولی راه حل خودم زیاد به گراف ربطی نداره. می خوام راه حل گرافیش رو ببینم.
پ.ن. گودرز جان، اون چیزایی که تو پستای دیگه گفتم رو ، کلا بی خیال شو. راهنمایی کن . :173:
سوال 7
با توجه به چیزایی که فریدون در مورد سوال 7 گفت ، آدم میترسه بره روش بفکره. می گم سوال 7 رو هم بزاریم همچنان باشه، ولی یه سوال دیگه بزاریم تا نخوابه بحث.[HR][/HR]
سوال 8
پ.ن. اینو توی سوالای گراف دیدم. ولی راه حل خودم زیاد به گراف ربطی نداره. می خوام راه حل گرافیش رو ببینم.
پ.ن. گودرز جان، اون چیزایی که تو پستای دیگه گفتم رو ، کلا بی خیال شو. راهنمایی کن . :173:
پاسخ : ماراتون گراف
حالا من یه چیزی گفتم،دلیل نمیشه که رو سوال فک نکنید!!!سوالش سخت هست ولی اگه سواد گرافت خوب باشه سوالش خیلی هم خف نیست،کما اینکه در عرض 1هفته ای که به ما تکلیف داده بودن،3-4 نفر سوال رو حل کردن!
برای راهنمایی سوال 7 هم فقط یه چیز بگم!:به مکمل گراف دقت کنید!(مجموعه های مستقل هم خوبن!!!:198
حالا من یه چیزی گفتم،دلیل نمیشه که رو سوال فک نکنید!!!سوالش سخت هست ولی اگه سواد گرافت خوب باشه سوالش خیلی هم خف نیست،کما اینکه در عرض 1هفته ای که به ما تکلیف داده بودن،3-4 نفر سوال رو حل کردن!
برای راهنمایی سوال 7 هم فقط یه چیز بگم!:به مکمل گراف دقت کنید!(مجموعه های مستقل هم خوبن!!!:198
آخرین ویرایش توسط مدیر
پاسخ : .::ماراتن گراف::.
من می تونم راه حلش را بنویسم ولی کلی به دردسرم میندازه ولی یه سیر کلی از اثبات را می گم
1)برهان خلف: مسلما اگر حکم درست نباشد مکمل گراف دو بخشی نیست
2)کوچکترین دور فرد را در مکمل گراف در نظر بگیرید حالا حالتبندی می کنیم(3 یا 5 یا 7 یا 9 یا 11)
*پیشنهاد میدم از اینجا به بعد را یک دور خودت سعی کنی حل کنی
3)اگر سه باشد در بین رئوس باقیمانده(که جزو دور نیستند) یک تطابق با 2 یال داریم+یه سری حالتبندی ------>تناقض(جزئیاتش بماند)
4)اگر پنج باشد به مشابه سه به تناقض می رسیم
5)اگر هفت باشد: به این نتیجه می رسیم که در پنج راس باقیمانده در گراف مکمل یالی وجود ندارد ولی از یه جای دیگه (کلا جدا از این حالتبندی ها)متوجه می شویم که در گراف اضلی درجه هر راس حداکثر هشت است یا به عبارتی درجه هر راس در گراف مکمل حداقل سه است پس هر راس از بقیه رئوسی که در دور قرار ندارند به رئوس دور حداقل سه یال داده اند که با فرض کوچکترین دور بودن آن هفت راسی به تناقض می خورد
6)برای 9 توجه کنید که باید در هر 9 راس در گراف اصلی یک خوشه 5 راسی موجود باشد!!!!!
7)برای 11 توجه کنید که درجه رئوس دور در گراف اصلی حداقل 9 است
پس به تناقض رسیدیم
چون خودم یه مدتی از المپیاد دور بودم سوالی مد نظرم نیست اگه کسی دیگه سوال داره بگه
من می تونم راه حلش را بنویسم ولی کلی به دردسرم میندازه ولی یه سیر کلی از اثبات را می گم
1)برهان خلف: مسلما اگر حکم درست نباشد مکمل گراف دو بخشی نیست
2)کوچکترین دور فرد را در مکمل گراف در نظر بگیرید حالا حالتبندی می کنیم(3 یا 5 یا 7 یا 9 یا 11)
*پیشنهاد میدم از اینجا به بعد را یک دور خودت سعی کنی حل کنی
3)اگر سه باشد در بین رئوس باقیمانده(که جزو دور نیستند) یک تطابق با 2 یال داریم+یه سری حالتبندی ------>تناقض(جزئیاتش بماند)
4)اگر پنج باشد به مشابه سه به تناقض می رسیم
5)اگر هفت باشد: به این نتیجه می رسیم که در پنج راس باقیمانده در گراف مکمل یالی وجود ندارد ولی از یه جای دیگه (کلا جدا از این حالتبندی ها)متوجه می شویم که در گراف اضلی درجه هر راس حداکثر هشت است یا به عبارتی درجه هر راس در گراف مکمل حداقل سه است پس هر راس از بقیه رئوسی که در دور قرار ندارند به رئوس دور حداقل سه یال داده اند که با فرض کوچکترین دور بودن آن هفت راسی به تناقض می خورد
6)برای 9 توجه کنید که باید در هر 9 راس در گراف اصلی یک خوشه 5 راسی موجود باشد!!!!!
7)برای 11 توجه کنید که درجه رئوس دور در گراف اصلی حداقل 9 است
پس به تناقض رسیدیم
چون خودم یه مدتی از المپیاد دور بودم سوالی مد نظرم نیست اگه کسی دیگه سوال داره بگه
