Блог

В настоящее время я работаю над небольшим проектом для курса, связанного с теорией графов. Текущая задача, с которой я столкнулся, заключается в создании каждого неизоморфного графа с N узлами (где N <= 4).

Более конкретно, я не уверен, как достичь определенного «шага» моего алгоритма. Идея состоит в том, чтобы сгенерировать каждый возможный граф с N узлами или, другими словами, сгенерировать все возможные матрицы смежности порядка N, отправить каждую из них в функцию для проверки на изоморфизм и распечатать их, если они изоморфны.

Вся задача включает в себя несколько функций и шагов, хотя в этом вопросе я сосредоточусь на том, который вызывает у меня проблемы — генерирование всех возможных комбинаций матриц смежности.

То, что я смог сделать до сих пор, — это сгенерировать все матрицы с одним ребром или, другими словами, только с одним «1». Вот моя функция (на C ):

 void generateAdjacencyMatrices(int N) {

    for (int i = 0; i < N; i  ) {
        for (int j = 0; j < N; j  ) {
            if (i != j) {
                adjacencyMatrix[i][j] = 1;
                //logic for isomorphism
                //logic for printing the graph
            }
            adjacencyMatrix[i][j] = 0;
        }        
    }
}
 

Это генерирует матрицы, подобные этим (на примере N = 3):

 0 1 0      0 0 1     0 0 0     0 0 0
0 0 0      0 0 0     1 0 0     0 0 1
0 0 0      0 0 0     0 0 0     0 0 0
 

и так далее.

Что мне нужно сделать, это сгенерировать каждую отдельную матрицу с произвольным числом ребер (произвольное число «1» в матрице), что я не уверен, как сделать за обычное время. Любые советы будут высоко оценены.

Этот код сгенерирует все 2^(N*N) матрицы смежности для размера N :

 #include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N);
    for (unsigned int counter = 0; counter < max;   counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N amp;amp; c != 0; i  ) {
            for (int j = 0; j < N amp;amp; c != 0; j  ) {
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto amp;row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << 'n';
        }
        std::cout << 'n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}
 

Он перебирает числа от 0 до N-1 и использует двоичное представление каждого числа для заполнения значений матрицы.

С помощью простого изменения вы можете сохранить нулевую диагональ и генерировать 2^(N*N - N) матрицы смежности:

 #include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N - N);
    for (unsigned int counter = 0; counter < max;   counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N amp;amp; c != 0; i  ) {
            for (int j = 0; j < N amp;amp; c != 0; j  ) {
                if (i == j) continue;
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto amp;row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << 'n';
        }
        std::cout << 'n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}
 

Вы можете начать с counter = 1 того, чтобы пропустить нулевую матрицу:

 #include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N - N);
    for (unsigned int counter = 1; counter < max;   counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N amp;amp; c != 0; i  ) {
            for (int j = 0; j < N amp;amp; c != 0; j  ) {
                if (i == j) continue;
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto amp;row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << 'n';
        }
        std::cout << 'n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}