Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:گراف:سوال ۴

سوال ۴

یک گراف 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

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

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) باشند، A1A2 نماینده‌ی گراف c-نشانی است که از اجتماع گراف‌های G1 و G2 و سپس منطبق کردن رئوسی از آن‌ها که نمادهای غیر صفر مساوی دارند به‌دست می‌آید. البته پس از انجام عمل، یال‌ها‌ی دوگانه (در صورت تشکیل) ساده می‌شوند.

برای مثال (C1C2E1,2C3E2,3)(C1C3E1,3) نشان‌پذیر می‌نامیم، اگر تابع F و عبارت c-نشان‌گذار A وجود داشته باشد، که A نشان‌دهنده‌ی (G,F) باشد.

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

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


ابزار صفحه