عدد گلوگاهی رو توی یک لوپ قرار بدین
مثل شکل زیر. که گزینه های ۱ و ۳ و ۴ رد میشن و ۲ اثبات میشه

من بعد از دو ماه این سوالو دیدم و جالبه برام که چرا اینقدر رو این سوال بحث هست و جالبتر اینکه این طاهرپور پارسه چرا غلط جواب داده (هرچند ، از این غلطها کم نداشته)
صورت سوالو دقت کنید
۱/ گراف همبند و بی جهت ، پس بین هر دو راس مسیر وجود داره
۲/ گفته به ازای هر دو راس ، پس یعنی واسه بدست آوردن عدد گلوگاه باید تمام رئوس را دو دوتا با هم در نظر بگیریم
۳/ گفته بزرگترین b به ازای هر دو راس
پس با این سه فرض ما تعداد بسیار زیادی عدد گلوگاه میتونیم داشته باشیم که باید بزرگترینشو انتخاب کنیم
بزرگترین عدد گلوگاه مسلما بین دو راسی است که دو سر بزرگترین یال هستند. یکی از مسیر های بین این دو راس که دو سر بزرگترین یال هستند دقیقا همین یاله. پس چون این یال بزرگترین یال در گراف میشه پس به عنوان گلوگاه انتخاب میشه و گزینه ۲ صحیحه

مثلا تو همین شکلی که اون دوستمون گذاشتند
طبق صورت سوال گفته بین هر دو راس ، پس من میتونم هر دو راسی که عشقم کشید را انتخاب کنم
واسه همین من دو راس a و b را انتخاب میکنم
چند تا مسیر بین a , b هست. بسیار مسیر (چون نگفته مسیر ساده یا ابتدایی) و یکی از این مسیرها همون یال ۸ بین این دوتاست
پس من یه عدد گلوگاه واسه این درخت بدست آوردم با مقدار ۸
حالا هر کی تونست یکی بیشتر از این مقدار پیدا کنه ؛ کمتر هم پیدا کردید که فایده نداره چون ما قراره بزرگترین را انتخاب کنیم

جواب طاهرپور را خداییش یه دور ببینید. قشنگ معلومه این بنده خدا بدون اینکه صورت سوال رو بخونه، رفته و طبق درخت گلوگاه (نه عدد گلوگاهی که تو صورت سوال گفته شده) جواب داده

(۱۴ بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)masoud67 نوشته شده توسط:  طبق صورت سوال گفته بین هر دو راس ، پس من میتونم هر دو راسی که عشقم کشید را انتخاب کنم
واسه همین من دو راس a و b را انتخاب میکنم
چند تا مسیر بین a , b هست. بسیار مسیر (چون نگفته مسیر ساده یا ابتدایی) و یکی از این مسیرها همون یال ۸ بین این دوتاست
پس من یه عدد گلوگاه واسه این درخت بدست آوردم با مقدار ۸
حالا هر کی تونست یکی بیشتر از این مقدار پیدا کنه ؛ کمتر هم پیدا کردید که فایده نداره چون ما قراره بزرگترین را انتخاب کنیم

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

(۱۶ بهمن ۱۳۹۲ ۱۱:۵۱ ق.ظ)keywan78 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)masoud67 نوشته شده توسط:  طبق صورت سوال گفته بین هر دو راس ، پس من میتونم هر دو راسی که عشقم کشید را انتخاب کنم
واسه همین من دو راس a و b را انتخاب میکنم
چند تا مسیر بین a , b هست. بسیار مسیر (چون نگفته مسیر ساده یا ابتدایی) و یکی از این مسیرها همون یال ۸ بین این دوتاست
پس من یه عدد گلوگاه واسه این درخت بدست آوردم با مقدار ۸
حالا هر کی تونست یکی بیشتر از این مقدار پیدا کنه ؛ کمتر هم پیدا کردید که فایده نداره چون ما قراره بزرگترین را انتخاب کنیم

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

شما هم که حرف منو زدی. الان رد کردی یا تایید کردی؟
گفته به ازای هر دو راس. یعنی شما باید تمام رئوس را دوتا دوتا باهم بگیری و هرچی عدد میشه بدست بیاری و دست آخر بزرگترین را انتخاب کنی
یعنی حدود $\binom{n}{2}$ بار نیازه که این عمل را انجام بدی

(۱۶ بهمن ۱۳۹۲ ۱۲:۰۱ ب.ظ)masoud67 نوشته شده توسط:  

