تعداد مؤلفه های همبندی گرافی که گره هایش $n$-تایی های مرتب ۰ و ۱ هستند و دو گره که دقیقا در دو مؤلفه متفاوت هستند یال دارند را بیابید.

Question

گراف $G$ را این گونه تعریف کنید که مجموعهٔ گره‌هایش تمام $n$-تایی‌های مرتب ساخته‌شده با ۰ و ۱ باشد و دو گره همسایه هستند (با یک یال به هم وصل شده‌اند) هر گاه در دقیقا دو مؤلفه‌شان با هم متفاوت باشند. تعداد مؤلفه‌های همبندی این گراف را بیابید.

Comments

@Rad1999 خودتان چه تلاشی کرده‌اید؟ آیا برای چند $n$ کوچک مانند ۱، ۲، ۳ و ۴ امتحان کره‌اید که بعد به حدسی برسید که بخواهید آن را ثابت کنید؟

---

برای nهای کوچکتر حساب نکردم.ولی از آنجا که مولفه یک گراف زیر گراف های همبند ماکسیمال آن است. و با حذف یال برش حد اکثر یک مولفه اضافه میشود.پس اگر دو بار xوyرا جابجا کنیم یعنی دو مولفه اضافه شده پس مولفه های گراف ۳تا میشه....البته هیچ اطمینانی از این استدلا ندارم

---

@Rad1999 لطفا با شناسهٔ کاربری‌تان وارد شوید و سپس پست بگذارید که بعد بتوانید آن را ویرایش کنید. متوجه از «پس» به بعد حرف‌تان نمی‌شوم. چجوری ۳ تا بدست آوردید؟ برای هر $n$ عدد ۳ بدست آوردید؟ برای حالت $n=1$ یک گراف دو گره‌ای بدون یال دارید. تعداد مؤلفه‌هایش ۲ می‌شود نه ۳. برای $n=2$ نیز تعداد مؤلفه‌ها نیز ۲ می‌شود. پس یعنی دست‌کم دو مثال نقض برای پاسخ‌تان یافت شد. دوباره از نو فکر کنید. بعلاوه چرا با حذف یک یال برشی «حداکثر» یک مؤلفه اضافه می‌شود؟ جمله‌تان یعنی یا مؤلفه‌ای اضافه نمی‌شود یا یکی اضافه می‌شود ولی حالت اول نباید رخ بدهد و گرنه با برشی‌بودن یالی که در موردش حدف می‌زنید تناقض دارد. در جمله‌تان ظاهرا «حداکثر» باید با «حداقل» جابجا شود.

Answer 1

نخست برای $n$های کوچک امتحان کنید. اگر $n=1$ آنگاه گراف‌تان دو گره دارد که با $(0)$ و $(1)$ متناظر هستند. چون هر یک، یک یک‌تایی هستند (یک مؤلفه دارند) پس اصلا نمی‌توانید دو مؤلفهٔ متفاوت از آنها پیدا کنید پس یالی هم نخواهید داشت. گراف‌تان دو گرهٔ گوشه‌گیر (منزوی) دارد پس دو مؤلفهٔ همبندی دارد.

اکنون $n=2$. گراف‌تان چهار گره دارد متناسب با $(0,0)$، $(0,1)$، $(1,0)$، $(1,1)$. تنها دو زوج می‌توانید بیابید که در دو مؤلفه متفاوت باشند یعنی $(0,0)$ و $(1,1)$ و دیگری $(0,1)$ و $(1,0)$. پس دو یال بیشتر ندارید. گراف‌تان دو یال مجزا می‌شود پس دو مؤلفهٔ همبندی دارد.

برای $n=3$ را نیز خودتان رسم کنید، که توصیه می‌کنم حتما انجام دهید و جتی برای $n=4$ را هم انجام دهید.

می‌توانید ادامه بدهید. در هر صورت مشاهده‌ای که می‌کنید این است که همیشه دو مؤلفهٔ همبندی دارید و اگر یک گرهٔ دلخواه بردارید، آنگاه تمام گره‌‌های دیگر یا در تعداد فردی مؤلفه با آن متفاوت هستند یا در تعداد زوجی مؤلفه، اگر تعداد مؤلفه‌های متفاوت‌شان زوج باشد آنگاه در مؤلفهٔ همبندیِ یکسانی با آن گره هستند، و گر نه در مؤلفهٔ دیگر هستند.

