پایان نامه > کتابخانه مرکزی دانشگاه صنعتی شاهرود > علوم ریاضی > مقطع کارشناسی ارشد > سال 1392
پدیدآورندگان:
اعظم شاهسواری نجف آبادی [پدیدآور اصلی]، میثم علیشاهی[استاد راهنما]، غلامرضا امیدی [استاد راهنما]
چکیده: به کمترین تعداد رنگ های مورد نیاز برای رنگ آمیزی رئوس Hعدد رنگی (χ(H گفته می شود به طوریکه هیچ یال E_i از H که 1<|E_i| وجود نداشته باشد که همه ی رئوس آن دارای رنگ یکسان باشند. همچنین کمترین تعداد رنگ های مورد نیاز برای رنگ آمیزی یالهای H، به طوریکه هر کلاس رنگی به شکل یک تطابق باشد را اندیس رنگی (عدد رنگی یالی) H گوییم و با (χ′(H نشان می دهیم. به عبارت دیگر، در رنگ آمیزی یالی ابرگرافها هیچ دو یال متقاطع رنگ یکسان ندارند. از آنجا که محاسبه ی دقیق اندیس رنگی ابرگرافها ساده نمی باشد، بنابراین در این پایان نامه سعی می کنیم آنرا با کران مشخص کنیم. برای اینکار قضیه ی معروف شانون را بیان و تعمیم آنرا برای حالت های مختلفی از یک ابرگراف معرفی می کنیم تا بتوانیم از نتایج مربوط به آن کران های مختلف را برای انواع ابرگرافها به دست آوریم، حتی در بسیاری از موارد برای رنگ آمیزی از الگوریتم حریصانه استفاده می کنیم تا بتوانیم به یک کران خوب دست پیدا کنیم. برای انواع خاص ابرگرافهای یکنواخت، کران الون و کیم را که به صورت حدس است ارائه می کنیم و سپس آنرا برای ابرگرافهای یکنواخت که متقاطع نیز باشند، ثابت می کنیم. در نهایت از این حقیقت که گرافها حالت خاصی از ابرگرافها هستند، استفاده کرده و قضیهی ویزینی که معروف ترین قضیه در مورد اندیس رنگی گرافهاست را بیان می کنیم، سپس با به کارگیری قضایای مربوط به اندیس رنگی برای گرافها و همچنین دوگانگی گرافهای چندگانه و گرافهای یالی، یک کران بالا را برای گراف های چندگانه ارائه می دهیم. همچنین از تعمیم قضیه ی ویزینگ در حالتهای مختلف یک ابرگراف استفاده های بسیاری می شود. برخی از مسائل هنوز باز می باشند.
کلید واژه ها (نمایه ها):
#ابرگراف #اندیس رنگی #عدد رنگی
محل نگهداری: کتابخانه مرکزی دانشگاه صنعتی شاهرود
یادداشت: حقوق مادی و معنوی متعلق به دانشگاه صنعتی شاهرود می باشد.
تعداد بازدید کننده:
پایان نامه های مرتبط (بر اساس کلیدواژه ها)