حل تمرین ۳.۷ وزیرانی
يكشنبه, ۱۴ خرداد ۱۳۹۶، ۱۰:۲۱ ق.ظ
یکی ۴ تا کامنت گذاشته حل این را خواسته. بفرمایید:
سوال این بوده که اگر یک گراف متریک داشته باشیم و یک زیرمجموعه از رأسهای آن را برداریم، آیا تطابق کمینه روی این زیرمجموعه کمتر از گراف اصلی خواهد بود یا خیر؟
یکی دیگه خواسته این را توضیح بدهم: گراف سمت راستی گراف اصلی است. به ازای هر سه تا رأسی میتوانید چک کنید که نامساوی مثلث برقرار است، پس متریک است. (چون به وضوح دو تا شرط دیگر را دارد). سمت چپ تطابق روی V یا خط راست و تطابق روی V' با خط‌چین نشان داده شده که وزن آنها به ترتیب ۲ و ۳ می‌شود. پس چیزی که در صورت سوال پرسیده که آیا تطابق روی V کران بالا برای تطابق روی V' است جوابش می‌شود: نه نیست.
Let G = (V, E) be a graph with edge costs satisfying the triangle inequality, and V' < V be a set of even cardinality. Prove or disprove: The cost
of a minimum cost perfect matching on V' is bounded above by the cost of
a minimum cost perfect matching on V.