(16 بهمن ۱۳۹۲ ۱۱:۵۱ ق.ظ)keywan78 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)masoud67 نوشته شده توسط:  طبق صورت سوال گفته بین هر دو راس ، پس من میتونم هر دو راسی که عشقم کشید را انتخاب کنم
واسه همین من دو راس a و b را انتخاب میکنم
چند تا مسیر بین a , b هست. بسیار مسیر (چون نگفته مسیر ساده یا ابتدایی) و یکی از این مسیرها همون یال ۸ بین این دوتاست
پس من یه عدد گلوگاه واسه این درخت بدست آوردم با مقدار ۸
حالا هر کی تونست یکی بیشتر از این مقدار پیدا کنه ؛ کمتر هم پیدا کردید که فایده نداره چون ما قراره بزرگترین را انتخاب کنیم

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

شما هم که حرف منو زدی. الان رد کردی یا تایید کردی؟
گفته به ازای هر دو راس. یعنی شما باید تمام رئوس را دوتا دوتا باهم بگیری و هرچی عدد میشه بدست بیاری و دست آخر بزرگترین را انتخاب کنی
یعنی حدود $\binom{n}{2}$ بار نیازه که این عمل را انجام بدی

مه دیگه اینجوری حساب نمیشه.
همین مثال بالا وقتی میگین ۸ عدد گلوگاهیه باید بین راسهای دیگه همچین مسیری پیدا کنین که یالهاش از ۸ کمتر نباشه. میشه پیدا کرد ایا؟؟؟

(۱۶ بهمن ۱۳۹۲ ۱۲:۰۹ ب.ظ)keywan78 نوشته شده توسط:  مه دیگه اینجوری حساب نمیشه.
همین مثال بالا وقتی میگین ۸ عدد گلوگاهیه باید بین راسهای دیگه همچین مسیری پیدا کنین که یالهاش از ۸ کمتر باشه. میشه پیدا کرد ایا؟؟؟

b مربوط به یک مسیره و نه عدد گلوگاه
ما یه تعداد زیادی b داریم که بزرگترینش را به عنوان گلوگاه انتخاب میکنیم
تو صورت سوال نگفته که به ازای هر مسیر وزن هر یال از عدد گلوگاه کمتر نباشد، گفته به ازای هر مسیر وزن هر یال از b کمتر نباشد

(۱۶ بهمن ۱۳۹۲ ۱۲:۳۲ ب.ظ)masoud67 نوشته شده توسط:  

(16 بهمن ۱۳۹۲ ۱۲:۰۹ ب.ظ)keywan78 نوشته شده توسط:  مه دیگه اینجوری حساب نمیشه.
همین مثال بالا وقتی میگین ۸ عدد گلوگاهیه باید بین راسهای دیگه همچین مسیری پیدا کنین که یالهاش از ۸ کمتر باشه. میشه پیدا کرد ایا؟؟؟

b مربوط به یک مسیره و نه عدد گلوگاه
ما یه تعداد زیادی b داریم که بزرگترینش را به عنوان گلوگاه انتخاب میکنیم
تو صورت سوال نگفته که به ازای هر مسیر وزن هر یال از عدد گلوگاه کمتر نباشد، گفته به ازای هر مسیر وزن هر یال از b کمتر نباشد

توصیه میکنم سوال رو دوباره بخونین. کلا چند بار بخونین. متوجه میشین b همون عدد گلوگاهه مستقل از مسیر

من اینو گزینه ۳ زدم ولی سوال مزخرف هست اگه این مدلی بیاد نمیزنم !! بخصوص که الان دارم میبینم سنجش گزینه ۲ رو درست اعلام کرده!
خداییش سوالای پارسال رو امروز کار کردم دهنم صاف شده! خیلی بد دادن !

(۰۹ آذر ۱۳۹۲ ۰۱:۴۱ ب.ظ)tarane1992 نوشته شده توسط:  سلام

دوستان عدد گلوگاهی مگه بزرگترین وزن در گراف نیست؟
خوب جواب این سوالو سنجش که حل کرده بزرگترین وزن یال در نظر نگرفته چرا؟؟پس منظور از عدد گلوگاه چیه؟

سوالو در زیر گذاشتم جواب گزینه سنجش گزینه ۲ است ولی پارسه گزینه های ۱و۳ رو درست گفته !!!من کاملا گیج شدم

پارسه سبکترین یالو گلوگاه گرفته پس با این حساب هر گرافی بکشیم که سبکترین یالش همون گلوگاه باشه پس درخت کمینه اش هم همون یال خواهد بود یعنی اون یال سبک در درخت کمینه هست.
ولی سنجش نمیدونم چرا تو حلش گفته ۳ عدد گلوگاهیه ولی گرافی کشیده که ۴ یعنی بزرگترین عدد توش هست به نظرتون سنجش درست گفته ؟من که جوابشو قبول ندارم مگه نباید ببزرگترین یالو گلوگاه بگیریم؟؟

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

