دوستعلی مژده

تعریف کارکردهای احاطهکننده رومی با الهام گرفتن از مقاله ای در ساینتیفیک آمریکن توسط استوارت با عنوان "دفاع از امپراتوری روم" ] 13 [ و حتی پیش از آن توسط ریول ] 7 ] ارائه شد. هر رأس در گراف ما مکانی را در امپراتوری روم نشان می دهد. اگر هیچ ارتش در آنجا مستقر نباشد یک مکان )راس v( ناامن در نظر گرفته می شود )یعنی 𝑓(𝑣) = 0 ( و در غیر این صورت ایمن است )یعنی اگر 𝑓(𝑣) ∈ {1,2} (. یک مکان ناامن )راس v( را می توان با ارسال یک ارتش به v از یک مکان همسایه )یک راس u مجاور( ایمن کرد. اما کنستانتین کبیر )امپراتور روم( در قرن چهارم پس از میلاد، فرمانی برای دفاع از مناطق صادر کرد، که در آن ارتش نمیتوان از یک مکان امن که فقط یک ارتش در آنجا مستقر است به مکان ناامن فرستاد، زیرا در غیر این صورت ترک آن مکان موجب ناامن شدن مکان میشود. بنابراین، دو ارتش باید در یک مکان (𝑓(𝑣) = 2) قبل از اینکه یکی از ارتشها به مکان همسایه فرستاده شود، مستقر شوند. به این ترتیب امپراتور کنستانتین کبیر می تواند از امپراتوری روم دفاع کند. از آنجایی که نگهداری یک ارتش در یک مکان هزینه زیادی دارد، امپراتور دوست دارد تا حد امکان ارتش کمتری را مستقر کند، در حالی که همچنان از امپراتوری روم دفاع می کند. تابع احاطهکننده رومی وزن γ𝑅(𝐺) با چنین تخصیص بهینه ارتشها به مکان ها مطابقت دارد. رومی احاطهکننده رومی} 2 {)که در ] 23 [ نامیده می شود