احاطه گر k-مجاورت در گرافها | ||
| پدافند الکترونیکی و سایبری | ||
| دوره 9، شماره 3 - شماره پیاپی 35، پاییز 1400، صفحه 125-131 اصل مقاله (610.79 K) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسنده | ||
| داود بخشش* | ||
| استدیار، گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران | ||
| چکیده | ||
| فرض کنید G یک گراف ساده و بدون دور با مجموعه رئوس V باشد. یک مجموعه S که زیرمجموعه V است را احاطهگر گویند هرگاه هر رأسی که خارج از S است با حداقل یک رأس در S همجوار باشد. فرض کنید k≥1 عددی صحیح باشد. مجموعه احاطهگر S را یک مجموعه احاطهگر k-مجاورت مینامیم هرگاه زیرگراف القائی G[S] شامل رأسی از درجه حداکثر k-1 باشد. کمترین تعداد عناصر یک مجموعه احاطهگر k-مجاورت برای گراف G عدد احاطه k-مجاورت آن گراف نامیده میشود و با نماد γ_k^a (G) نمایش داده میشود. در این مقاله، مطالعه احاطهگر k-مجاورت آغاز میشود. سپس مقادیر دقیق و کرانهایی برای عدد احاطه k-مجاورت یک گراف داده شده ارائه میشود. همچنین، نشان داده میشود که یک الگوریتم با زمان چندجملهای برای محاسبه عدد احاطه k-مجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت میشود که مسئله تصمیمگیری مرتبط با احاطهگر k-مجاورت برای گرافهای دوبخشی NP-کامل است. | ||
| کلیدواژهها | ||
| مجموعه احاطهگر؛ گراف؛ عدد احاطه | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 458 تعداد دریافت فایل اصل مقاله: 446 |
||