ارائه روشی برای کاهش میانگین شعاع رأس ها در ساختار گراف شبکه ها

یکی از موضوعات مهم پیرامون ساختار گرافها، میانگین شعاع رأس ها است، که در سرعت انجام عملیات روی آنها تأثیر دارد. اگر بتواندو رأسی را که نتیجه حاصل از اتصالشان بیشترین کاهش میانگین شعاع رأس های گراف است را پیدا کرد، آنگاه با اتصال این دو رأسمی توان بیشترین کاهش میانگین شعاع رأس های گراف را شاهد بود. ما قصد داریم با ارائه یک روش رأس هایی را برای اتصال انتخابمی کنیم که اتصال آنها منجر به بیشترین میزان کاهش میانگین شعاع رأس های گراف می شود. برای طراحی این روش از فاکتورهاییچون درجه رأس های، شعاع رأس های، موقعیت رأس های، فاصله رأس های از یکدیگر، تعداد شعاع های منتهی به هر رأس و ترکیب کردناین فاکتورها در فرمولهای مناسب استفاده کرده ایم. در این روش برای اعمال موقعیت رأس در انتخاب رأس های مناسب از تابع بازگشتیاستفاده شده است و همچنین برای تأثیر مناسب فاکتورهای فاصله رأس های و تعداد شعاع های منتهی به هر رأس، در فرمول از ضریب یکششم استفاده کردهایم. با اتصال رأس های انتخاب شده توسط این روش می توان بیشترین کاهش میانگین شعاع رأس های گراف را ایجادکرد. بدین وسیله عملیات کاوش در گرافها سریعتر انجام می شود.

Keywords:

درجه رأس , رتبه رأس های گراف , فاصله رأسها , موقعیت رأس , میانگین شعاع رأس های گراف