CIVILICA We Respect the Science
(ناشر تخصصی کنفرانسهای کشور / شماره مجوز انتشارات از وزارت فرهنگ و ارشاد اسلامی: ۸۹۷۱)

گواهی نمایه سازی مقاله نتایجی بر عدد گراند گراف ها

عنوان مقاله: نتایجی بر عدد گراند گراف ها
شناسه (COI) مقاله: REGCMAES02_002
منتشر شده در دومین همایش ملی ریاضیات و کاربردهای آن در علوم مهندسی در سال ۱۳۹۴
مشخصات نویسندگان مقاله:

فاطمه رضامحمدی - دانشگاه شاهرود، دانشکده ریاضی، گروه گراف و ترکیبیات

خلاصه مقاله:
در روش حریصانه، راسهای گراف n راسی با اندیسهای n راسی با اندیسهای n، .....، 1 اندیس گذاری می شوند سپس رنگ آمیزی به ترتیب اندیسها طوری انجام می شود که رنگ راس iام کوچکترین شماره رنگی است که در راسهای قبلی مجاور به کار نرفته باشد. عدد گراندی یک گرافG، بیشترین مقدار K است که برای آن یک اندیس گذاری از راس های G با n، ....، 1وجود دارد به طوری که تعداد رنگ های لازم برای رنگ آمیزی حریصانه G با این اندیس گذاری، k است. عدد گراندی گراف G را با (G) نشان می دهند. در حالت کلی بدست آوردن عدد گراندی یک مساله NP – کامل است. ثابت شده که عدد گراندی مکمل هر گراف دوبخشی، NP- کامل است اما با وجود داشتن یک خوشه توسعه یافته و یا مینیمم مجموعه احاطه گر یالی می توان عدد گراندی آن را بدست آورد.

کلمات کلیدی:
عدد گراندی، مجموعه احاطه گر یالی، مجموعه احاطه گر یالی

صفحه اختصاصی مقاله و دریافت فایل کامل: https://www.civilica.com/Paper-REGCMAES02-REGCMAES02_002.html