سوالهای آخر کتاب تراویسان

سوال ۱ می‌گوید ثابت کنید کسر لایتون-رائو بعد از جایگزین کردن کوتاه‌ترین مسیر روی جواب LP به جای وزن یالها به مقدار کمتری می‌رسد و همچنان یک جواب برای LP هست.
خب برای این کار به LP مربوطه یک نگاه می‌اندازیم. قید‌های آن نصفشان مربوط به شبه‌متر هستند که تغییر نمی‌کنند و فقط یک قید است که می‌گوید جمع وزن یالهای H با یک ضریب d برابر E[H]/E[G] می‌شود.

طبیعتاً برای قیدهای شبه‌متر بودن مشکلی پیش نمی‌آید چون کوتاهترین مسیر در گراف خودش یک متر است (نامساوی مثلث برایش صادق است و نامنفی هم هست اگر یالها نامنفی باشند).

قید دیگر هم که خودش گفته تأثیری در جواب ندارد و فقط برای نرمال‌سازی است.

پس حالا فقط می‌ماند این که ثابت کنیم که این جواب کمتری می‌دهد. چون ضریب G_{u,v} تغییر نکرده است ولی ضریب d_{u,v} کم شده پس این جواب از قبلی بهتر است.

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