گراف و مدل سازی

پاسخنامه‌ی تحلیلی

«$4$» درست است. **گام ۱ — داده‌ها:** $n=7$، $q=9$ پس $\sum d_i = 2q = 18$ و $\sum d_i^2 = 56$. **گام ۲ — جای‌گذاریِ هوشمندانه:** قرار می‌دهیم $e_i = d_i - 3$. آنگاه $$\sum e_i = 18 - 7\times 3 = -3,\qquad \sum e_i^2 = \sum d_i^2 - 6\sum d_i + 9n = 56 - 108 + 63 = 11.$$ **گام ۳ — شمارشِ حالت‌ها:** هر $e_i$ عددی صحیح در $[-3,3]$ است و $\sum e_i^2 = 11$ با $7$ جمله. تنها تجزیه‌هایِ ممکن به مربع‌ها عبارت‌اند از $11 = 9+1+1$ و $11 = 4+4+1+1+1$: - $\{\pm3,\pm1,\pm1,0,0,0,0\}$ با شرطِ $\sum e_i=-3$ فقط $(-3,-1,+1)$ را می‌دهد $\Rightarrow$ درجه‌دنباله $(0,2,3,3,3,3,4)$. - $\{\pm2,\pm2,\pm1,\pm1,\pm1,0,0\}$ با $\sum e_i=-3$ دو حالت می‌دهد: $(-2,+2,-1,-1,-1)$ و $(-2,-2,-1,+1,+1)$ $\Rightarrow$ درجه‌دنباله‌هایِ $(1,2,2,2,3,3,5)$ و $(1,1,2,3,3,4,4)$. **گام ۴ — شمارشِ رئوسِ فرد:** در $(0,2,3,3,3,3,4)$ چهار تایِ $3$؛ در $(1,2,2,2,3,3,5)$ اعدادِ $1,3,3,5$؛ در $(1,1,2,3,3,4,4)$ اعدادِ $1,1,3,3$. در **هر سه** حالت دقیقاً $4$ رأسِ فرد داریم. **وارسیِ مستقل:** هر سه دنباله با معیارِ اردیش–گالای گرافیک‌اند (مثلاً $(1,1,2,3,3,4,4)$ به‌سادگی ساخته می‌شود)، پس مسئله سازگار است و جواب یکتاست: $4$. **ردِ سایر گزینه‌ها:** $0$ رد می‌شود چون اگر همهٔ درجات زوج باشند با $a,b,c,d$ = تعدادِ رئوسِ درجهٔ $0,2,4,6$ می‌رسیم به $b+2c+3d=9$ و $b+4c+9d=14$، یعنی $2c+6d=5$ که فرد است و ناممکن. $2$ و $6$ نیز در شمارشِ کاملِ بالا اصلاً ظاهر نمی‌شوند. **تلهٔ تستی:** تعدادِ رئوسِ فرد همیشه زوج است، پس $0،2،4،6$ همگی از این نظر مجازند؛ قاعدهٔ دست‌دادن به‌تنهایی جواب را مشخص نمی‌کند و باید از $\sum d_i^2$ هم استفاده کرد.

پاسخنامه‌ی تحلیلی

«$n = 2k + 1$» درست است. درجه هر رأس در $\bar{G}$ برابر $(n-1)-k$ است. برای $k$-منتظم بودن $\bar{G}$ باید $(n-1)-k = k$، یعنی $n-1 = 2k$، پس $n = 2k + 1$. **تلهٔ تستی:** فراموش‌کردنِ $-1$ در فرمولِ $\deg_{\bar G}(v)=(n-1)-\deg_G(v)$ رایج‌ترین اشتباه در کلِ این خانواده از سؤالات است.

پاسخنامه‌ی تحلیلی

