چکیده: فرض کنید (G = (V, E گرافی همبند و بدون جهت باشد و r ≥ ١ عددی صحیح باشد. زیرمجموع ه
ای از رئوس مانند C ⊆ V را در نظر بگیرید. به ازای هر رأس v ∈ V مجموعه (B_r(v را به صورت { B_r(v) = {u ∈ V : d(v, u) ≤ r تعریف می
کنیم. اگر به ازای هر رأس ،v ∈ V همه مجموعه
های ( C ∩ Br(v ناتهی و دو به دو از هم متمایز باشند، آن
گاه C را کد r-شناسایی می
نامیم. اگر به ازای هر رأس ، v ∈ V \C همه مجموعه
های ( C ∩ Br(v ناتهی و دو به دو از هم متمایز باشند، آن
گاه C را کد r-احاطه
گر مکانی می
نامیم. کمترین اندازه یا تراکم این کدها در این پایان
نامه بررسی می
شود. ابتدا ، تعاریف و قضایایی از نظریه گراف را بیان می
کنیم. سپس ویژگی
هایی از انتقال در Z^2 را توصیف می
کنیم که در بررسی کدهای متناوب مفیدند و با استفاده از آن به مطالعه کدهای r-شناسایی با مقادیر r کوچک در چهار مشبکه
ی شش
گوشه، مثلث، مربع و شاهوار می
پردازیم. در ادامه ثابت می
کنیم که کمترین تراکم در مشبکه شاهوار برای r > ١برابر 1/4r است. در نهایت مقدار دقیق بهترین تراکم ممکن در زنجیرهای متناهی و نامتناهی و همچنین در دورها را ارائه می
نماییم.