سوالات گراف

شروع موضوع توسط مهسا.ق ‏2013/3/5 در انجمن المپیاد كامپيوتر

  1. علیمپو

    علیمپو کاربر فوق حرفه ای

    ارسال‌ها:
    602
    امتیازات:
    +3,254 / -238
    نام مرکز سمپاد:
    حلی۲
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    تهران
    رشته دانشگاه:
    آمار
    پاسخ : سوالات گراف

    این قسمت قرمز حرفت غلطه :-" ( لزومی هم به این قسمت ندارمی واسه اثبات ! پاکش کنی درسته جوابت)
    به جز این قسمت بقیش درسته دیگه !
    یعنی به ازای هر راس از G , دو تا راس دیگه پیدا میشن که با هم تشکیل یه مسیر به طول 2 رو بدن ! ( که همون حکمه ! )
     
    • لایک لایک x 1
  2. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    نتیجه گرفتیم به ازای هر راس از G، دو تا راس دیگه پیدا میشن که با هم تشکیل یه مسیر به طول 3 رو میدن. اما از کجا میتونیم این مسیر 3 راسی متعلق به یه زیرگراف القایی هستش؟
     
  3. علیمپو

    علیمپو کاربر فوق حرفه ای

    ارسال‌ها:
    602
    امتیازات:
    +3,254 / -238
    نام مرکز سمپاد:
    حلی۲
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    تهران
    رشته دانشگاه:
    آمار
    پاسخ : سوالات گراف

    خب حالا از کامل نبودن گراف استفاده کن واسه این که بگی اگر مثلث تشکیل شه ، این راس با 2 تا دیگه تشکیل میده مسیر 3 تایی رو !
    حالت بندیش خیلی زیاد میشه ولی !
    همون استقرا بهتره :-"

    # یه راه دیگه : راس با کوچیکترین درجه رو فرض کن . چون گراف کامل نیست درجش کمتر از n - 1 هست . فرض کن با k تا راس مجاوره و با n - k - 1 راس مجاور نیست ...
    این طوری هم حل میشه :-"
     
    • لایک لایک x 2
  4. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    سلام. یه سوال گراف دارم. فکر کنم استقرا باشه:

    ثابت کنید گرافی ساده با دنباله درجات 3,3,2,2,1,1,...k.k وجود دارد.

    ایدم اینه که کار نمی کنه: روی k استفرا بزنیم. به جز 2 راسی که درجشون k+1 هستش، بقیه ی راس ها طبق فرض بین خودشون گراف تشکیل داده اند. حالا این 2 راس با درجه ی k+1 رو میخواستم به همه وصل کنم که اینطوری دیگه راسی با درجه ی 1 نمی مونه!
     
  5. Mim

    Mim کاربر فوق فعال

    ارسال‌ها:
    144
    امتیازات:
    +1,428 / -30
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    قم
    سال فارغ التحصیلی:
    96
    دانشگاه:
    تهران
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    ببین الان 2k راس داری!
    میتونیم اینطوری بگیم که یه راسو به k راس که درجه های 1 تا k دارن وصل میکنیم. حالا k تا راس داریم با درجه های 1 تا k ، k تا با درجه های 2 تا k+1 ، یکی با درجه k ! یه راس دیگه م اضافه میکنیم وصلش میکنیم به این ! این میشه k+ 1 ، راس جدیدم درجه ش میشه 1
    درس میشه :D
     
    • لایک لایک x 1
  6. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    درسته ممنون!
     
  7. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    ثابت کنید هر گرافی که مثلت نداره، این رابطه براش برقراره: کمترین درجه + بیشترین درجه اش، کوچکتر یا مساوی تعداد راس ها هستند.

    ایدم استقراست. اما جواب نداده. توی اثبات حکم استقرا اومدم از برهان خلف استفاده کنم فقط تونستم بفهمم گرافی که مثلث داره راسی داره که حداقل درجه اش 2 هستش. اما از اینجا به بعد نتونستم چیزی بگم!

    ایده ی حلش استقراست؟ یکی یه راهنمایی بکنه!
     
  8. عَنّآب ؛؛)

    عَنّآب ؛؛) کاربر نیمه حرفه ای

    ارسال‌ها:
    214
    امتیازات:
    +1,608 / -51
    نام مرکز سمپاد:
    فرزانگان۱
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    ایده ی حلش استقراس ینی چی دقیقا؟ ممکنه با استقرا هم حل شه خب

    اما بدون استقرا هم حل میشه! با همون برهان خلف! بدون استقرا

    راهنماییم اینکه اگه حداقل اون تساوی ان به علاوه یک باشه مینیمم و ماکسیمم یه همسایه مشترک دارن! رو این همسایه مشترکه حرف بزن

    مثلث تشکیل میشه!

    خیلی زیاد راهنمایی کردم فک کنم :/
     
    • لایک لایک x 1
  9. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    آره خیلی راهنمایی کردید!! بیشترین درجه و همسایش روی هم به حداقل n-1 راس وصل هستن (طبق فرض خلف) و کلا n-2 راس دیگه هست --> لانه کبوتری --> حداقل یه راس هست که هم به به راس دارای بیشترین درجه و به همسایش وصله. --> مثلث داریم --> تناقض!
     
  10. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    نگرفتم!
     
  11. Mim

    Mim کاربر فوق فعال

    ارسال‌ها:
    144
    امتیازات:
    +1,428 / -30
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    قم
    سال فارغ التحصیلی:
    96
    دانشگاه:
    تهران
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    حل شد دیگه !
    بگذریم :-"
     
  12. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    ثابت کنید توی یک گراف 10 راسی ساده که هر از هر سه راسی، حداقل دوتاشون مجاور باشن، عدد خوشه ای بزرگتر مساوی 4 هستش.
     
  13. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,912 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات گراف

    عدد خوشه ای تعداد راسای بزرگترین زیرگراف القایی کامل بود؟ :/
     
  14. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    عدد خوشه ای بیشترین تعداد عضو های یه زیرمجموعه از راس هاست به طوری هر دو راسی توی اون مجموعه راس ها مجاور باشند.
    یعنی تعداد عضو های گنده ترین مجموعه ای راس ها که بشه پیدا کرد به طوری همه ی راس های توش دو به دو مجاور باشند
     
  15. عَنّآب ؛؛)

    عَنّآب ؛؛) کاربر نیمه حرفه ای

    ارسال‌ها:
    214
    امتیازات:
    +1,608 / -51
    نام مرکز سمپاد:
    فرزانگان۱
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    همین ک مجید میگه س دیگه!
    القاییشو نگی هم حله :-" :-اظهار نظر
     
  16. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    سوال اصلی یه چیز دیگست! بحث سر تعریف عدد خوشه ای نیست :D
     
  17. عَنّآب ؛؛)

    عَنّآب ؛؛) کاربر نیمه حرفه ای

    ارسال‌ها:
    214
    امتیازات:
    +1,608 / -51
    نام مرکز سمپاد:
    فرزانگان۱
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    به هرحال مشکلات هرچند جزعی باید حل شن :-منبر

    فقد یه چیزی!

    الان ما باید اینو حل کنیم و ب شما اطلاع بدیم و یا فقد حل کنیم؟
     
  18. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    حل کنید یا اکر حل نشد ایده هاتونو بگید! راهنمایی شه!
     
  19. Mim

    Mim کاربر فوق فعال

    ارسال‌ها:
    144
    امتیازات:
    +1,428 / -30
    نام مرکز سمپاد:
    فرزانگان
    شهر:
    قم
    سال فارغ التحصیلی:
    96
    دانشگاه:
    تهران
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    همه همسایه ها یه راسو در نظر بگیر ! اگه حداقل به 4 راس یال نداشته باشه، چون نباید مجموعه مستقل 3 عضوی داشته باشیم، همه این راسا به هم یال دارن و تمام ! حالا اگه به حداقل 6 راس یال داشته باشه ! ثابت میکنیم بین این 6 راس، یه مثلث هس : باز یه راس ازین 6 تارو در نظر بگیر ! اگه به حداقل سه راس یال نداشته باشه که اینا به هم یال دارن و بازم تمام، وگرنه حداقل به 3 تا یال داره ! بین خود این سه تا هم قطعا یه یال هس ! تمام :D (این مثلث با اون راس اولیه که در نظر گرفتیم یه خوشه تشکیل میدن.)
    خیلی هم کثیف :- "
     
    • لایک لایک x 1
  20. عَنّآب ؛؛)

    عَنّآب ؛؛) کاربر نیمه حرفه ای

    ارسال‌ها:
    214
    امتیازات:
    +1,608 / -51
    نام مرکز سمپاد:
    فرزانگان۱
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    دانشگاه:
    صنعتی شریف
    رشته دانشگاه:
    علوم کامپیوتر
    پاسخ : سوالات گراف

    حالا که بحث خوشه ـس منم یه سوال بگم!

    100 راس در نظر میگیریم و روی هرکودوم یه رشته ی 100 بیتی 0 و 1 مینویسیم!

    حالا هر دو راسی ک رشته های متناظر با اونا حداقل تو 51 بیت متفاوتن رو به هم وصل میکنیم

    ثابت کنید گراف حاصل عدد خوشه ایش از 50 بیشتر نیس!

    آیا گرافی با خوشه 50 راسی داریم اصا؟ :/