SCI Библиотека

В данной работе рассматривается труднорешаемая комбинаторная задача построения топологического рисунка графа. В соответствии с предложенным в данной статье подходом решение этой задачи разбивается на несколько этапов, вводятся основные определения и ограничения предлагаемых математических моделей. Основой построения моделей служат методы дискретной оптимизации и теория вращения вершин графа. Для построения математической модели решается задача выделения плоской части графа, которая рассматривается как комбинаторная задача нахождения подмножества изометрических циклов графа. Представленный метод выделения плоской части графа основан на выделении базиса изометрических циклов графа модифицированным алгоритмом Гаусса с последующим выделением плоской части методом градиентного спуска. Рассматриваются методы построения топологического рисунка графа с минимальным числом пересечений.

Модель сетевого графа является удобным инструментом для анализа сетей передачи информации, где возможность передачи в условиях атаки на объект можно описывать с помощью дробных критических графов, а уязвимость сети можно измерять с помощью варианта параметра изолированной жесткости. Рассматривается как устойчивость сети, так и реализуемость передачи данных при повреждении узлов, и определяется граница на вариант изолированной жесткости для дробных (a, b, n)-критических графов, где параметр n означает количество поврежденных узлов в определенный момент времени. С помощью контрпримера доказывается точность полученной границы на вариант изолированной жесткости. Основной теоретический вывод позволяет находить оптимальное соотношение между производительностью и стоимостью при проектировании топологии сети.

Методом производящих функций дан новый прямой вывод одного из естественно возникших в перечислительной комбинаторике тождеств - тождества В. С. Шевелёва, ранее доказанного с помощью исчисления конечных разностей. Ряд вспомогательных результатов доказан методами классического математического анализа.