دوستعلی مژده

فرض کنیم G یک گراف متناهی همبند با مجموعه راسهای V(G) V=ومجموعه یالهای=E(G) E باشدکه در آن VوE مجموعه های متناهی هستند. هر گراف همبند که فاقد دور باشد یک درخت است.Pn یک مسیر nراسی است. یک برگ از G یک راس از درجه 1 است و یک راس پشتیبانی از G یک راس در مجاورت یک برگ است. یک راس پشتیبانی که در مجاورت حداقل دو برگ باشد، یک راس پشتیبانی قوی می نامیم. یک همسایه باز از راس v را با {u ∈ V | uv ∈ E} N(v)= نشان می دهیم و یک همسایه بسته با N[v] = N(v) ∪ {v} نمایش داده می شود. اگر v ∈ S و w ∈ V – S, N(w) ∩ S = {v } آنگاه راس w یک همسایه خصوصی خارجی از v نسبت به S است . مجموعه S ⊆ V یک مجموعه احاطه کننده (DS) از G است، اگر هر راس در V-S مجاور به یک راس درS باشد و S یک مجموعه احاطه کننده کلی (TDS)از گراف G است، اگر هر راس در v در مجاورت یک راس از S باشد . مینیمم اندازه یک مجموعه(TDS) عدد احاطه کننده کلی نامیده می شودوبا (G) γ_tنمایش داده می شود. برای هر درخت از مرتبه حد اقل 2 عدد احاطه کننده کلی و جایابی و متریک بررسی می شود.