Прикладная алгебра и графы

Рассматриваются цепи и циклы с четным количеством вершин, где одна половина вершин одного типа, а остальные – другого. Для таких цепей и циклов описываются схемы построения минимального вершинного и реберного 1-расширения.

В докладе представляются результаты вычислительного эксперимента, в котором были построены все минимальные вершинные и реберные 1-расширения циклов с числом вершин до 17.

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

        Общая постановка задачи формулируется следующим образом.  Пусть К – некоторый класс графов, а G – граф, не принадлежащий К. Требуется произвести те или иные изменения в структуре графа G, чтобы полученный граф G/ оказался К-графом (см. [4]). Очевидное требование, чтобы все вышеперечисленные изменения были оптимальными в том или ином смысле.

Граф G* = (V*, a*) называется минимальным вершинным k‑расширением  n‑вершинного графа G = (V, a), если выполняются следующие условия:

Подсчитывается количество бассейнов в конечных динамических системах двоичных векторов, ассоциированных с такими графами, как цепи и циклы.