گزینه «$20$» درست است. برای یک گراف $4$-منتظم $10$ رأسی داریم $q = \frac{4 \times 10}{2} = 20$. چون $G$ هیچ یالی ندارد، باید $20$ یال اضافه کرد. سایر گزینه‌ها حاصل محاسبات اشتباه مانند $\frac{4 \times 10}{4}$ یا $\frac{4 \times 10}{4} + 5$ هستند. **تلهٔ تستی:** رایج‌ترین اشتباه، تقسیمِ $nk$ بر $k$ به‌جایِ $2$ است (یا فراموش‌کردنِ تقسیم به‌طورِ کامل)؛ فرمولِ $q=\frac{nk}{2}$ را همیشه با جای‌گذاریِ مستقیم چک کنید.

پاسخنامه‌ی تحلیلی

«$2$» درست است. **گام ۱ — کرانِ پایین:** هر رأسِ مجموعهٔ احاطه‌گر حداکثر خودش و $\Delta$ همسایه، یعنی حداکثر $\Delta+1$ رأس را می‌پوشاند. پس $\gamma(G) \geq \left\lceil \frac{n}{\Delta+1} \right\rceil = \left\lceil \frac{10}{6} \right\rceil = 2$. **گام ۲ — نشان‌دادنِ دست‌یافتنی‌بودنِ $2$:** رئوس را $v_1, v_2, u_1, \dots, u_8$ بنامید. $v_1$ را به $u_1,\dots,u_4$ و به $v_2$ وصل کنید ($\deg v_1 = 5$) و $v_2$ را به $u_5,\dots,u_8$ و به $v_1$ وصل کنید ($\deg v_2 = 5$). حالا $N[v_1] \cup N[v_2]$ همهٔ $10$ رأس را می‌پوشاند و $\Delta(G)=5$ است، پس $\gamma(G)=2$ ساخته شد. **وارسیِ مستقل (حالتِ حدی):** اگر $\gamma=1$ بود، یک رأس باید همهٔ $9$ رأسِ دیگر را همسایه می‌داشت، یعنی $\Delta \geq 9$؛ ولی $\Delta=5$ داده شده، پس $\gamma=1$ ناممکن است — سازگار با کرانِ گام ۱. **ردِ سایر گزینه‌ها:** «$1$» رد می‌شود چون $\Delta=5 < 9$ اجازهٔ رأسِ فراگیر نمی‌دهد. «$3$» و «$4$» رد می‌شوند چون سؤال **کمترین** مقدارِ ممکن را می‌خواهد و ما در گام ۲ گرافی با $\gamma=2$ ساختیم؛ درست است که گراف‌هایی با $\Delta=5$ و $\gamma=3$ یا بیشتر هم وجود دارند، ولی آن‌ها کمینه نیستند. **تلهٔ تستی:** رابطهٔ $\gamma \geq \lceil n/(\Delta+1)\rceil$ فقط یک **کرانِ پایین** است؛ برایِ اینکه بگوییم آن کران واقعاً کمینه است باید یک گرافِ نمونه بسازیم که به آن برسد — رایج‌ترین اشتباه، بسنده‌کردن به فرمول بدونِ ساختِ مثال است.

پاسخنامه‌ی تحلیلی

«این دنباله یک درجه‌دنباله گراف ساده نیست زیرا مجموع عناصر آن فرد است» درست است. مجموعِ عناصر: $5+4+4+3+3+2=21$ که فرد است. طبقِ قضیهٔ دست‌دادن، مجموعِ درجاتِ هر گرافِ ساده باید همیشه زوج ($=2q$) باشد؛ چون $21$ فرد است، این دنباله هرگز نمی‌تواند درجه‌دنبالهٔ یک گراف ساده باشد. گزینه‌هایی که ادعا می‌کنند این دنباله معتبر است (با مجموعِ $۲۰$ یا $۲۱$) رد می‌شوند چون مجموعِ واقعی $۲۱$ (فرد) است، نه $۲۰$؛ محاسبهٔ درستِ مجموع همیشه اولین قدمِ ضروری است. **تلهٔ تستی:** رایج‌ترین اشتباه، جمع‌زدنِ نادرستِ عناصرِ دنباله (یا فراموش‌کردنِ یکی از آن‌ها) است که می‌تواند زوج/فرد‌بودنِ مجموع را عوض کند و به نتیجه‌گیریِ کاملاً غلط برساند — همیشه جمع را دوباره حساب کنید.