اکنون بیاییم چیزی را که می‌بینیم را ثابت کنیم. $n$ را یک عدد دلخواه ولی ثابت بگیرید. یک گرهٔ دلخواه را انتخاب و سپس آن را ثابت بگیرید. ما آن را $u$ می‌نامیم. یک گره که در تعداد زوجی مثلا $2k$ مؤلفه با $u$ متفاوت است حتما با یک مسیر به $u$ وصل می‌شود. چون کافی است گرهٔ $u$ را در ابتدای مسیر قرار دهید، سپس گرهٔ دوم را همان عددهای $u$ بگذارید ولی ۲ تا از $2k$ مؤلفهٔ متفاوت را برایش تغییر دهید. گرهٔ سوم را عددهای گرهٔ دوم بگذارید و فقط ۲ تا از $2k$ مؤلفهٔ متفاوت که قبلا انتخاب نشده‌اند را برایش تغییر دهید. به همین ترتیب تا همهٔ $2k$ مؤلفهٔ متفاوت تغییر کنند. مشخص است که چون هر دو گرهٔ پشت سر هم دقیقا در دو مؤلفه متفاوت هستند پس با یال متصل هستند. پس یک مسیر به درازای $k$ بین $u$ و گرهٔ مطلوب ساختیم. اکنون اگر نشان دهیم که یک گره که در تعداد فردی مؤلفه با $u$ متفاوت است نمی‌تواند با هیچ مسیری به $u$ وصل شود کار تمام می‌شود.

یک مسیر دلخواه با شروه از $u$ در نظر بگیرید. شروع کنید از سمت $u$ به حرکت کردن. اگر گره‌ای که به آن می‌رسید در تعداد زوجی مؤلفه با $u$ متفاوت است که هیچ و ادامه دهید. به اولین گره‌ای که فکر می‌کنید گرهٔ بعدی‌اش می‌تواند تعداد فردی مؤلفهٔ متفاوت از $u$ داشته‌باشد که رسیدید بایستید. فرض کنید $2k$ مؤلفهٔ متفاوت از $u$ دارد. چون گرهٔ بعدی باید با یک یال متصل شود پس باید از گرهٔ پیشین دقیقا در دو مؤلفه متفاوت باشد. ۳ حالت بیشتر نداریم. ۱- یا هر دو مؤلفه قرار از مؤلفه‌های در حال حاضر شبیه به $u$ انتخاب شده‌اند که با تغییر آنها تعداد مؤلفه‌های متفاوت گرهٔ جدید برابر با $2k+2$ می‌شود و زوج است. ۲- یک مؤلفهٔ در حال حاضر مشابه به $u$ و یک مؤلفهٔ در حال حاضر متفاوت از $u$ انتخاب شده‌اند که با تغییر آنها تعداد مؤلفه‌های متفاوت از $u$ برابر با $2k+1-1=2k$ می‌شود. ۳- دو مؤلفهٔ در حال حاضر متفاوت از $u$ انتخاب شده‌اند که با تغییر آنها تعداد مؤلفه‌های متفاوت از $u$ برابر می‌شوند با $2k-2$. در هر سه صورت دوباره تعداد مؤلفه‌های متفاوت از $u$ روج شدند. پس گرهٔ بعدی نمی‌تواند یک گره با تعداد مؤلفهٔ متفاوت فرد باشد. چون در گام دلخواهی در مسیر این را نشان دادیم پس یعنی تمام گره‌ای این مسیر باید تعداد زوجی مؤلفهٔ متفاوت از $u$ داشته‌باشند. چون مسیر را دلخواه گرفته بودیم. پس نشان دادیم گرهٔ $u$ به هیچ گره‌ای که در تعداد فردی مؤلفه از آن متفاوت است متصل نیست. و چون $u$ دلخواه بود اثبات ادعایمان کامل است.

نه تنها ثابت کردیم دو مؤلفهٔ همبندی داریم بلکه حتی می‌توانیم دو مؤلفه را سریع نشان دهیم. کافیست گرهٔ $u$ را مثلا گرهٔ با همهٔ درایه‌های صفر بگیرید. آنگاه دو مؤلفه به این شکل خودشان را به شما نشان خواهند داد. مجموعهٔ گره‌های با تعداد فرد ۱ و مجموعهٔ تمام گره‌های با تعداد زوج ۱.