تالار گفتمان مانشت
سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - تعریف تطابق ماکزیمال - نسخه‌ی قابل چاپ

سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - تعریف تطابق ماکزیمال - آرمین - ۱۱ آبان ۱۳۹۲ ۱۲:۵۷ ب.ظ

سلام

تو کتاب گسسته ی پوران پژوهش نوشته شده که:
«تطابق ماکسیمال در یک گراف، تطابقی است که تا حد امکان بیشترین رئوس را با هم جور کند.»

در هر حالی که تو سئوال گسسته ای که پارسال اومده، گفته شده بود که:
«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»

این دو تعریف معادل نیستند... درسته؟
چون طبق تعریف اول، تمام تطابق های ماکسیمال یک گراف، تعداد یال های برابری دارن... (و طبق این تعریف، گزینه ی «۴» درست میشه)
در حالی که طبق تعریف دوم، به هیچ وجه چنین نتیجه ای رو نمیشه کرد... (و طبق این تعریف، گزینه ی «۳» درست میشه)

آیا من اشتباه می کنم؟ Huh

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - zimenswall - 11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ

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

و فکر کنم یک گراف اگر چندتا تطابق ماکسیمال داشته باشه، حتما همشون اندازه برابری دارند.
پس چه تعریف توی سوال را در نظر بگیریم و چه در نظر نگیریم عبارت ب نادرسته.

البته خیلی مطمئن نیستم و فقط نظرم را گفتم
در ضمن به مورد الف هم شک دارم که درست باشه. چون گفته تطابق دلخواه، پس ظاهرا میشه هر مجموعه راسی و یالی که دلمون خواست را انتخاب کنیم که اجتماعشون شاید دوبخشی نشه.

اگر این مورد را هم کسی توضیح بده ممنون میشیم

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - آرمین - ۱۱ آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ

