سلام
تو کتاب گسسته ی پوران پژوهش نوشته شده که:
«تطابق ماکسیمال در یک گراف، تطابقی است که تا حد امکان بیشترین رئوس را با هم جور کند.»
در هر حالی که تو سئوال گسسته ای که پارسال اومده، گفته شده بود که:
«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»
این دو تعریف معادل نیستند... درسته؟
چون طبق تعریف اول، تمام تطابق های ماکسیمال یک گراف، تعداد یال های برابری دارن... (و طبق این تعریف، گزینه ی «۴» درست میشه)
در حالی که طبق تعریف دوم، به هیچ وجه چنین نتیجه ای رو نمیشه کرد... (و طبق این تعریف، گزینه ی «۳» درست میشه)
آیا من اشتباه می کنم؟
من هنوز این قسمت را نخوندم ولی یه چیزایی یادمه.
توی کتاب علی رضوانی هم نوشته که بیشترین رئوس باهم جور بشن.
و فکر کنم یک گراف اگر چندتا تطابق ماکسیمال داشته باشه، حتما همشون اندازه برابری دارند.
پس چه تعریف توی سوال را در نظر بگیریم و چه در نظر نگیریم عبارت ب نادرسته.
البته خیلی مطمئن نیستم و فقط نظرم را گفتم
در ضمن به مورد الف هم شک دارم که درست باشه. چون گفته تطابق دلخواه، پس ظاهرا میشه هر مجموعه راسی و یالی که دلمون خواست را انتخاب کنیم که اجتماعشون شاید دوبخشی نشه.
اگر این مورد را هم کسی توضیح بده ممنون میشیم
(۱۱ آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط: من هنوز این قسمت را نخوندم ولی یه چیزایی یادمه.ممنونم دوست عزیز از پاسختون...
توی کتاب علی رضوانی هم نوشته که بیشترین رئوس باهم جور بشن.
و فکر کنم یک گراف اگر چندتا تطابق ماکسیمال داشته باشه، حتما همشون اندازه برابری دارند.
پس چه تعریف توی سوال را در نظر بگیریم و چه در نظر نگیریم عبارت ب نادرسته.
البته خیلی مطمئن نیستم و فقط نظرم را گفتم
در ضمن به مورد الف هم شک دارم که درست باشه. چون گفته تطابق دلخواه، پس ظاهرا میشه هر مجموعه راسی و یالی که دلمون خواست را انتخاب کنیم که اجتماعشون شاید دوبخشی نشه.
اگر این مورد را هم کسی توضیح بده ممنون میشیم
اما اگه تمام تطابق های ماکسیمال اندازشون برابر باشه... اون وقت وقتی اندازه ی یکی رو در عددی بزرگتر از یک ضرب می کنیم، عدد حاصله بزرگتر از اندازه ی هر تطابق ماکسیمال دیگه ای میشه...
و در این صورت عبارت «ب» درست میشه...
در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...
(۱۱ آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...
یه ابهامی برام پیش اومده که در عبارت الف، اون دو تا تطابق دلخواهی که در نظر میگیرم آیا باید مجموعه رئوسی که افراز میکنیم در هر دو یکسان باشه یا میتونه متفاوت هم باشه؟
چون اگه متفاوت باشه، ظاهرا الف میتونه غلط باشه
(۱۱ آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:هم می تونن متفاوت باشن هم می تونن یکسان باشن...(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
دیدم امکان نداره گراف حاصل از اجتماع ۲ تطابق، دور به طول فرد داشته باشه...
و گرافی هم که دور به طول فرد نداشته باشه، قطعا دوبخشی هست...
یه ابهامی برام پیش اومده که در عبارت الف، اون دو تا تطابق دلخواهی که در نظر میگیرم آیا باید مجموعه رئوسی که افراز میکنیم در هر دو یکسان باشه یا میتونه متفاوت هم باشه؟
چون اگه متفاوت باشه، ظاهرا الف میتونه غلط باشه
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود!
(۱۱ آبان ۱۳۹۲ ۰۹:۱۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:هم می تونن متفاوت باشن هم می تونن یکسان باشن...(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
یه ابهامی برام
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود!
درست میفرمایید. چیزی که توی ذهن من بود را پیاده کردم دیدم دور ایجاد میشه ولی نه دور به طول فرد.
ظاهرا آدم تا دست به قلم نشه و ننویسه نمیتونه چیزی را اثبات کنه.
صحبت شما درست و صحیح بود.
تشکر از شما
(۱۱ آبان ۱۳۹۲ ۰۹:۳۱ ب.ظ)zimenswall نوشته شده توسط:خواهش می کنم...(11 آبان ۱۳۹۲ ۰۹:۱۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۸:۲۰ ب.ظ)zimenswall نوشته شده توسط:هم می تونن متفاوت باشن هم می تونن یکسان باشن...(11 آبان ۱۳۹۲ ۰۵:۲۲ ب.ظ)آرمین نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۲:۵۶ ب.ظ)zimenswall نوشته شده توسط:در مورد عبارت «الف» هم من واسه خودم چند تا مثال زدم...
یه ابهامی برام
اما در هر حالت، این طور که من بررسی کردم دور به طول فرد ایجاد نمیشه...
اگه مثال نقضی پیدا کردین، لطفا بگین... شایدم واقعا غلط بود!
درست میفرمایید. چیزی که توی ذهن من بود را پیاده کردم دیدم دور ایجاد میشه ولی نه دور به طول فرد.
ظاهرا آدم تا دست به قلم نشه و ننویسه نمیتونه چیزی را اثبات کنه.
صحبت شما درست و صحیح بود.
تشکر از شما
آره، دقیقا تا آدم دست به قلم نشه انگار مسائل یه جور دیگن... بعد یه جور دیگه میشن!
همیشه تو ریاضیات این موضوع هست...
مرسی از شما...
سلام. این تعریف در حالت کلی اشتباهه:
«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»
ولی چون سوال این جمله رو درست مطرح کرده باید درست درنظر بگیریم. بهتر بود یه اسم غیر از ماکزیمال انتخاب میکرد. جواب همون ۳ باید باشه. مثال نقضش هم گراف به شکل Z هست. یکبار دو یال موازی و یکبار یال مورب انتخاب میشه.
حرف شما رو قبول دارم.
(۱۲ آبان ۱۳۹۲ ۱۲:۲۴ ق.ظ)Jooybari نوشته شده توسط: سلام. این تعریف در حالت کلی اشتباهه:خیلی ممنون آقای جویباری بابت پاسختون...
«تطابق ماکسیمال در یک گراف، تطابقی است که زیرمجموعه ی سره ی تطابق دیگری نباشد.»
ولی چون سوال این جمله رو درست مطرح کرده باید درست درنظر بگیریم. بهتر بود یه اسم غیر از ماکزیمال انتخاب میکرد. جواب همون ۳ باید باشه. مثال نقضش هم گراف به شکل Z هست. یکبار دو یال موازی و یکبار یال مورب انتخاب میشه.
حرف شما رو قبول دارم.
الان کتاب گریمالدی رو دیدم... همون تعریف پوران رو نوشته... و تصدیق حرف شما که تعریف سنجش از تطابق ماکسیمال اشتباه هست... و باید نام دیگه ای انتخاب میشد برای این تعریف...
اما واقعا این سئوال ناجوان مردانه بوده...
کسی که قبلا تطابق ماکسیمال رو جور دیگه ای تو ذهنش در نظر داشته، سر کنکور حتی یک درصد هم فکر نمی کنه تطابق ماکسیمال «سازمان سنجش» متفاوت با تطابق ماکسیمالی هست که قبلا یاد گرفته... و متاسفانه سئوال رو اشتباه جواب میده...
سر کنکور حتی اگه سئوال از گراف دوبخشی هم بدن، سئوالو خوب بخونیم شاید منظورش یه دوبخشی دیگه ورژن «سنجشی» بود!
بعضی حرکت های سازمان سنجش واقعا عجیبه!!!
(۱۲ آبان ۱۳۹۲ ۰۱:۵۵ ب.ظ)آرمین نوشته شده توسط: سر کنکور حتی اگه سئوال از گراف دوبخشی هم بدن، سئوالو خوب بخونیم شاید منظورش یه دوبخشی دیگه ورژن «سنجشی» بود!به قول استادم که میگفت آدم گهگاهی باید تست های کنکور ارشد را غلط بزنه، چون به احتمال زیاد با کلید سنجش صحیح در میاد.
بعضی حرکت های سازمان سنجش واقعا عجیبه!!!
یک سوال آسون!
زیر مجموعه ی سره یعنی چی ؟
(۱۰ بهمن ۱۳۹۲ ۱۰:۵۶ ق.ظ)tayebe68 نوشته شده توسط: یک سوال آسون!
زیر مجموعه ی سره یعنی چی ؟
سلام. منظور زیرمجموعه هایی هستن که برابر با مجموعه مرجع نیستن. درواقع حداقل یک عضو از مجموعه اصلی کمتر دارن.
به عبارت دیگه هر مجموعه زیرمجموعه خودش هست ولی زیر مجموعه سره خودش نیست.
شکلی که پیوست کردم مثال نقض برای قسمت الفه!
دو تا خط سبز یک تطابق کازیمال و دو یال قرمز یک تطابق دیگه اند
با این حساب الف رد میشه؟