گراف و جادو¶

جواب¶

چه زمان حذف کردن عددی مثل \(x\) از مجموعه ها موجب ایجاد دو مجموعه مساوی می شود؟ تنها زمانی که دو مجموعه مثل \(A_i, A_j\) وجود داشته باشند که تنها تفاوت آن ها در \(x\) باشند. یعنی همه اعداد به جز \(x\) یا در هر دو آمده باشند یا در هیچکدام نیامده باشند.

حالا مسئله را به اینصورت به گراف مدل سازی می کنیم که \(n\) راس در نظر می گیریم که هر کدام نماینده \(A_i\) ها هستند. بین دو راس \(u,v\) یالی با وزن \(w\) بکشید اگر تنها تفاوت \(A_u, A_v\) در عضو \(w\) باشد. حالا مسئله معادل این است که ثابت کنیم وزنی وجود دارد که بین یال ها نیامده است!

طبق مدل سازی گرافمان هر بار که یالی با وزن \(w\) را طی کنیم عضو \(w\) از مجموعه فعلی مان حذف یا به آن اضافه می شود. پس در هر گذر بسته باید از هر وزن زوج تا داشته باشیم (زیرا وضعیت بودن یا نبودن هر عضو باید زوج بار تغییر کند تا بعد از طی کردن گذر به همان مجموعه اولیه برسیم).

حالا برهان خلف بزنید که از هر وزن حداقل یک یال با این وزن داشته باشیم. پس از هر وزن یک یال دلخواه با این وزن را انتخاب کنید و گراف \(n\) یالی \(G\) را تشکیل دهید.

ابتدا واضح است که گراف \(G\) دور ندارد. زیرا در صورت وجود دور باید از هر وزن زوج تا داشته باشیم که چون از هر وزن دقیقا یکی داریم ممکن نیست. پس \(G\) باید جنگل باشد. از طرفی گفتیم \(G\) دقیقا \(n\) یال دارد و می دانیم این ممکن نیست (زیرا بیشینه یال در جنگل مربوط به درخت است که \(n-1\) یال دارد).

پس می توانیم از تناقض حاصل نتیجه بگیریم وزنی هست که در بین یال ها ظاهر نشده است که حکم مسئله مان را ثابت می کند.