Інтернет, Интернет, Internet ; задача Штейнера ; критерій привабливості, критерий предпочтительности ; складні мережі, сложные сети ; субоптимальні рішення, субоптимальные решения ; топологія, топология, topology

Задачу пошуку оптимальної топології зв'язків в мережі Інтернет для цільового вузла, яка відпочатку є комбінаторною NP-складною задачею, подібною до задачі Штейнера, було трансформовано до поліноміальної задачі, сутність якої полягає в відмові від перебору комбінацій з n вузлів по v зв'язків. Замість перебору запропоновано метод отримання субоптимального рішення шляхом початкового ранжування вузлів за фактором віддаленості вузла, що є відношенням середнього шляху вузла середнього шляху по мережі. Для цього в множині вузлів введено відношення порядку за фактором віддаленості. Впорядкування має поліноміальну складність. Експериментально показано, що приєднання до заданої кількості вузлів саме з найвищим рангом фактором віддаленості дає в результаті найменший фактор віддаленості нового вузла: в разі приєднання до 2 вузлів він був на 24,4% менший, а в разі приєднання до З вузлів - на 26,7% менший, ніж середнє значення фактора віддаленості по інших вузлах мережі.

• УДК // Інтернет. Портали
• УДК // Топологічні та метричні задачі теорії графів. Поєднуваність. Планарність