گراف و جادو
=======================

بعضی از اوقات مسائل ترکیبیاتی با ایده های بسیار جذاب به گراف مدل سازی می شوند. در فضای گراف ها با ابزار های قدرتمندی که داریم (قضیه ها و شهود خوب روی گراف) می توان مسائل را به راحتی حل کرد.

در این بخش قصد داریم شما را با چند مثال با جادوی مدل سازی با گراف آشنا کنیم!

درخت؟
------------

مجموعه :math:`S` را مجموعه اعداد 1 تا :math:`n` تعریف می کنیم و :math:`n` زیرمجموعه :math:`A_1,A_2,...,A_n` را از مجموعه :math:`S` در نظر می گیریم که همه متمایزند. ثابت کنید عددی مثل :math:`x` وجود دارد که اگر :math:`x` را از :math:`A_i` ها حذف کنیم همچنان :math:`A_i` ها با هم متمایز باشند.

جواب
~~~~~~~~~~

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

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

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

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

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

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



مثلث ها؟
--------------

فرض کنید :math:`S` مجموعه ای :math:`2^n+1` عضوی باشد و :math:`f({x,y})` تابعی باشد که ورودی آن یک زیرمجموعه دو عضوی از :math:`S` است و خروجی آن یک عدد بین 0 تا :math:`2^{n-1}-1` می باشد. همچنین می دانیم به ازای هر :math:`x,y,z` که سه عضو متفاوت :math:`S` هستند از بین :math:`f({x,y}), f({x,z}), f({y,z})` یکی از آنها برابر جمع دو تای دیگر است. شما باید ثابت کنید :math:`x,y,z` وجود دارند که :math:`f({x,y}), f({x,z}), f({y, z})` هر سه برابر با 0 هستند.