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

سوالات گراف

daneshvar.amrollahi

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

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

فرض کنید 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

مازیمون
ارسال‌ها
1,962
امتیاز
6,833
نام مرکز سمپاد
علامه حلی
شهر
تهران، استانبول، کوالالامپور، اُسلو!
دانشگاه
Universitetet i Oslo
رشته دانشگاه
ریاضی، CS، نانو الکترونیک
پاسخ : سوالات گراف

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

فرض کنید 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

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

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

عَنّآب ؛؛)

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

به نقل از DaneshvarA :
*اگر کسی راه دیگه ای هم داره بگه !

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

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

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

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

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

daneshvar.amrollahi

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

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

Mim

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

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

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

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

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

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

درسته این؟

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

daneshvar.amrollahi

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

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

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

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

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

عَنّآب ؛؛)

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

به نقل از daneshvar.a :
متوجه شدم سوال قبلی ایراد چی بود!

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

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

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

هردو درسته!

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

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

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

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

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

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

daneshvar.amrollahi

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

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

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

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

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

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

* هیچ خجالتی از اشتباه بودنش نمی کشم! :D انقدر باید ایراد ها پیدا شه تا یاد بگیریم دیگه! اگر ایراد داره بگید!
 
ارسال‌ها
919
امتیاز
4,414
نام مرکز سمپاد
حلی
شهر
تهران
سال فارغ التحصیلی
1395
دانشگاه
تهران
پاسخ : سوالات گراف

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

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

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

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

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

* هیچ خجالتی از اشتباه بودنش نمی کشم! :D انقدر باید ایراد ها پیدا شه تا یاد بگیریم دیگه! اگر ایراد داره بگید!
این روحیتو تحسین میکنم :-"
 

Fliqpy

کاربر نیمه‌حرفه‌ای
ارسال‌ها
181
امتیاز
303
نام مرکز سمپاد
غیر انتفاعی علامه حلی 3
شهر
تهران
مدال المپیاد
هر جوری حساب میکنم افتخار نمیکنم بهش
دانشگاه
شريف
رشته دانشگاه
نرم افزار
پاسخ : سوالات گراف

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

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

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

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

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

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

daneshvar.amrollahi

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

به نقل از ناهمساز :
چيزي كه به نظرم ميرسه اينه كه اگه k<N جواب مساله حداقل يكه ولي تو خيلي حالتا چيزي كه شما در آوردين اصلا منفيه، متوجه نشدم چرا بايد تعداد يالها رو منهاي تعداد حالات نامطلوب كنين. تعداد حالات كه با تعداد يالها ارتباطي نداره، خصوصا كه حتي تعداد حالات هم اون نيست چون به تعداد رئوس مولفه ها هم ارتباط داره.
حالا شايد من بد فهميدم.
راه خودش با گراف مكمل و تورانه؟
نه شما درست فهمیدی! من اشتباه گفتم!
راه خودش: http://s5.picofile.com/file/8120303234/west_solution.pdf.html
سوال 1.3.40 بخش b
 

MehrnaZz

کاربر حرفه‌ای
ارسال‌ها
359
امتیاز
3,035
نام مرکز سمپاد
فرزانگان 1
شهر
زاهدان
سال فارغ التحصیلی
95
مدال المپیاد
مرحله 1 ریاضی
دانشگاه
فردوسی
رشته دانشگاه
برق
پاسخ : سوالات گراف

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

عَنّآب ؛؛)

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

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

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

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

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

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

Anita H

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

به نقل از عَنـّـاب ؛؛) :
مکملاشو بشمار!

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

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

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

KURT

KC
ارسال‌ها
32
امتیاز
814
نام مرکز سمپاد
Hell i
شهر
Tehran
پاسخ : سوالات گراف

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

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

Anita H

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

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

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