Информатика

Расширением n-вершинного графа G называется граф H с n+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа H. Тривиальное расширение графа G – соединение графа G с одноэлементным графом (т.е. к графу G добавляется вершина, которая соединяется ребром с каждой вершиной графа G). Т-неприводимым расширением графа G называется расширение графа G, получаемое из тривиального расширения данного графа удалением максимально возможного набора добавленных при построении тривиального расширения ребер.

В работе рассматриваются возможности использования технологий параллельных вычислений Message Passing Interface и Open Computing Language при моделировании металлических фотонных кристаллов методом функций Грина и интегральных уравнений. Анализируется эффективность этих технологий в рамках данной задачи, приводятся выводы о целесообразности их применения. 

 Минимальные реберные расширения графов можно рассматривать как модель оптимальной реберной отказоустойчивой реализацией некоторой системы. Задача нахождения минимальных реберных расширений произвольного графа является NP-полной, поэтому представляет интерес нахождение классов графов, для которых возможно построить минимальное реберное расширение аналитически. Эта работа посвящена реберным 1-расширениям графов специального класса—класса пальм. В этой работе приводится вид реберного 1-расширения для некоторых пальм и доказывается его минимальность. 

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