نظرات خصوصی

من اصلاً نظرات خصوصی را نمی‌خوانم. ناراحت هستید از اسم مستعار استفاده کنید.

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

حل تمرین ۳.۷ وزیرانی

یکی ۴ تا کامنت گذاشته حل این را خواسته. بفرمایید:

سوال این بوده که اگر یک گراف متریک داشته باشیم و یک زیرمجموعه از رأسهای آن را برداریم، آیا تطابق کمینه روی این زیرمجموعه کمتر از گراف اصلی خواهد بود یا خیر؟

یکی دیگه خواسته این را توضیح بدهم: گراف سمت راستی گراف اصلی است. به ازای هر سه تا رأسی می‌توانید چک کنید که نامساوی مثلث برقرار است، پس متریک است. (چون به وضوح دو تا شرط دیگر را دارد). سمت چپ تطابق روی V یا خط راست و تطابق روی V' با خط‌چین نشان داده شده که وزن آنها به ترتیب ۲ و ۳ می‌شود. پس چیزی که در صورت سوال پرسیده که آیا تطابق روی V کران بالا برای تطابق روی V' است جوابش می‌شود: نه نیست.