به نظرم با توجه به توضیحات صورت سوال:
گ ۱ غلط هست چون فکر کنید گراف مثالی یک درخت با سه نود و دویال باشد یه طوری که دو نود با دو یال به یک نود متصل شده اند.(به شکل میوه گیلاس) فرض کنید وزن یکی از یال ها ۱ و دیگری ۵ باشد در این صورت عدد گلوگاه برابر ۵ هست نه ۱ که کمترین وزن هست.
گ ۴ هم غلط هست به مثال بالا توجه کنید.
به نظرم گ ۳ هم همواره برقرار نیست خوب با توجه به توضیحات صورت سوال عدد گلوگاه برابر با وزن سنگین ترین یال هست می دانیم در یگ گراف اگر دوری شامل یال با سنگین ترین وزن یاشد در این صورت در درخت پوشای مینیمم ان گراف، یال با سنگین ترین وزن وجود ندارد پس اگر گرافی داشته یاشیم که شامل این دور باشد درخت پوشای مینیمم ان حاوی این یال نیست.
به نظرم گ ۲ درست هست چون به نظرم درخت بیشینه همواره حاوی ماگزیمم یال هست. و با توجه به توضیحات صورت سوال عدد گلوگاه برابر با وزن سنگین ترین یال هست.
دوستان نظر شما چیه؟

من حرف rad.bahar قبول دارم ولی این در صورتی درست میشه که عدد گلوگاه کوچیکتر باشه.
ولی الان که صورت سوال چند بار خوندم فک کنم منظورش اینه که b که عدد گلوگاهی هست باید کوچیکتر بشه اونحایی که گفته عدد b بزرگترین عدد نباید مارو به اشتباه بندازه که حتما سنگترین یال هم همون هست نه! خط دوم سوالو بخونیم میگه اگر مسیری بین دو یال در این گراف باشه باید وزنش از b کمتر نباشه پس یعنی یال هایی هم وجود دارن که از عدد گلوگاه (b)بیشترن یعنی عدد گلوگاه از همه کمتر.

خوب حالا که از همه کمتره ما میدونیم اگر گرافی رو در نظر بگیریم که یالb هم در اون گراف هست از اونجایی که گراف رو هم دور دار در نظر بگیریم بخواییم درخت کمینه رو بدست بیاریم هیچ وقت این یال کمو(b) حذف نمیکنیم که کمینه رو بدست بیاریم چون هنوز یال های سنگیتر هم در گراف هستن ما اون هارو حذف میکنیم.پس باید به نظر من ۱و۳ درست بشه.سنجش داره اشتباه میگه در صورتی جواب ۲ میشد اگر در صورت سوال در خط دوم سوال میگفت اگر بین رئوس مسیر ما از b کوچیکتر بشه اون وقت اینجا عدد گلوگاه از همه وزن یال ها بزرگتر میشد جواب ۲ میشد.

بچه ها نظرتون حالا چیه ؟؟

به نظرتون این طوری میگم اثباتش به واقعیت نزدیکتره.

(۰۹ آذر ۱۳۹۲ ۰۸:۲۰ ب.ظ)tarane1992 نوشته شده توسط:  من حرف rad.bahar قبول دارم ولی این در صورتی درست میشه که عدد گلوگاه کوچیکتر باشه.
ولی الان که صورت سوال چند بار خوندم فک کنم منظورش اینه که b که عدد گلوگاهی هست باید کوچیکتر بشه اونحایی که گفته عدد b بزرگترین عدد نباید مارو به اشتباه بندازه که حتما سنگترین یال هم همون هست نه! خط دوم سوالو بخونیم میگه اگر مسیری بین دو یال در این گراف باشه باید وزنش از b کمتر نباشه پس یعنی یال هایی هم وجود دارن که از عدد گلوگاه (b)بیشترن یعنی عدد گلوگاه از همه کمتر.

خوب حالا که از همه کمتره ما میدونیم اگر گرافی رو در نظر بگیریم که یالb هم در اون گراف هست از اونجایی که گراف رو هم دور دار در نظر بگیریم بخواییم درخت کمینه رو بدست بیاریم هیچ وقت این یال کمو(b) حذف نمیکنیم که کمینه رو بدست بیاریم چون هنوز یال های سنگیتر هم در گراف هستن ما اون هارو حذف میکنیم.پس باید به نظر من ۱و۳ درست بشه.سنجش داره اشتباه میگه در صورتی جواب ۲ میشد اگر در صورت سوال در خط دوم سوال میگفت اگر بین رئوس مسیر ما از b کوچیکتر بشه اون وقت اینجا عدد گلوگاه از همه وزن یال ها بزرگتر میشد جواب ۲ میشد.

