Skip to content

vekarpov/CDC

Repository files navigation


Программа включает:



1.  Файл Matrix.h, в котором находится описание класса Basis.
Класс Basis - это класс для задания некоторого подпространства циклов. Задаётся через его базис,
который хранится, как набор векторов в улучшенном ступенчатом виде.

У него есть следующие функции:
    Basis(v) - нахождение базиса в улучшенном ступенчатом виде для системы линейнонезависимых векторов O(n^3)

    Basis(v, q) - нахождение базиса в улучшенном ступенчатом виде для любой ситемы векторов O(n^3)
    Gauss() - служебная функция для привидения матрицы к улучшенному ступенчатому виду O(n^3)
    Equiv(n) - определяет, совпадает ли данный базис с каким-то улучшенным полным графом на n вершинах
    Subset(n) - определяет, является ли подмножеством какого-либо на n вершинах



Алгоритмы
    Equiv(n):

    Идея: достаточно перебирать лишь "пучковый базис", неважно в каком порядке O(C_m^n) ~ O(\frac{m!}{n! (m - n)!}) ~ O(m^n)
    Если учесть, что n^2 ~ m O(m^sqrt(m)) - для 20 вполне ok


About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published