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

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 گراف کنزر (زنگ‌تفريح شماره‌ي 57)
گراف کنزر (زنگ‌تفريح شماره‌ي 57)زنگ تفريح كامپيوتر
در نظریه گراف‌ یک سری از گراف‎ها وجود دارند که خاصند و به‌دلیل خصوصیاتشان و طرز ساخت یا کاربردی ترکیبیاتی و غیره از اهمیت خاصی برخوردارند مانند گراف پترسون که حتما درمورد آن اطلاعاتی دارید. گراف کنزر یکی از این گراف‎هاست...

 
مقدمه


در نظریه گراف‌ یک سری از گراف‎ها وجود دارند که خاصند و به دلیل خصوصیاتشان و طرز ساخت یا کاربردی ترکیبیاتی و غیره از اهمیت خاصی برخوردارند مانند گراف پترسون که حتما درمورد  آن اطلاعاتی دارید.
گراف کنزر یکی از این گراف‎هاست، این گراف‌ها به نام مارتین کنزر نام‌گذاری شده‌اند که
برای اولین بار آنها را در سال ۱۹۵۵ بررسی کرد.


این گراف که با KGn,k نشان داده می‎شود، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k-عضوی از یک مجموعه‎ی n-عضوی است.
بین دو رأس این گراف‌ یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند (اشتراکشان تهی باشد).
با توجه به روش ساخت یک گراف کنزر KGn,k به‌سادگی می‎توان به خصوصیات زیر اشاره کرد:

1.  تعداد راس‎های گراف کنزر برابر است.

2. هر راس در گراف کنزر با راس دیگر مجاور است.

3.  گراف کامل n-رأسی، گراف کنزر KGn,1 است و در شکل 1 هم مشاهده می‎شود.
 

شكل 1



4. در گراف کنزر اگر k=n/2 باشد، و n هم عددی زوج باشد، آن‎گاه  هر راس تنها با یک راس دیگر مجاور است و بنابراین گراف موردنظر شبیه نردبانی است که   پله دارد و در شکل 2 هم دو نمونه از این گراف‎ها نشان داده شده‌اند.


شكل 2


5. گراف  کنزر KG5,2 با گراف پترسون ایزومورف است و در شکل 3 دیده می‎شود.

شكل 3


6.  کنزر حدس زده بود که  عدد رنگی گراف KGn,k دقیقاً برابر n-2k+2 است. Lovasz در سال ۱۹۷۸ و Joshua در سال ۲۰۰۲ برای این فرمول اثبات‌هایی ارائه دادند و در سال ۲۰۰۴ Matoušek اثباتی کاملاً ترکیبیاتی برای آن پیدا کرد.


مطالعه‌ي بيشتر:

1388/4/25لينک مستقيم

فرستنده :
ناشناس HyperLink HyperLink 1389/2/14
مـتـن : خیلی خوب عالیییییییییییییییییییییییییییییییییییییییییییی!!!!!!

فرستنده :
ناشناس HyperLink HyperLink 1389/2/14
مـتـن : خیلی ازمطالبتون خوشم نیامد

فرستنده :
1 HyperLink HyperLink 1388/11/6
مـتـن : توضیحات تکمیلی ؟
پاسـخ :http://mathworld.wolfram.com/KneserGraph.html



http://en.wikipedia.org/wiki/Kneser_graph

فرستنده :
ناشناس HyperLink HyperLink 1388/11/6
مـتـن : باعرض سلام ميخواستم از مطالب بسيار مفيد سايت تشكر كنم اما متاسفانه هيچ وقت نميتوانم مطاب روي سايت را دركامپيوتر ذخيره كنم چون خط wordسايت قديمي هست و درword هاي جديد خطها به هم ميريزند.
پاسـخ : سلام
برای ذخیره‌ی مطلب‌ها بهتر است آن را به صورت فایل html ذخیره کنید.
برای این کار در منوی بالایی مرورگر خود ابتدا گزینه‌ی «File» و سپس گزینه‌ی «Save as» را انتخاب نمایید.

فرستنده :
HyperLink HyperLink 1388/11/6
مـتـن : mamnoon mataleb jalebi dare

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

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  3465
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  3465