نسخه‌ي همبند بازي رنگ‌آميزي گراف‌ها

اصفهان : دانشگاه صنعتي اصفهان

رياضيات و كاربردها

كارشناسي ارشد

بازي روي گراف ها همواره از موضوعات جالب و مورد توجه بوده است. از جمله اين بازي ها، بازي رنگ آميزي رأسي، بازي احاطه گري، بازي علامت گذاري و ... هستند. در اين پايان نامه بازي رنگ آميزي رأسي و بازي رنگ آميزي رأسي همبند مورد مطالعه قرار گرفته است. بازي رنگ آميزي رأسي همبند يك بازي دو نفره است كه بين دو بازيكن مانند آليس و باب انجام مي شود. آليس و رنگي كه به آنها داده شده است، به نوبت رأس هاي گراف را رنگ آميزي مي كنند به طوري -k باب با توجه به مجموعه ي كه رأس هاي مجاور هم رنگ نباشند. در اين بازي هدف بازيكن شروع كننده تكميل رنگ آميزي كل گراف است ولي هدف بازيكن ديگر اين است كه از دستيابي به رنگ آميزي كل گراف جلوگيري كند.

233223

گراف و تركيبيات

رياضي

دانشگاه صنعتي اصفهان