سوالات گراف

[daneshvar.amrollahi]

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

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

فرض کنید G گرافی ساده، همبند و غیر کامل با حداقل 3 راس باشد. ثابت کنید 3 راس مانند u,v,w در G وجود دارند که یال های uv,vw وجود داشته باشند اما یال uw وجود نداشته باشد.

میگم دو راس غیر مجاور u,w در نظر بگیر (میتونیم این کار رو بکنیم چون گراف کامل نیست). حالا برهان خلف میزنیم میگیم: از اونجا که گراف همبنده، مسیری بین u,w که باید وجود داشته باشه. فرض خلف میشه u,w کمترین فاصله شون بیشتر از پیمایش 2 یال هستش (حداقل 3 یاله - یعنی توی کوتاهترین مسیر بین u,w حداقل 2 راس ظاهر میشن). همین که 2 راس ظاهر میشن تناقضه. اینطوری بگم ملموس تره: فرض کنید کوتاه ترین مسیر بین u,w این باشه: u,z1,z2,w . چون کوتاه ترین مسیره، u به z2 و z1 به w یال نداره. اما توی همین مسیری که گفتم، فرض خلف نقض شد. به این دلیل: u,z1,z2 و z1,z2,w همون چیزی هستن که فرض کردیم پیدا نمیشن!

درسته این اثبات آیا؟

*اگر کسی راه دیگه ای هم داره بگه !

 

[maziar]

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

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

فرض کنید G گرافی ساده، همبند و غیر کامل با حداقل 3 راس باشد. ثابت کنید 3 راس مانند u,v,w در G وجود دارند که یال های uv,vw وجود داشته باشند اما یال uw وجود نداشته باشد.

میگم دو راس غیر مجاور u,w در نظر بگیر (میتونیم این کار رو بکنیم چون گراف کامل نیست). حالا برهان خلف میزنیم میگیم: از اونجا که گراف همبنده، مسیری بین u,w که باید وجود داشته باشه. فرض خلف میشه u,w کمترین فاصله شون بیشتر از پیمایش 2 یال هستش (حداقل 3 یاله - یعنی توی کوتاهترین مسیر بین u,w حداقل 2 راس ظاهر میشن). همین که 2 راس ظاهر میشن تناقضه. اینطوری بگم ملموس تره: فرض کنید کوتاه ترین مسیر بین u,w این باشه: u,z1,z2,w . چون کوتاه ترین مسیره، u به z2 و z1 به w یال نداره. اما توی همین مسیری که گفتم، فرض خلف نقض شد. به این دلیل: u,z1,z2 و z1,z2,w همون چیزی هستن که فرض کردیم پیدا نمیشن!

درسته این اثبات آیا؟

اره درسته من تایید می کنم!

 

[Anita H]

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

منم حرف مازیمونو تایید میکنم

اره درسته من تایید می کنم!

 

[عَنّآب ؛؛)]

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

*اگر کسی راه دیگه ای هم داره بگه !

راه های سوالا شبیه همه دیگه :/

معلومش اینه که استقرا بزن رو راسا مثن :/

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

حالا حتما راسی از خوشه هس که یو بهش یال نداره!چون خوشه ماکسیممه!

این راسه رم میذارم دبلیو!چیزی که خاسیم و داریم :/ هوم؟

 

[daneshvar.amrollahi]

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

ویرایش: کلا یه سوتی خیلی بد دادم. ببخشید!

 

[Mim]

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

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

سوال میگه: برای هر k که k بزرگتر مساوی 2 هستش، ثابت کنید یه گراف k منتظم دو بخشی یال برشی نداره.

پایه این اثباتی که میگم اینه که k نمیتونه فرد باشه. یعنی منظورم اینه که گرافی k منتظم و دو بخشی نداریم که k فرد باشه. درسته این اصلا؟

بعد میگم تنها حالتی که واسه اینجور گراف ها میمونه K k/2 k/2 هستش. (گراف کامل 2 بخشی که هر بخش k/2 راس داره).

میدونیم یه یال برشیه اگر و تنها اگر به هیچ دوری متعلق نباشه. اما همه ی یال های این گراف توی دور میان. پس یال برشی نداره.

درسته این؟

تعداد راسا k نیستا !
درجه همه راسا k عه !

 

[daneshvar.amrollahi]

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

متوجه شدم سوال قبلی ایراد چی بود!

یه سوال دیگه هم هست. یه قضیه دیگه هم تو وست هست که میگه: اگر و تنها اگر n تا عدد جمعشون زوج بشه، میتونن دنباله درجات یه گراف باشند. توی پی دی اف انگلیسیش قضیه 1.3.28 هستش. خوب غلط نیست این؟ اکر نیست، پس هاول حکیمی واسه چی الگوریتم داده؟ فقط چک میکرد جمعش زوج باشه دیگه

http://s6.uplod.ir/i/00632/75gnf5ecstjd.png

