احاطه گر k-مجاورت در گراف ها
Publish place: Electronic and cyber defense، Vol: 9، Issue: 3
Publish Year: 1400
Type: Journal paper
Language: Persian
View: 246
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
Export:
Document National Code:
JR_PADSA-9-3_010
Index date: 12 December 2021
احاطه گر k-مجاورت در گراف ها abstract
فرض کنید G یک گراف ساده و بدون دور با مجموعه رئوس V باشد. یک مجموعه S که زیرمجموعه V است را احاطه گر گویند هرگاه هر راسی که خارج از S است با حداقل یک راس در S همجوار باشد. فرض کنید k≥۱ عددی صحیح باشد. مجموعه احاطه گر S را یک مجموعه احاطه گر k-مجاورت می نامیم هرگاه زیرگراف القائی G[S] شامل راسی از درجه حداکثر k-۱ باشد. کمترین تعداد عناصر یک مجموعه احاطه گر k-مجاورت برای گراف G عدد احاطه k-مجاورت آن گراف نامیده می شود و با نماد γ_k^a (G) نمایش داده می شود. در این مقاله، مطالعه احاطه گر k-مجاورت آغاز می شود. سپس مقادیر دقیق و کران هایی برای عدد احاطه k-مجاورت یک گراف داده شده ارائه می شود. همچنین، نشان داده می شود که یک الگوریتم با زمان چندجمله ای برای محاسبه عدد احاطه k-مجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت می شود که مسئله تصمیم گیری مرتبط با احاطه گر k-مجاورت برای گراف های دوبخشی NP-کامل است.
احاطه گر k-مجاورت در گراف ها Keywords:
احاطه گر k-مجاورت در گراف ها authors
داود بخشش
گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :