• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

سوالات گراف

علیمپو

بچّه سنّی
ارسال‌ها
670
امتیاز
4,857
نام مرکز سمپاد
حلی۲
شهر
تهران
سال فارغ التحصیلی
1396
پاسخ : سوالات گراف

به نقل از DaneshvarA :
سلام. ۲ تا سوال از وست دارم. یکیش رو تا حدی خودم تونستم حل کنم اما هنوز مشکل دارم:

۱ ۰ فرض کنیم G یک گراف ساده همبند است که کامل نیست. ثابت کنید که هر راس از G متعلق به یک زیرگراف القایی 3 راسی یکریخت یا یک مسیر ۳ راسی می باشد.

راه حل خودم: یک راس دلخواه v1 را انتخاب می کنیم. چون گراف همبند هستش، درجه ی این راس نمیتونه صفر باشه. پس به v2 یال داره. دوباره چون همبند هستش، v2 به v3 یال داره (مگر اینکه گراف ۲ راسی باشه که نیست). پس یعنی تا الان اثبات کردیم هر زیر گراف ۳ راسی از G، تشکیل یک مسیر میده.یعنی هر زیرگراف القایی ۳ راسی هم از این گراف برداریم، تشکیل یک مسیر میده. چون در انتخاب این ۳ راس، فرض اضافی نکردیم، هر راسی از G متعلق به یک زیرگراف القایی یکریخت با یک مسیر ۳ راسی است.

این اثبات کلا غلطه؟ بعضی جاهاش غلطه؟ کسی میتونه درستش رو بگه؟

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

daneshvar.amrollahi

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

به نقل از am.ma :
این قسمت قرمز حرفت غلطه :-" ( لزومی هم به این قسمت ندارمی واسه اثبات ! پاکش کنی درسته جوابت)
به جز این قسمت بقیش درسته دیگه !
یعنی به ازای هر راس از G , دو تا راس دیگه پیدا میشن که با هم تشکیل یه مسیر به طول 3 رو بدن ! ( که همون حکمه ! )

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

علیمپو

بچّه سنّی
ارسال‌ها
670
امتیاز
4,857
نام مرکز سمپاد
حلی۲
شهر
تهران
سال فارغ التحصیلی
1396
پاسخ : سوالات گراف

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

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

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

daneshvar.amrollahi

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

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

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

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

Mim

کاربر فوق‌فعال
ارسال‌ها
147
امتیاز
1,408
نام مرکز سمپاد
فرزانگان
شهر
قم
سال فارغ التحصیلی
96
دانشگاه
تهران
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

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

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

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

daneshvar.amrollahi

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

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

daneshvar.amrollahi

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

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

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

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

عَنّآب ؛؛)

کاربر نیمه‌حرفه‌ای
ارسال‌ها
214
امتیاز
1,619
نام مرکز سمپاد
فرزانگان۱
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
برنز کامپیوتر ۹۵
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

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

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

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

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

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

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

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

خیلی زیاد راهنمایی کردم فک کنم :/
 

daneshvar.amrollahi

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

به نقل از عَـــژدَر B-) :
ایده ی حلش استقراس ینی چی دقیقا؟ ممکنه با استقرا هم حل شه خب

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

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

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

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

daneshvar.amrollahi

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

به نقل از -sky- :
اگه ماکس و مین تو مولفه های جدا باشن که واضحه !
اگه تو یه مولفه باشن، و فاصله شون 1 باشه، ینی راسی که مینیمم درجه رو داره (m) با راسی که ماکسیمم درجه رو داره (M) همسایه س ! چون گراف مثلث نداره، پس بین راسای مجاور M یالی نیس، پس هرچقد بخایم به درجه مین اضافه شه، حداقل باید به همون اندازه راس اضافه کنیم که به همه مجاورای M یال داشته باشه ! پس به دو طرف به یه اندازه اضافه میشه و تساوی برقراره.
اگه فاصله از 2 بیشتر باشه، تعداد رئوس حداقل، درجه مین + درجه ماکس + 2 عه !
و اما اگه فاصله 2 باشه : m به یه سری راسای مجاور M متصله که درجه اون راسا طبیعتا از مین بیشتره ! پس غیر از m ، حداقل به اندازه مین بهشون راس متصله. (با احتساب M ) در نتیجه رابطه کوچکتر مساوی برقرار میشه ...