بچه ها نظرتون حالا چیه ؟؟

به نظرتون این طوری میگم اثباتش به واقعیت نزدیکتره.

حق با شما دوستان هست. اشتباه کردم عدد گلوگاه برابر وزن یال با کمترین وزن هست. با این حساب گزینه ۱ درسته گ ۴ هم درسته گ۳ هم همواره درست هست چون می دانیم در الگوریتم کروسکال در اولین مرحله سبک وزن ترین یال انتخاب میشه گ۲ هم غلط هست این گزینه برای کراف هایی درست است که یال با سبک ترین وزن در صورت حذف آن گراف همبندی خود را از دست بدهد فکر کنم یعنی حداقل شامل یک دور حاوی یال با سبک ترین وزن نباشند.
به نظرتان درست میگم؟

(۰۹ آذر ۱۳۹۲ ۱۰:۵۱ ب.ظ)rad.bahar نوشته شده توسط:  

(09 آذر ۱۳۹۲ ۰۸:۲۰ ب.ظ)tarane1992 نوشته شده توسط:  من حرف rad.bahar قبول دارم ولی این در صورتی درست میشه که عدد گلوگاه کوچیکتر باشه.
ولی الان که صورت سوال چند بار خوندم فک کنم منظورش اینه که b که عدد گلوگاهی هست باید کوچیکتر بشه اونحایی که گفته عدد b بزرگترین عدد نباید مارو به اشتباه بندازه که حتما سنگترین یال هم همون هست نه! خط دوم سوالو بخونیم میگه اگر مسیری بین دو یال در این گراف باشه باید وزنش از b کمتر نباشه پس یعنی یال هایی هم وجود دارن که از عدد گلوگاه (b)بیشترن یعنی عدد گلوگاه از همه کمتر.

خوب حالا که از همه کمتره ما میدونیم اگر گرافی رو در نظر بگیریم که یالb هم در اون گراف هست از اونجایی که گراف رو هم دور دار در نظر بگیریم بخواییم درخت کمینه رو بدست بیاریم هیچ وقت این یال کمو(b) حذف نمیکنیم که کمینه رو بدست بیاریم چون هنوز یال های سنگیتر هم در گراف هستن ما اون هارو حذف میکنیم.پس باید به نظر من ۱و۳ درست بشه.سنجش داره اشتباه میگه در صورتی جواب ۲ میشد اگر در صورت سوال در خط دوم سوال میگفت اگر بین رئوس مسیر ما از b کوچیکتر بشه اون وقت اینجا عدد گلوگاه از همه وزن یال ها بزرگتر میشد جواب ۲ میشد.

بچه ها نظرتون حالا چیه ؟؟

به نظرتون این طوری میگم اثباتش به واقعیت نزدیکتره.

حق با شما دوستان هست. اشتباه کردم عدد گلوگاه برابر وزن یال با کمترین وزن هست. با این حساب گزینه ۱ درسته گ ۴ هم درسته گ۳ هم همواره درست هست چون می دانیم در الگوریتم کروسکال در اولین مرحله سبک وزن ترین یال انتخاب میشه گ۲ هم غلط هست این گزینه برای کراف هایی درست است که یال با سبک ترین وزن در صورت حذف آن گراف همبندی خود را از دست بدهد فکر کنم یعنی حداقل شامل یک دور حاوی یال با سبک ترین وزن نباشند.
به نظرتان درست میگم؟