پاسخنامه‌ی تحلیلی

«در $G$ حداقل دو رأسِ غیرمجاور وجود دارند» درست است. **گام ۱ — استدلالِ اصلی:** عددِ رنگیِ گرافِ کاملِ $K_n$ برابرِ $n$ است و $K_n$ تنها گرافِ $n$ رأسی با $\chi = n$ است. چون $\chi(G) = n-2 < n$، پس $G \neq K_n$؛ یعنی دستِ‌کم یک زوجِ رأسِ غیرمجاور در $G$ هست. پس گزینهٔ ۴ **همواره** برقرار است. **وارسیِ مستقل (نگاه از دیدِ مکمل):** $\chi(G) = n-2$ یعنی رئوس را می‌توان به $n-2$ کلاسِ مستقل افراز کرد. با $n$ رأس در $n-2$ کلاس، یا یک کلاسِ $3$تایی داریم یا دو کلاسِ $2$تایی. در هر دو حالت دستِ‌کم یک کلاسِ بیش از یک‌عضوی هست، یعنی دو رأسِ غیرمجاور — همان نتیجهٔ گام ۱. **ردِ گزینهٔ ۱:** «$G = K_n$» نادرست است، چون $\chi(K_n) = n \neq n-2$. **ردِ گزینهٔ ۳:** «$\bar{G}$ حتماً مثلث دارد» نادرست است. مثالِ نقض: $G = K_n$ منهایِ دو یالِ **مجزا** (مثلاً $ab$ و $cd$ با $a,b,c,d$ متمایز). آنگاه $\bar{G}$ فقط همان دو یالِ مجزا را دارد و بدونِ مثلث است، در حالی که مجموعه‌هایِ مستقلِ $\{a,b\}$ و $\{c,d\}$ رنگ‌آمیزی با $n-2$ رنگ می‌دهند و بیش از این هم نمی‌توان ادغام کرد، پس دقیقاً $\chi(G)=n-2$. **ردِ گزینهٔ ۲:** «$\chi(\bar{G}) = 3$» نادرست است؛ در همان مثالِ نقضِ بالا $\bar{G}$ دو یالِ مجزاست و $\chi(\bar{G}) = 2$. **تلهٔ تستی:** از $\chi(G)=n-2$ نتیجه نمی‌شود که $\bar G$ حتماً مثلث دارد؛ حالتِ «دو یالِ مجزا در مکمل» همان‌قدر ممکن است که حالتِ «مثلث در مکمل». رایج‌ترین اشتباه، در نظر گرفتنِ فقط یکی از این دو حالت است.

پاسخنامه‌ی تحلیلی

