سوالات گراف

[علیمپو]

پاسخ : سوالات گراف

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

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

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

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

 

[علیمپو]

پاسخ : سوالات گراف

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

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

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

 

[Mim]

پاسخ : سوالات گراف

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

ثابت کنید گرافی ساده با دنباله درجات 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
درس میشه

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

درسته ممنون!

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

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

 

[عَنّآب ؛؛)]

پاسخ : سوالات گراف

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

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

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

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

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

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

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

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

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

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

نگرفتم!

 

[Mim]

پاسخ : سوالات گراف

نگرفتم!

حل شد دیگه !
بگذریم

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

 

[Anita H]

پاسخ : سوالات گراف

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

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

 

[عَنّآب ؛؛)]

پاسخ : سوالات گراف

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

همین ک مجید میگه س دیگه!

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

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

 

[عَنّآب ؛؛)]

پاسخ : سوالات گراف

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

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

فقد یه چیزی!

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

 

[daneshvar.amrollahi]

پاسخ : سوالات گراف

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

فقد یه چیزی!

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

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

 

[Mim]

پاسخ : سوالات گراف

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

 

[عَنّآب ؛؛)]

پاسخ : سوالات گراف

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

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

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

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

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