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

В 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)$-фактора. Кроме того, показывается, что нижняя оценка в данном условии является наилучшей возможной в некотором смысле.