احاطه گر k-مجاورت در گراف ها
- سال انتشار: 1400
- محل انتشار: فصلنامه پدافند الکترونیکی و سایبری، دوره: 9، شماره: 3
- کد COI اختصاصی: JR_PADSA-9-3_010
- زبان مقاله: فارسی
- تعداد مشاهده: 279
نویسندگان
گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران
چکیده
فرض کنید G یک گراف ساده و بدون دور با مجموعه رئوس V باشد. یک مجموعه S که زیرمجموعه V است را احاطه گر گویند هرگاه هر راسی که خارج از S است با حداقل یک راس در S همجوار باشد. فرض کنید k≥۱ عددی صحیح باشد. مجموعه احاطه گر S را یک مجموعه احاطه گر k-مجاورت می نامیم هرگاه زیرگراف القائی G[S] شامل راسی از درجه حداکثر k-۱ باشد. کمترین تعداد عناصر یک مجموعه احاطه گر k-مجاورت برای گراف G عدد احاطه k-مجاورت آن گراف نامیده می شود و با نماد γ_k^a (G) نمایش داده می شود. در این مقاله، مطالعه احاطه گر k-مجاورت آغاز می شود. سپس مقادیر دقیق و کران هایی برای عدد احاطه k-مجاورت یک گراف داده شده ارائه می شود. همچنین، نشان داده می شود که یک الگوریتم با زمان چندجمله ای برای محاسبه عدد احاطه k-مجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت می شود که مسئله تصمیم گیری مرتبط با احاطه گر k-مجاورت برای گراف های دوبخشی NP-کامل است.کلیدواژه ها
مجموعه احاطه گر, گراف, عدد احاطهاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.