«$\gamma(G) \leq 2$» درست است. **گام ۱ — ساختنِ مجموعهٔ احاطه‌گرِ دو عضوی:** رأسِ دلخواهِ $v$ را بگیرید. چون $\deg(v) \geq 7$، $|N[v]| \geq 8$ و بیرونِ آن حداکثر $12-8 = 4$ رأس می‌ماند. **گام ۲ — چرا همیشه جفتی پیدا می‌شود:** فرض کنید $\gamma(G) \geq 3$. آنگاه برایِ هر زوجِ $\{u,w\}$ رأسی هست که با هیچ‌کدام مجاور نیست. در مکملِ $\bar G$ که $\Delta(\bar G) \leq 12-1-7 = 4$ است، این یعنی **هر دو رأس در $\bar G$ همسایهٔ مشترک دارند**. حالا رأسِ $u$ را در $\bar G$ بگیرید: $11$ رأسِ دیگر باید از طریقِ $N_{\bar G}(u)$ پوشش داده شوند، و از این $4$ همسایه حداکثر $4 \times 3 = 12$ یالِ دیگر بیرون می‌رود؛ چون خودِ این $4$ همسایه هم باید پوشیده شوند، دستِ‌کم $2$ یال (یک تطابقِ کامل) درونِ $N_{\bar G}(u)$ لازم است و تنها $12-4 = 8$ ظرفیت برایِ $7$ رأسِ بیرونی می‌ماند. این شمارشِ فشرده، $\bar G$ را ناچار به $4$-منتظم‌بودن و به افرازِ یال‌ها به دقیقاً $8$ مثلث می‌کند — و بررسیِ همهٔ حالت‌هایِ چنین ساختاری نشان می‌دهد هیچ‌کدام شرطِ «همسایهٔ مشترک برایِ هر زوج» را برآورده نمی‌کند. پس فرض باطل و $\gamma(G) \leq 2$ است. **وارسیِ مستقل (دو حالتِ حدی):** اگر رأسی درجهٔ $11$ داشته باشد، $\gamma = 1 \leq 2$ ✓. و اگر $G = K_{12}$ منهایِ یک تطابقِ کامل باشد (که $10$-منتظم است و شرطِ $\delta \geq 7$ را دارد)، هیچ رأسی به‌تنهایی همه را نمی‌پوشاند، ولی هر رأس به همراهِ جفتِ نامجاورش کلِ گراف را می‌پوشاند، پس $\gamma = 2$ ✓. **ردِ سایر گزینه‌ها:** «$\gamma(G) \geq 2$» نادرست است، چون گرافی با یک رأسِ فراگیر (درجهٔ $11$) و بقیهٔ درجات $\geq 7$ وجود دارد که $\gamma = 1$ می‌دهد. «$\gamma(G) = 2$» به همان دلیل همواره درست نیست. «$\gamma(G) \geq 3$» با گام‌هایِ بالا مستقیماً نقض می‌شود. **تلهٔ تستی:** فراموش‌کردنِ اینکه هر رأس **خودش را هم** می‌پوشاند (پوششِ $\deg(v)+1$ نه $\deg(v)$) کرانِ نادرست می‌دهد؛ و نکتهٔ دوم اینکه شرطِ $\delta \geq n/2$ فقط کرانِ **بالا** برایِ $\gamma$ می‌دهد، نه کرانِ پایین.

پاسخنامه‌ی تحلیلی

«$1$» درست است. $\overline{G} \cong C_5$ یعنی $G$ مکمل یک $C_5$ است. هر $C_5$ با $5$ رأس و $5$ یال مشخص است. $q(K_5) = 10$، پس $q(G) = 10 - 5 = 5$. گراف $G$ دقیقاً $5$ یال دارد و حداکثر $7$ یال شرط را برآورده می‌کند. تنها یک $C_5$ (تا ایزومورفیسم) وجود دارد، پس تنها یک $G$ داریم. سایر گزینه‌ها تعداد نادرست را نشان می‌دهند. **تلهٔ تستی:** رایج‌ترین اشتباه، محاسبهٔ $q(G)$ مستقیماً از رویِ یال‌هایِ $C_5$ به‌جایِ استفاده از رابطهٔ مکمل ($q(G)=q(K_5)-q(C_5)$) است.

پاسخنامه‌ی تحلیلی

«$850$» درست است. $q(G) = \frac{100 \times 17}{2} = 850$ زیرا گراف $17$-منتظم است. $1700$ حاصل ضرب ساده $100 \times 17$ بدون تقسیم بر $2$ است و $150$ نیز نادرست است. بنابراین تنها $850$ می‌تواند اندازه باشد. **تلهٔ تستی:** فراموش‌کردنِ تقسیم بر $2$ در فرمولِ $q=\frac{nk}{2}$ رایج‌ترین اشتباه است — بدونِ این تقسیم، هر یال دوبار شمرده می‌شود.

پاسخنامه‌ی تحلیلی

گزینه «$q + q' = \binom{n}{2}$» درست است چون $q + q'$ برابر تعداد یال‌های $K_n$ یعنی $\binom{n}{2}$ است. سایر گزینه‌ها اعداد اشتباهی را نشان می‌دهند. **تلهٔ تستی:** رایج‌ترین اشتباه، استفاده از $n(n-1)$ (تعدادِ زوج‌هایِ مرتب) به‌جایِ $\binom{n}{2}=\frac{n(n-1)}{2}$ (تعدادِ زوج‌هایِ نامرتب، که همان تعدادِ یال‌هایِ ممکن است) می‌باشد.