Эта публикация цитируется в 19 статьях

Большие системы

Достаточное условие существования в графах дробных $(g,f)$-факторов с ограничениями

С. Чжоу^a, Ч. Сунь^b, Ц. Пань<sup>a

a</sup> Школа естественных наук, Научно-технологический университет Цзянсу, Чжэньцзян, провинция Цзянсу, КНР
^b Школа математических наук, Нанкинский нормальный университет, Нанкин, КНР

Аннотация: В NFV-сети доступность планирования ресурсов может быть выражена наличием дробного фактора в соответствующем графе. Исследования о существовании специальных дробных факторов в структуре сети могут помочь построить NFV-сеть с эффективным распределением ресурсов. Рассмотрим некоторую функцию $h\colon E(G)\to[0,1]$. Обозначим $d_G^{h}(x)=\sum\limits_{e\ni x}h(e)$. Назовем граф $F_h$ с множеством вершин $V(G)$ и множеством ребер $E_h$ дробным $(g,f)$-фактором графа $G$ с индикаторной функцией $h$, если неравенство $g(x)\le d_G^{h}(x)\le f(x)$ выполняется для любого $x\in V(G)$, где $E_h=\{e: e\in E(G), h(e)>0\}$. Скажем, что $G$ обладает свойством $E(m,n)$ относительно дробного $(g,f)$-фактора, если для любых двух множеств независимых ребер $M$ и $N$, таких что $|M|=m$, $|N|=n$ и $M\cap N=\emptyset$, граф $G$ допускает дробный $(g,f)$-фактор $F_h$, такой что $h(e)=1$ для всякого $e\in M$ и $h(e)=0$ для всякого $e\in N$. Понятие $E(m,n)$-свойства относительно дробного $(g,f)$-фактора отвечает структуре NFV-сети, где определенные каналы заняты или повреждены в некоторые моменты времени. Рассматривается проблема планирования ресурсов в NFV-сетях, используя теорию графов. Приводится условие, основанное на объединении окрестностей вершин, при котором граф обладает $E(1,n)$-свойством относительно дробного $(g,f)$-фактора. Кроме того, показывается, что нижняя оценка в данном условии является наилучшей возможной в некотором смысле.

Ключевые слова: NFV-сеть, граф, объединение окрестностей, дробный $(g,f)$-фактор, дробные $(g,f)$-факторы с ограничениями.

УДК: 621.391 : 519.17

Поступила в редакцию: 21.02.2020
После переработки: 30.05.2020
Принята к печати: 02.06.2020

DOI: 10.31857/S055529232004004X

 Англоязычная версия: Problems of Information Transmission, 2020, 56:4, 332–344

Реферативные базы данных:

•