Дискретная математика. Рубрика в журнале - Вестник Бурятского государственного университета. Математика, информатика
Алгоритм преобразования ориентированного графа в ациклический
Статья научная
Совместно с экспертами в разных областях знаний авторами статьи за последние пять лет был решен ряд актуальных задач. Используя элементы теории графов, были построены оригинальные экономичные алгоритмы для исследования рассматриваемых моделей и протестированы на реальных данных. Работа является продолжением исследований в этом направлении и задача, решаемая в ней, поставлена специалистами в области биоинженерии. На первом этапе в орграфе была проведена факторизация по отношению циклической эквивалентности, и в каждом кластере были выделены входные и выходные вершины (ребер извне и вовне), применяя ранее построенный авторами работы экономичный алгоритм. На втором шаге, используя алгоритм фронта волны, каждый кластер был заменен на его ациклический подграф, соединяющий входные вершины с выходными путями минимальной длины. Далее исходный орграф был заменен на ациклический орграф, в котором нет обратных связей, связывающий входные и выходные вершины кластеров.
Бесплатно
Об одном семействе е-замкнутых классов гиперфункций ранга
Статья научная
Гиперфункции представляют собой функции, заданные на конечном множестве и принимающие в качестве своих значений все непустые подмножества рассматриваемого множества. В теории дискретных функций интересным и важным является вопрос классификации относительно различных операторов замыкания. Одним из таких операторов является оператор замыкания с разветвлением по предикату равенства (Е-оператор). Такой оператор относится к категории сильных операторов замыкания. В статье рассматривается семейство классов гиперфункций ранга к, сохраняющих перестановки на k-элементном множестве. Показано, что такие классы являются Е-замкнутыми. В случае, если перестановка распадается на циклы одинаковой простой длины, то такие классы являются Е-предполными. Кроме этого показано, что множество, содержащее все функции-константы и функцию, возвращающую на всех наборах некоторое зафиксированное непустое подмножество исходного множества, является Е-полным.
Бесплатно
