سوال ۴
یک گراف c-نشان، یک زوج مرتب (G,F) است، بهطوریکه G یک گراف و F تابعی است که به هر کدام از رئوس G، یک نماد از بین اعداد ۰ تا c نسبت میدهد به طوری که اگر F به دو راس از گراف نمادهای مساوی نسبت دهد، آن نماد صفر باشد.
نوعی عبارت به نام عبارتهای c-نشانگذار برای نشان دادن بعضی از گرافهای c-نشان به روش بازگشتی زیر تعریف میشود.
اگر i عددی بین ۱ و c باشد، Ci یک عبارت c-نشانگذار نشاندهندهی (G,F) است که G گرافی شامل یک راس است که F به آن نماد iرا نسبت میدهد.
اگر i عددی بین ۱ و c و A یک عبارت c-نشانگذار نشاندهندهی گراف c-نشان (G,F) باشد، ADi یک عبارت c-نشانگذار نشاندهندهی گراف c-نشان (G′,F′) است که:
F′(v)={F(v)F(v)≠i0F(v)=i
F′(v)={iv=uF(v)F(v)≠i0F(v)=i
اگر i و j عددهای متمایز بین ۱ و c و A یک عبارت c-نشانگذار نشاندهندهی گراف c-نشان (G,F) باشد، AEi,j یک عبارت c-نشانگذار نشاندهندهی گراف c-نشان (G′,F) است که G'از افزودن یک یال بین رئوس با نمادهای i و j (در صورت وجود) در G بهدست میآید. البته گراف ساده باقی میماند.
اگرA1 و A2 عبارتهای c-نشانگذار به ترتیب نمایندهی گرافهای c-نشان (G1,F1) و (G2,F2) باشند، A1⊕A2 نمایندهی گراف c-نشانی است که از اجتماع گرافهای G1 و G2 و سپس منطبق کردن رئوسی از آنها که نمادهای غیر صفر مساوی دارند بهدست میآید. البته پس از انجام عمل، یالهای دوگانه (در صورت تشکیل) ساده میشوند.
برای مثال (C1C2E1,2C3E2,3)⊕(C1C3E1,3) نشانپذیر مینامیم، اگر تابع F و عبارت c-نشانگذار A وجود داشته باشد، که A نشاندهندهی (G,F) باشد.
الف) ثابت کنید یک گراف ۲-نشانپذیر است اگر و تنها اگر جنگل باشد.
ب)حداکثر تعداد یالهای یک گراف n-راسی k-نشانپذیر چقدر است؟