|
چکیده
|
برای یک گراف G=(V(G),E(G))، مجموعه S یک مجموعه احاطه کننده است اگر هر راس در V(G)∖S مجاور یک راس در S باشد. عدد احاطه کننده γ(G) برابر است با حداقل کاردینالیته یک مجموعه احاطه کننده از گراف G. مدلی را برای موقعیت‌هایی ارائه می‌کند که در آن رئوس S از رئوس همسایه‌ای که در S نیستند محافظت می‌کنند. فرض کنیدG یک گراف و v∈V(G) باشد. همسایگی باز v مجموعه N(v)={u∈V(G)∣uv∈E(G)}است و همسایگی بسته آن مجموعه N[v]=N(v)∪{v} است. فرض کنیدf تابعی باشد که به هر رأس مجموعه ای از رنگ های انتخاب شده از مجموعه {1,…,k} را اختصاص می دهد. یعنیf:V(G)→P({1,…,k}). اگر برای هر راس v∈V(G)به طوری که f(v)=∅داریم: ⋃_(u∈N(v))▒ f(u)={1,…,k}
|