logo
417ПИ-Кривошеев / krivosheev

Дискретная математика. Расчёт функции Эйлера для составных чисел.

  1. Преобразовать последовательность a,b,c,dв уникальный набор неповторяющихся цифр: например,,, наборы, не имеющие повторений, сохраняются, и рассчитать следующие функции Эйлера,,,,,

    1. Какие из модулей удовлетворяют СТАНДАРТНЫМ Требованиям для применения алгоритмов Диффи-Хелмана, Масси-Омуры, RSA.

Хроматические полиномы. Задача о раскрасках.

  1. (в пяти вершинном исполнении –очень Дорогая задача).

    1. (1+ задача) Построить хроматический полином по пустым графам и кликам для 4-хвершинного графа, пример

    2. Вариант 2 Построить хроматический полином по пустым графам и кликам для стандартизованного 5ти рёберного и 5-ти вершинного графа.

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

точнее

слева-направо (номера ) и сверху вниз – РАСТРОВАЯ развёртка).

Конкретнее, рассматриваем ровно 5 позиций: позиции 1 и 3 в первой строке, 1 и 3 во второй (каждый раз счёт идёт от диагонали) позицию 2 в третьей и ЗАМЕНЯЕМ в порядке ОЧЕРЁДНОСТИ избыточные ЭЛЕМЕНТЫ на НЕДОСТАЮЩИЕ. (Мы рассмотрели нечётные позиции при обходе над-диагонального треугольника

пока в графе есть 2 ребра.

МЫ ЗАМЕНИЛИ первые три НУЛЯ (нечётной под-Последовательности ) на ТРИ ЕДИНИЦЫ.

    1. Вариант 3 (эта часть решается по указанию преподавателя вместо части b) … для 5-ти вершинного графа, полученного из заполнения верхнетреугольной матрицы инцидентности симметричного графа двоичными записями чиселabcd(числа пишутся в каждое в свою строку так, чтобы последний разряд был в последнем столбце).(Недостаток – этой части неконтролируемый уровень сложности, что преодолено в частиb, если числапроведённыхинепроведённыхрёбер оба равны 5.(всего может быть 10 рёбер в полном графе)).