کاربرد پایه گروبنر در تعیین عدد رنگی گراف

یک مسیله متداول در نظریهگراف این است که یک گراف G با n راس، k-رنگپذیرراسی هست یا نه. ریاضیدانان علاقمندند که بفهمند کمترین تعداد رنگ مورد نیاز برای رنگآمیزیگراف چند است. از روش پایه گروبنر برای تعیین k-رنگپذیر بودن یک گراف استفاده میکنیم. پایه گروبنر همچنین میتواند به ما کمک کند که ریوس را رنگ کنیم. پایه گروبنر برای یک ایدهال، مجموعه مولدی از ایدهال را به ما ارایه میکند. برای یافتن این مجموعه مولد یک راهحل الگوریتمی وجود دارد. یکی از کاربردهای پایه گروبنر در تعیین عدد رنگی گراف میباشد. در این مقاله به بررسی الگوریتم عدد رنگی برای حل مسیله k-رنگپذیری گراف میپردازیم که یک گراف n راسی را بهصورت یک چندجملهای n متغیره نمایش میدهیم و با استفاده از پایه گروبنر آنرا حل میکنیم. سپس الگوریتمهای ارایه شده را در نرمافزار ریاضی میپل پیادهسازی و اجرا خواهیم کرد.

کلیدواژه ها:

پایه گروبنر ، عدد رنگی گراف ، k -رنگپذیر راسی ، الگوریتم عدد رنگی گراف