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