سوال ۴

یک گراف c-نشان، یک زوج مرتب $(G,F)$ است، به‌طوری‌که $G$ یک گراف و $F$‌ تابعی است که به هر کدام از رئوس $G$، یک نماد از بین اعداد ۰ تا c نسبت می‌دهد به طوری که اگر $F$ به دو راس از گراف نمادهای مساوی نسبت دهد، آن نماد صفر باشد.

نوعی عبارت به نام عبارت‌های c-نشان‌گذار برای نشان دادن بعضی از گراف‌های c-نشان به روش بازگشتی زیر تعریف می‌شود.

• اگر $i$ عددی بین ۱ و c باشد، $C_i$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی $(G,F)$ است که $G$‌ گرافی شامل یک راس است که $F$‌ به آن نماد $i$‌را نسبت می‌دهد.
• اگر $i$ عددی بین ۱ و c و $A$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G,F)$ باشد، $AD_i$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G',F')$ است که:

$$ F'(v) = \begin{cases} F(v) & F(v)\ne i \\ 0 & F(v)=i \end{cases}$$

• اگر $i$ عددی بین ۱ و c و $A$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G,F)$ باشد، $AC_i$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G',F')$ است که G' از افزودن راس $u$ به $G$ به‌دست می‌آید و

$$ F'(v) = \begin{cases} i & v=u \\ F(v) & F(v)\ne i \\ 0 & F(v)=i \end{cases}$$

• اگر $i$ و $j$ عددهای متمایز بین ۱ و $c$ و $A$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G,F)$ باشد، $AE_{i,j}$ یک عبارت c-نشان‌گذار نشان‌دهنده‌ی گراف c-نشان $(G',F)$ است که G'از افزودن یک یال بین رئوس با نمادهای $i$ و $j$ (در صورت وجود) در $G$ به‌دست می‌آید. البته گراف ساده باقی می‌ماند.
• اگر$A_1$ و $A_2$ عبارت‌های c-نشان‌گذار به ترتیب نماینده‌ی گراف‌های c-نشان $(G_1,F_1)$ و $(G_2,F_2)$ باشند، $A_1 \oplus A_2$ نماینده‌ی گراف c-نشانی است که از اجتماع گراف‌های $G_1$ و $G_2$ و سپس منطبق کردن رئوسی از آن‌ها که نمادهای غیر صفر مساوی دارند به‌دست می‌آید. البته پس از انجام عمل، یال‌ها‌ی دوگانه (در صورت تشکیل) ساده می‌شوند.

برای مثال $(C_1C_2E_{1,2}C_3E_{2,3}) \oplus (C_1C_3E_{1,3})$ نشان‌پذیر می‌نامیم، اگر تابع $F$ و عبارت c-نشان‌گذار $A$ وجود داشته باشد، که $A$ نشان‌دهنده‌ی $(G,F)$ باشد.

الف) ثابت کنید یک گراف ۲-نشان‌پذیر است اگر و تنها اگر جنگل باشد.

ب)حداکثر تعداد یال‌های یک گراف n-راسی k-نشان‌پذیر چقدر است؟

• سوال بعد
• سوال قبل