الان کلیّت قضیه رو گفتم !
افتضاح توضیح دادم میدونم :| شاید هم غلط باشه !
نگرفتم!
 

Mim

کاربر فوق‌فعال
ارسال‌ها
147
امتیاز
1,408
نام مرکز سمپاد
فرزانگان
شهر
قم
سال فارغ التحصیلی
96
دانشگاه
تهران
رشته دانشگاه
علوم کامپیوتر

daneshvar.amrollahi

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

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

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوالات گراف

به نقل از DaneshvarA :
ثابت کنید توی یک گراف 10 راسی ساده که هر از هر سه راسی، حداقل دوتاشون مجاور باشن، عدد خوشه ای بزرگتر مساوی 4 هستش.
عدد خوشه ای تعداد راسای بزرگترین زیرگراف القایی کامل بود؟ :/
 

daneshvar.amrollahi

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

به نقل از amoo.majid :
عدد خوشه ای تعداد راسای بزرگترین زیرگراف القایی کامل بود؟ :/
عدد خوشه ای بیشترین تعداد عضو های یه زیرمجموعه از راس هاست به طوری هر دو راسی توی اون مجموعه راس ها مجاور باشند.
یعنی تعداد عضو های گنده ترین مجموعه ای راس ها که بشه پیدا کرد به طوری همه ی راس های توش دو به دو مجاور باشند
 

عَنّآب ؛؛)

کاربر نیمه‌حرفه‌ای
ارسال‌ها
214
امتیاز
1,619
نام مرکز سمپاد
فرزانگان۱
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
برنز کامپیوتر ۹۵
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

به نقل از DaneshvarA :
عدد خوشه ای بیشترین تعداد عضو های یه زیرمجموعه از راس هاست به طوری هر دو راسی توی اون مجموعه راس ها مجاور باشند.
یعنی تعداد عضو های گنده ترین مجموعه ای راس ها که بشه پیدا کرد به طوری همه ی راس های توش دو به دو مجاور باشند

همین ک مجید میگه س دیگه!
به نقل از amoo.majid :
عدد خوشه ای تعداد راسای بزرگترین زیرگراف القایی کامل بود؟ :/

القاییشو نگی هم حله :-" :-اظهار نظر
 

daneshvar.amrollahi

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

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

عَنّآب ؛؛)

کاربر نیمه‌حرفه‌ای
ارسال‌ها
214
امتیاز
1,619
نام مرکز سمپاد
فرزانگان۱
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
برنز کامپیوتر ۹۵
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

به نقل از DaneshvarA :
سوال اصلی یه چیز دیگست! بحث سر تعریف عدد خوشه ای نیست :D
به هرحال مشکلات هرچند جزعی باید حل شن :-منبر

فقد یه چیزی!

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

daneshvar.amrollahi

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

به نقل از عَن عان هپی فلاور :)) :
به هرحال مشکلات هرچند جزعی باید حل شن :-منبر

فقد یه چیزی!

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

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

Mim

کاربر فوق‌فعال
ارسال‌ها
147
امتیاز
1,408
نام مرکز سمپاد
فرزانگان
شهر
قم
سال فارغ التحصیلی
96
دانشگاه
تهران
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

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

عَنّآب ؛؛)

کاربر نیمه‌حرفه‌ای
ارسال‌ها
214
امتیاز
1,619
نام مرکز سمپاد
فرزانگان۱
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
برنز کامپیوتر ۹۵
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : سوالات گراف

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

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

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

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

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