پایان نامه > کتابخانه مرکزی دانشگاه صنعتی شاهرود > علوم ریاضی > مقطع کارشناسی ارشد > سال 1392
پدیدآورندگان:
محمود تردستی [پدیدآور اصلی]، صادق رحیمی شعرباف مقدس[استاد راهنما]، میثم علیشاهی[استاد راهنما]
چکیده: برای گراف ،Gتابع c : V (G) −→ ℵ را یک رنگ آمیزی مجاز گوییم هرگاه برای هر (uv ∈ E(G داشته باشیم (c(u) ̸= c(v مجموع رنگی متناظر با رنگآمیزی c را برابر با (Σu∈V (G)c(u تعریف میکنیم و مجموع رنگی ،Σ(G) ،G را کمترین مقدار ممکن برای مجموع رنگی، در میان همه ی رنگ آمیزی های مجاز G قرار میدهیم. همچنین کمترین تعداد رنگی که برای آن، میتوان یک رنگ آمیزی، با مجموع رنگ یکسان با مجموع رنگی گراف G پیدا کرد را قدرت رأسی ،s(G) ،G مینامیم. در این پایان نامه، ابتدا با مرور بر تحقیقات گذشته، با روند ایجاد مسأله ی مجموع رنگی و بسط و گسترش این مفهوم آشنا خواهیم شد و گستره ی آن را در علومی نظیر مهندسی و الکترونیک، با بیان کاربردی از مسأله ی »مجموع رنگی« که به مسأله ی طراحی V LSI معروف است، نشان خواهیم داد. همچنین در ادامه مروری بر تعاریف اساسی و قضایای کلی مورد استفاده در فصلهای آینده خواهیم داشت. مفاهیم رنگ آمیزی مینیمال، مجموع رنگی و قدرت رأسی گراف را در فصل سوم بیان، و به بررسی کرانهایی برای این مفاهیم خواهیم پرداخت. و در نهایت با استفاده از مفهوم هم ریختی گرافها، به ذکر کران هایی برای مجموع رنگی میپردازیم و فصل را با بیان دو الگوریتم، جهت محاسبه ی تقریبی از مقادیر مجموع رنگی و قدرت رأسی، به پایان خواهیم رساند.
کلید واژه ها (نمایه ها):
#مجموع رنگی #رنگ آمیزی مینیمال #قدرت رأسی
محل نگهداری: کتابخانه مرکزی دانشگاه صنعتی شاهرود
یادداشت: حقوق مادی و معنوی متعلق به دانشگاه صنعتی شاهرود می باشد.
تعداد بازدید کننده:
پایان نامه های مرتبط (بر اساس کلیدواژه ها)