من چیو اشتباه فهمیدم؟

 

[عَنّآب ؛؛)]

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

متوجه شدم سوال قبلی ایراد چی بود!

یه سوال دیگه هم هست. یه قضیه دیگه هم تو وست هست که میگه: اگر و تنها اگر n تا عدد جمعشون زوج بشه، میتونن دنباله درجات یه گراف باشند. توی پی دی اف انگلیسیش قضیه 1.3.28 هستش. خوب غلط نیست این؟ اکر نیست، پس هاول حکیمی واسه چی الگوریتم داده؟ فقط چک میکرد جمعش زوج باشه دیگه

http://s6.uplod.ir/i/00632/75gnf5ecstjd.png

من چیو اشتباه فهمیدم؟

هردو درسته!

هاول حکیمیو نگاه کن!(وست اینگیلیسی- صفحه 45- 1.3.31) جمله آخرش گفته که تنها دمباله ی تک المنتی گرافیک برابره با d1 = 0!! در حالیه که یه لوپ تک راسی هم گرافه ینی دمباله درجه ی d1 = 2 !!

پس ازینجا میفهمیم که هاول حکیمی داره راجب گراف های ساده صحبت میکنه!

اما زوج بودن مجموع درجه ها برای گرافیک بودن لازمه! اما ممکنه گرافی ک تشکیل میده ساده نباشه : )

مثال قضیه ای ک گفتی هم ساده س!

راسای درجه زوج رو یه لوپ e یالی در نظر بگیر!

درجه فردا رو دو به دو به هم وصل کن و یالای باقیمونده رو به خودشون وصل کن :/ هوم؟

 

[daneshvar.amrollahi]

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

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

سوال میگه: فرض کنید یه گراف n راسی داریم که دقیقا k مولفه داره. این گراف حداکثر چندتا یال میتونه داشته باشه؟

من میگم خوب بیایم k مولفه رو در نظر بگیریم. میخوایم تا میتونیم یال های درون مولفه ای رو زیاد کنیم و بین مولفه ها هیچ یالی نیاد.

کلا که انتخاب 2 از n تا یال میشه گذاشت. اما میخواهیم یال هایی که بین مولفه ها اومدن رو برداریم. یه دنباله از 0,1 در نظر بگیرید به طول انتخاب 2 از k که هر خونش نشان دهنده ی وجود یالی بین دو مولفه ی مشخص i,j هستش. منظورم اینه که مثلا میشه برای نشان هر خونه یه زوج مرتب در نظر گرفت. برای این دنباله 2 به توان (انتخاب 2 از k) حالت وجود داره که فقط توی 1 حالتشه که هیچ یالی بین هیچ دو مولفه ای نمی آید. بقیه حالت ها نامطلوب هستن. پس متمم میزنیم:
جواب میشه :
C(N,2) - 2^ (C(k,2)) + 1

درسته آیا یا اینکه دوباره یه سوتیه خیلی بد داره؟؟ اگر درست باشه یه اتحاد ترکیبیاتی ساخته میشه با اون جواب وست!

* هیچ خجالتی از اشتباه بودنش نمی کشم! انقدر باید ایراد ها پیدا شه تا یاد بگیریم دیگه! اگر ایراد داره بگید!

 

[Infinite Infinity]

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

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

سوال میگه: فرض کنید یه گراف n راسی داریم که دقیقا k مولفه داره. این گراف حداکثر چندتا یال میتونه داشته باشه؟

من میگم خوب بیایم k مولفه رو در نظر بگیریم. میخوایم تا میتونیم یال های درون مولفه ای رو زیاد کنیم و بین مولفه ها هیچ یالی نیاد.

کلا که انتخاب 2 از n تا یال میشه گذاشت. اما میخواهیم یال هایی که بین مولفه ها اومدن رو برداریم. یه دنباله از 0,1 در نظر بگیرید به طول انتخاب 2 از k که هر خونش نشان دهنده ی وجود یالی بین دو مولفه ی مشخص i,j هستش. منظورم اینه که مثلا میشه برای نشان هر خونه یه زوج مرتب در نظر گرفت. برای این دنباله 2 به توان (انتخاب 2 از k) حالت وجود داره که فقط توی 1 حالتشه که هیچ یالی بین هیچ دو مولفه ای نمی آید. بقیه حالت ها نامطلوب هستن. پس متمم میزنیم:
جواب میشه :
C(N,2) - 2^ (C(k,2)) + 1

درسته آیا یا اینکه دوباره یه سوتیه خیلی بد داره؟؟ اگر درست باشه یه اتحاد ترکیبیاتی ساخته میشه با اون جواب وست!

مگه هر مولفه فقط یک راسه ؟ کلا حس میکنم قاطی کردی
ولی خب N=3 و K=2 بزار مثلا ! جوابت غلط میشه !
میشه 2 از n-k+1

