Прикладная дискретная математика №1 2016

Производящая функция представлений графов в виде k-дольных графов // ПДМ. <...> Круговые инверсии перестановок и их использование в задачах сортировки // ПДМ. <...> Представление геометрических типов булевых функций от трёх переменных алгебраическими пороговыми функциями // ПДМ. <...> К вопросу о линейной декомпозиции двоичных функций // ПДМ. <...> Правила преобразования состояний системы в рамках ДП-модели управления доступом в компьютерных сетях, построенных на основе ОС семейства Linux // ПДМ. <...> ДИСКРЕТНЫЕ МОДЕЛИ РЕАЛЬНЫХ ПРОЦЕССОВ 104–118 Шумиляк Л. М. , Жихаревич В. В. , Остапов С. Э. <...> Если множество вершин графа G можно разбить на k подмножеств так, чтобы между входящими в одно подмножество вершинами не было ни одного ребра, то будем говорить, что граф G представим в виде k-дольного графа. <...> Получившийся k-дольный граф будем называть представлением исходного графа G в виде k-дольного графа. <...> Хроматический полином Пусть p(k;G)—функция от графа G, дающая для каждого числа k количество представлений графа G в виде k-дольного графа с маркированными, в том числе пустыми, долями. <...> Таким образом, функция p(x;G) представляет собой хроматический полином [7] p(x;G) =  i>0 n Mk(G) = l0 bixi, (9) где n—количество вершин графа G. <...> Так как k-дольный граф является представлением для всех изоморфных графу G графов, то функция φ(G) должна быть инвариантной относительно изоморфизма. <...> Moscow, Dialog-MIFI Publ., 2010. (in Russian) ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2016 Теоретические основы прикладной дискретной математики УДК 51.76, 577.21, 512.542.7 КРУГОВЫЕ ИНВЕРСИИ ПЕРЕСТАНОВОК И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ СОРТИРОВКИ А.Ю. <...> М.В. Ломоносова, г. Москва, Россия Предлагается алгоритм сортировки перестановки на основе её множеств круговых инверсий. <...> Ключевые слова: инверсии и круговые инверсии перестановок, сортировка линейных и круговых перестановок, диаметр группы подстановок. <...> Задачи сортировки перестановок Целое направление исследований в вычислительной молекулярной биологии связано с оценкой сложности <...>