زنگ‌تفریح تصادفی

 زنگ‌تفریح‌های پربازدید
 آرشيو
 
 سه‌رنگ‌پدیری در گره‌ها
سه‌رنگ‌پدیری در گره‌هازنگ تفريح رياضي
زنگ‌تفریح شماره ۱۱۴

 

در زنگ‌تفریح ۱۰۲ با نظریه‌ی گره‌ها و در زنگ‌تفریح شماره ۱۱۳ با چگونگی ساختن یک ناوردا برای گره‌ها با استفاده از «قضیه‌ی رایدمایستر» آشنا شدید. در این زنگ تفریح می‌خواهیم یک ناوردای ساده بسازیم به‌نام «سه‌رنگ‌پذیری» و با استفاده از آن خواهیم دید که «گره هشت» با «گره سه‌پر» و «ناگره» هم‌ارز نیست. البته این ناوردا به نسبت سایر ناورداهایی که تا کنون برای گره‌ها ساخته شده است (از جمله چندجمله‌ای‌ها) بسیار ضعیف‌ است. اما ساختن آن در عوض ساده است و در این زنگ‌تفریح به‌راحتی می‌توان آن را معرفی کرد. 
 
در ابتدا مفهوم «سه‌رنگ‌پذیری» را برای یک گره معرفی می‌کنیم. اگر به تصویر یک گره دقت کنید متوجه می‌شوید که هر تصویر گره از تعدای خم پیوسته تشکیل شده است. در واقع بخشی از گره که از «زیر یک تقاطع» شروع می‌شود و به «زیر یک تقاطع دیگر» می‌رود یک بخش پیوسته از گره است. با چند قاعده می‌خواهیم یک گره را با «دقیقا سه رنگ» رنگ کنیم. 
 
۱.
از هر سه رنگ در رنگ‌آمیزی گره استفاده کنیم.
۲.
رنگ‌هایی که به یک تقاطع می‌رسند دقیقا باید «یک-رنگ» یا «سه-رنگ» باشند. یعنی نباید تقاطع «دو-رنگ» در رنگ‌آمیزی‌مان وجود داشته باشد. 
 
گره‌ای را که بتوان با دو قاعده‌ی بالا رنگ کرد را «سه‌رنگ‌پذیر» نامیم. به‌عنوان مثال می‌توان دید که گره سه‌پر سه‌رنگ‌پذیر است در حال که ناگره سه‌رنگ‌پذیر نیست.
 
 
 
همان‌طور که در زنگ‌تفریح پیش دیدیم برای اینکه ببینم سه‌رنگ‌پذیری یک ناوردا است بایستی آن را برای سه حرکت رایدمایستر بررسی کنیم. در شکل زیر این مساله را بررسی کرده‌ایم:
 
 
همان‌طور که در شکل دیده می‌شود سه‌رنگ‌پذیری در اثر سه حرکت رایدمایستر تغییر نمی‌کند. پس نتیجه‌ی زیر حاصل می‌شود:
 
اگر یک گره سه‌رنگ‌پذیر باشد، هر تصویر هم‌ارز با آن هم باید سه‌رنگ‌پذیر باشد.
 
یا به بیان دیگر اگر یک گره سه‌رنگ‌پذیر باشد و دیگری نباشد این دو گره با هم هم‌ارز نیستند.
 
حال به مثال قبلی برمی‌گردیم، نتیجه‌ی ساده این است که گره‌ سه‌پر با ناگره هم‌ارز نیست. به بیان شهودی گره سه‌پر را نمی‌توان بدون بریدن در بخشی از آن باز کرد. 
 
با استفاده از ناوردای سه‌رنگ‌پذیری می‌توان گره‌های زیادی را از ناگره تمییز داد، با این حال این ناوردا همه جا هم به‌دردبخور نیست. مثلا اگر سعی کنیم «گره هشت» را با سه رنگ و با قاعده‌های بالا رنگ کنیم شکست خواهیم خورد:
 
 
 
اما با استفاده از ابزارهای دیگر می‌توان نشان داد که گره‌ هشت با ناگره هم‌ارز نیست.
 

 

1390/9/20 لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 
 المپياد رياضي

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

     

 

فعاليت‌هاي علمي

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.