زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۱:۰۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

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

ارسال:
  

آرمین پرسیده:

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

سلام

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

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

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

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


فایل‌(های) پیوست شده

۱
ارسال:
  

Jooybari پاسخ داده:

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

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

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

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

ارسال:
  

آرمین پاسخ داده:

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

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

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

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

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

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

ارسال:
  

zimenswall پاسخ داده:

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

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

۰
ارسال:
  

zimenswall پاسخ داده:

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

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

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

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

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

ارسال:
  

آرمین پاسخ داده:

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

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

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

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

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

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

ارسال:
  

zimenswall پاسخ داده:

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

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

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

ارسال:
  

آرمین پاسخ داده:

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

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

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

ارسال:
  

zimenswall پاسخ داده:

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

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

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

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

تشکر از شما
یافتن تمامی ارسال‌های این کاربر

ارسال: #۱۰
  

آرمین پاسخ داده:

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

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

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

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

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

۰
ارسال: #۱۱
  

tayebe68 پاسخ داده:

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

یک سوال آسون!

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

ارسال: #۱۲
  

Jooybari پاسخ داده:

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

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

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

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

ارسال: #۱۳
  

tayebe68 پاسخ داده:

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

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


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


فایل‌(های) پیوست شده



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  رشته ای مهندسی کامپیوتر sanjeshserv1 ۰ ۱,۰۰۷ ۰۲ تیر ۱۴۰۱ ۰۴:۴۸ ب.ظ
آخرین ارسال: sanjeshserv1
  دانلود جزوه ریاضیات گسسته amiraraz ۱ ۳,۲۱۵ ۰۴ خرداد ۱۴۰۱ ۰۳:۵۵ ب.ظ
آخرین ارسال: start2
  معرفی منبع مناسب برای ارشد گسسته saharitst ۲۱ ۲۴,۴۶۶ ۲۲ دى ۱۴۰۰ ۰۶:۱۱ ب.ظ
آخرین ارسال: YasiAli
  [دانلود] حل تشریحی کنکور ارشد مهندسی کامپیوتر و آی تی ۸۷ تا ۹۲ good-wishes ۳۰ ۴۹,۷۱۵ ۲۰ فروردین ۱۴۰۰ ۰۲:۱۷ ب.ظ
آخرین ارسال: sima84
  بعد ۶ سال اومدم، ارشد مهندسی کامپیوتر کسی هست؟؟ seyed_eng ۷ ۵,۵۰۸ ۱۱ آبان ۱۳۹۹ ۰۷:۴۷ ق.ظ
آخرین ارسال: iraj.leo
Question [] مراجع مهندسی کامپیوتر [] itslady ۰ ۱,۷۵۷ ۲۷ اردیبهشت ۱۳۹۹ ۰۴:۵۰ ب.ظ
آخرین ارسال: itslady
  ریاضی گسسته روزن ویرایش ۷ همراه با کتاب حل تمرین ها livestrong ۱۲ ۱۹,۴۹۳ ۱۷ اردیبهشت ۱۳۹۹ ۰۴:۳۷ ب.ظ
آخرین ارسال: raziyeh.karbasi
  مشکل در حل تست ۲۲ فصل اول کتاب گسسته یوسفی pure.yaser ۷ ۸,۳۱۷ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۵۴ ب.ظ
آخرین ارسال: mohsentafresh
Information فروش کتابهای گسسته گریمالدی ۴ جلد + راهنمای حل مسائل tabassomesayna ۱ ۳,۳۰۹ ۲۷ فروردین ۱۳۹۹ ۰۴:۵۶ ب.ظ
آخرین ارسال: tabassomesayna
  قبول شدگان گروه مهندسی کامپیوتر ۹۷ F.N.44 ۵۱ ۲۷,۱۴۰ ۰۷ مهر ۱۳۹۸ ۱۲:۱۶ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close