* هیچ خجالتی از اشتباه بودنش نمی کشم! انقدر باید ایراد ها پیدا شه تا یاد بگیریم دیگه! اگر ایراد داره بگید!

این روحیتو تحسین میکنم

 

[Fliqpy]

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

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

سوال میگه: فرض کنید یه گراف n راسی داریم که دقیقا k مولفه داره. این گراف حداکثر چندتا یال میتونه داشته باشه؟

من میگم خوب بیایم k مولفه رو در نظر بگیریم. میخوایم تا میتونیم یال های درون مولفه ای رو زیاد کنیم و بین مولفه ها هیچ یالی نیاد.

کلا که انتخاب 2 از n تا یال میشه گذاشت. اما میخواهیم یال هایی که بین مولفه ها اومدن رو برداریم. یه دنباله از 0,1 در نظر بگیرید به طول انتخاب 2 از k که هر خونش نشان دهنده ی وجود یالی بین دو مولفه ی مشخص i,j هستش. منظورم اینه که مثلا میشه برای نشان هر خونه یه زوج مرتب در نظر گرفت. برای این دنباله 2 به توان (انتخاب 2 از k) حالت وجود داره که فقط توی 1 حالتشه که هیچ یالی بین هیچ دو مولفه ای نمی آید. بقیه حالت ها نامطلوب هستن. پس متمم میزنیم:
جواب میشه :
C(N,2) - 2^ (C(k,2)) + 1

درسته آیا یا اینکه دوباره یه سوتیه خیلی بد داره؟؟ اگر درست باشه یه اتحاد ترکیبیاتی ساخته میشه با اون جواب وست!

* هیچ خجالتی از اشتباه بودنش نمی کشم! انقدر باید ایراد ها پیدا شه تا یاد بگیریم دیگه! اگر ایراد داره بگید!

چيزي كه به نظرم ميرسه اينه كه اگه k<N جواب مساله حداقل يكه ولي تو خيلي حالتا چيزي كه شما در آوردين اصلا منفيه، متوجه نشدم چرا بايد تعداد يالها رو منهاي تعداد حالات نامطلوب كنين. تعداد حالات كه با تعداد يالها ارتباطي نداره، خصوصا كه حتي تعداد حالات هم اون نيست چون به تعداد رئوس مولفه ها هم ارتباط داره.
حالا شايد من بد فهميدم.

 

[daneshvar.amrollahi]

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

چيزي كه به نظرم ميرسه اينه كه اگه k<N جواب مساله حداقل يكه ولي تو خيلي حالتا چيزي كه شما در آوردين اصلا منفيه، متوجه نشدم چرا بايد تعداد يالها رو منهاي تعداد حالات نامطلوب كنين. تعداد حالات كه با تعداد يالها ارتباطي نداره، خصوصا كه حتي تعداد حالات هم اون نيست چون به تعداد رئوس مولفه ها هم ارتباط داره.
حالا شايد من بد فهميدم.
راه خودش با گراف مكمل و تورانه؟

نه شما درست فهمیدی! من اشتباه گفتم!
راه خودش: http://s5.picofile.com/file/8120303234/west_solution.pdf.html
سوال 1.3.40 بخش b

 

[MehrnaZz]

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

چند گراف 7-منتظم از مرتبه 10 داریم؟؟

 

[عَنّآب ؛؛)]

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

چند گراف 7-منتظم از مرتبه 10 داریم؟؟

مکملاشو بشمار!

10 راسی 7 منتظم مکملش میشه 10 راسی 2 منتظم!

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

راحت شد دیگه بشین بشمر ببین چن تا اجتماع دور هس که 10 راسی باشه من خسته م

 

[Anita H]

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

مکملاشو بشمار!

10 راسی 7 منتظم مکملش میشه 10 راسی 2 منتظم!

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

راحت شد دیگه بشین بشمر ببین چن تا اجتماع دور هس که 10 راسی باشه من خسته م

میشه این دو تا رو به طور واضح جواب بدید؟
چند تا گراف ۱۰ راسی ساده و بی جهت و لیبل دار داریم که اجتماع یه سری دور باشن؟
چند تا گراف ۱۰ راسی غیرساده و بی جهت و لیبل دار داریم که اجتماع یه سری دور باشن؟

 

[KURT]

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

بچه ها اگه کسی هست سوال بذارید حل کنیم

- پست بالا ماله یه سال پیشه، فکر نکنم دیگه جواب سوالشو بخواد "-: ولی کلا سوال جدید بذارید تاپیک بیاد بالا "-:

 

[Anita H]

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

بچه ها اگه کسی هست سوال بذارید حل کنیم

- پست بالا ماله یه سال پیشه، فکر نکنم دیگه جواب سوالشو بخواد "-: ولی کلا سوال جدید بذارید تاپیک بیاد بالا "-:

نه من هنوز جواب سوالمو میخوام : )