(۱۱ آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:  من هنوز این قسمت را نخوندم ولی یه چیزایی یادمه.
توی کتاب علی رضوانی هم نوشته که بیشترین رئوس باهم جور بشن.

و فکر کنم یک گراف اگر چندتا تطابق ماکسیمال داشته باشه، حتما همشون اندازه برابری دارند.
پس چه تعریف توی سوال را در نظر بگیریم و چه در نظر نگیریم عبارت ب نادرسته.

البته خیلی مطمئن نیستم و فقط نظرم را گفتم
در ضمن به مورد الف هم شک دارم که درست باشه. چون گفته تطابق دلخواه، پس ظاهرا میشه هر مجموعه راسی و یالی که دلمون خواست را انتخاب کنیم که اجتماعشون شاید دوبخشی نشه.

اگر این مورد را هم کسی توضیح بده ممنون میشیم
ممنونم دوست عزیز از پاسختون...
اما اگه تمام تطابق های ماکسیمال اندازشون برابر باشه... اون وقت وقتی اندازه ی یکی رو در عددی بزرگتر از یک ضرب می کنیم، عدد حاصله بزرگتر از اندازه ی هر تطابق ماکسیمال دیگه ای میشه...
و در این صورت عبارت «ب» درست میشه... Huh

در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - zimenswall - 11 آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ

(۱۱ آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:  
در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...

یه ابهامی برام پیش اومده که در عبارت الف، اون دو تا تطابق دلخواهی که در نظر میگیرم آیا باید مجموعه رئوسی که افراز میکنیم در هر دو یکسان باشه یا میتونه متفاوت هم باشه؟
چون اگه متفاوت باشه، ظاهرا الف میتونه غلط باشه

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - آرمین - ۱۱ آبان ۱۳۹۲ ۰۹:۱۲ ب.ظ

(۱۱ آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:  
در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...

یه ابهامی برام پیش اومده که در عبارت الف، اون دو تا تطابق دلخواهی که در نظر میگیرم آیا باید مجموعه رئوسی که افراز میکنیم در هر دو یکسان باشه یا میتونه متفاوت هم باشه؟
چون اگه متفاوت باشه، ظاهرا الف میتونه غلط باشه
هم می تونن متفاوت باشن هم می تونن یکسان باشن...
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود! Big Grin

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - zimenswall - 11 آبان ۱۳۹۲ ۰۹:۳۱ ب.ظ

(۱۱ آبان ۱۳۹۲ ۰۹:۱۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:  
در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...

یه ابهامی برام
هم می تونن متفاوت باشن هم می تونن یکسان باشن...
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود! Big Grin

درست میفرمایید. چیزی که توی ذهن من بود را پیاده کردم دیدم دور ایجاد میشه ولی نه دور به طول فرد.
ظاهرا آدم تا دست به قلم نشه و ننویسه نمیتونه چیزی را اثبات کنه.
صحبت شما درست و صحیح بود.

تشکر از شما

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - آرمین - ۱۱ آبان ۱۳۹۲ ۱۱:۱۵ ب.ظ

(۱۱ آبان ۱۳۹۲ ۰۹:۳۱ ب.ظ)zimenswall نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۹:۱۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:  
(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:  
در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...

یه ابهامی برام
هم می تونن متفاوت باشن هم می تونن یکسان باشن...
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود! Big Grin

درست میفرمایید. چیزی که توی ذهن من بود را پیاده کردم دیدم دور ایجاد میشه ولی نه دور به طول فرد.
ظاهرا آدم تا دست به قلم نشه و ننویسه نمیتونه چیزی را اثبات کنه.
صحبت شما درست و صحیح بود.

تشکر از شما
خواهش می کنم...
آره، دقیقا تا آدم دست به قلم نشه انگار مسائل یه جور دیگن... بعد یه جور دیگه میشن!
همیشه تو ریاضیات این موضوع هست...
مرسی از شما...

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - Jooybari - 12 آبان ۱۳۹۲ ۱۲:۲۴ ق.ظ

سلام. این تعریف در حالت کلی اشتباهه:

«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»

ولی چون سوال این جمله رو درست مطرح کرده باید درست درنظر بگیریم. بهتر بود یه اسم غیر از ماکزیمال انتخاب میکرد. جواب همون ۳ باید باشه. مثال نقضش هم گراف به شکل Z هست. یکبار دو یال موازی و یکبار یال مورب انتخاب میشه.
حرف شما رو قبول دارم.

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - آرمین - ۱۲ آبان ۱۳۹۲ ۰۱:۵۵ ب.ظ

(۱۲ آبان ۱۳۹۲ ۱۲:۲۴ ق.ظ)Jooybari نوشته شده توسط:  سلام. این تعریف در حالت کلی اشتباهه:

«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»

ولی چون سوال این جمله رو درست مطرح کرده باید درست درنظر بگیریم. بهتر بود یه اسم غیر از ماکزیمال انتخاب میکرد. جواب همون ۳ باید باشه. مثال نقضش هم گراف به شکل Z هست. یکبار دو یال موازی و یکبار یال مورب انتخاب میشه.
حرف شما رو قبول دارم.
خیلی ممنون آقای جویباری بابت پاسختون...
الان کتاب گریمالدی رو دیدم... همون تعریف پوران رو نوشته... و تصدیق حرف شما که تعریف سنجش از تطابق ماکسیمال اشتباه هست... و باید نام دیگه ای انتخاب میشد برای این تعریف...

اما واقعا این سئوال ناجوان مردانه بوده...
کسی که قبلا تطابق ماکسیمال رو جور دیگه ای تو ذهنش در نظر داشته، سر کنکور حتی یک درصد هم فکر نمی کنه تطابق ماکسیمال «سازمان سنجش» متفاوت با تطابق ماکسیمالی هست که قبلا یاد گرفته... و متاسفانه سئوال رو اشتباه جواب میده... Sad

سر کنکور حتی اگه سئوال از گراف دوبخشی هم بدن، سئوالو خوب بخونیم شاید منظورش یه دوبخشی دیگه ورژن «سنجشی» بود!
بعضی حرکت های سازمان سنجش واقعا عجیبه!!!

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - zimenswall - 12 آبان ۱۳۹۲ ۰۲:۰۵ ب.ظ

(۱۲ آبان ۱۳۹۲ ۰۱:۵۵ ب.ظ)آرمین نوشته شده توسط:  سر کنکور حتی اگه سئوال از گراف دوبخشی هم بدن، سئوالو خوب بخونیم شاید منظورش یه دوبخشی دیگه ورژن «سنجشی» بود!
بعضی حرکت های سازمان سنجش واقعا عجیبه!!!
به قول استادم که میگفت آدم گهگاهی باید تست های کنکور ارشد را غلط بزنه، چون به احتمال زیاد با کلید سنجش صحیح در میاد.

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - tayebe68 - 10 بهمن ۱۳۹۲ ۱۰:۵۶ ق.ظ

یک سوال آسون!

زیر مجموعه ی سره یعنی چی ؟

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - Jooybari - 10 بهمن ۱۳۹۲ ۰۶:۳۴ ب.ظ

(۱۰ بهمن ۱۳۹۲ ۱۰:۵۶ ق.ظ)tayebe68 نوشته شده توسط:  یک سوال آسون!

زیر مجموعه ی سره یعنی چی ؟

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

RE: تعریف تطابق ماکزیمال و سئوال ۴۵ گسسته مهندسی کامپیوتر ۹۲ - tayebe68 - 11 بهمن ۱۳۹۲ ۰۹:۳۳ ب.ظ

شکلی که پیوست کردم مثال نقض برای قسمت الفه!
دو تا خط سبز یک تطابق کازیمال و دو یال قرمز یک تطابق دیگه اند


با این حساب الف رد میشه؟