دوستانن دقت کنید که منظور سوال اینه که ممکنه بین دو راس چند مسیر باشه. ما از بین این مسیر ها باید مسیری رو انتخاب کنیم که پر هزینه ترین باشه. یال گلوگاه بزرگترین خروجی از مبدا یا مقصده.اپس گزینه ۱ غلطه. دقت کنین که گفته بزرگترین یال از بین "بی" ها
برای گزینه ۴ هم اگه وزن یال ها برابر باشه غلط میشه.
در حالت کلی با توجه به صورت سوال، عدد گلوگاه میشه بزرگترین یال گره مبدا یا مقصد که یال بعدی توی مسیر همه از اون بزرگترن.
برای غلط بودن گزینه ۳ حالتی رو در نظر بگیرید گرافی با ۵ نود با این مشخصات:
گره الف: ۴ یال با وزن های ۱ به ج،۲ به ب، ۳ به ه، ۴ به د
گره ب: یال با وزن ۲ به الف، یال با وزن ۲ به د، ۷ به ه
گره ج: ۱ به الف، ۶ به د
گره د: ۶ به ج، ۲ به ب، ۵ به ه
گره ه: ۵ به د، ۳ به الف، ۷ به ب
یال گلوگاه میشه ۴/ که توی درخت پوشای کمینه نیست. من نتونستم حالتی پیدا کنم که توی درخت پوشای بیشینه نباشه
این سوال از سوالاییه که گذاشتن بین رتبهای تک فاصله بیفته، اکثرا اشتباه جواب میدن. البته منم همین الان سوالو دیدم و ممکن بود با نگاه اول ۳ رو بزنم. نظرتون در مورد استدلالم چیه؟!
ببخشید فارسی نوشتم کیبورد قاطی میکرد.

من نظر اون دوستمونو قبول نمیکنم شاید به قول یکی از دوستان منظور سنجش این بوده کدوم غلطه .

من که این طوری میفهمم که اگر به فرض مسیری هم بین دو راس باشه نباید از b کمتر بشه. یعنی اینکه باید هر یالی در نظر میگیریم از b بیشتر بشه درسته که گفته که b بزرگترین وزنو داره ولی هر یالی در نظر بگیریم باید از b که بزرگ هم هست بزرگتر باشه پس یعنی b سبکترین یاله. اگر بفهمیم b سبکترین یاله هیچ وقت در یک دور یال یبک حذف نمیشه پس حتما در درخت کمینه ما هست.پس ۱و۳ درست میشه.

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

به قول دوستان همون غلط بودن منظور سوال بوده

آخرش چی شد؟
کدوم گزینه درسته؟

آخرش چی شد؟
کدوم گزینه درسته؟

(۱۴ بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)masoud67 نوشته شده توسط:  من بعد از دو ماه این سوالو دیدم و جالبه برام که چرا اینقدر رو این سوال بحث هست و جالبتر اینکه این طاهرپور پارسه چرا غلط جواب داده (هرچند ، از این غلطها کم نداشته)
صورت سوالو دقت کنید
۱/ گراف همبند و بی جهت ، پس بین هر دو راس مسیر وجود داره
۲/ گفته به ازای هر دو راس ، پس یعنی واسه بدست آوردن عدد گلوگاه باید تمام رئوس را دو دوتا با هم در نظر بگیریم
۳/ گفته بزرگترین b به ازای هر دو راس
پس با این سه فرض ما تعداد بسیار زیادی عدد گلوگاه میتونیم داشته باشیم که باید بزرگترینشو انتخاب کنیم
بزرگترین عدد گلوگاه مسلما بین دو راسی است که دو سر بزرگترین یال هستند. یکی از مسیر های بین این دو راس که دو سر بزرگترین یال هستند دقیقا همین یاله. پس چون این یال بزرگترین یال در گراف میشه پس به عنوان گلوگاه انتخاب میشه و گزینه ۲ صحیحه

مثلا تو همین شکلی که اون دوستمون گذاشتند
طبق صورت سوال گفته بین هر دو راس ، پس من میتونم هر دو راسی که عشقم کشید را انتخاب کنم
واسه همین من دو راس a و b را انتخاب میکنم
چند تا مسیر بین a , b هست. بسیار مسیر (چون نگفته مسیر ساده یا ابتدایی) و یکی از این مسیرها همون یال ۸ بین این دوتاست
پس من یه عدد گلوگاه واسه این درخت بدست آوردم با مقدار ۸
حالا هر کی تونست یکی بیشتر از این مقدار پیدا کنه ؛ کمتر هم پیدا کردید که فایده نداره چون ما قراره بزرگترین را انتخاب کنیم

جواب طاهرپور را خداییش یه دور ببینید. قشنگ معلومه این بنده خدا بدون اینکه صورت سوال رو بخونه، رفته و طبق درخت گلوگاه (نه عدد گلوگاهی که تو صورت سوال گفته شده) جواب داده

آقا من هرچی گفتم گوش نکردند

Sent from my SM-T210R using Tapatalk

(۱۴ بهمن ۱۳۹۲ ۱۱:۰۹ ب.ظ)hoomanab نوشته شده توسط:  آقا من هرچی گفتم گوش نکردند

خیلی واضحه سوال. به شرطی که دقیقا فرضها رو در نظر بگیری و از طرفی ، با درخت گلوگاه اشتباه نکنی