Умберто Эко

Проверка графов на изоморфизм, программа на С/С++

Имея два графа, мы можем задаться вопросом: "Являются ли они изоморфными?" Для ответа на этот вопрос предназначены различные алгоритмы, в том числе и алгоритм нахождения изоморфизма графов.

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

Один из основных алгоритмов проверки графов на изоморфизм находится в рамках NP-полных задач, поэтому не существует алгоритма, который будет работать за полиномиальное время для всех графов. Но существует несколько алгоритмов, которые обычно демонстрируют хорошую производительность на большинстве графов.

Один из таких алгоритмов - это алгоритм Ульмана. Он предназначен для нахождения биективного отображения между вершинами двух графов, сохраняющих ребра. Алгоритм Ульмана работает следующим образом:

  1. Один граф выбирается в качестве исходного, а другой - в качестве целевого. Для каждой вершины исходного графа вычисляется множество вершин целевого графа, с которыми эта вершина может быть изоморфна. Кроме того, для каждой пары вершин из исходного графа и целевого графа вычисляется множество ребер, которые могут соединять эти вершины. Эти операции выполняются за O(n^2) операций.
  2. Затем на основе полученной информации создается общий граф для двух графов. Этот общий граф является двудольным графом, где первая доля содержит вершины исходного графа, а вторая доля - вершины целевого графа. Между вершинами первой и второй долей проводятся ребра в соответствии с множеством ребер, вычисленных в предыдущем шаге. Этот шаг выполняется за O(n^3) операций.
  3. В полученном двудольном графе производится поиск максимального паросочетания. Если максимальное паросочетание содержит n ребер, то графы изоморфны. Иначе, если максимальное паросочетание содержит меньше n ребер, то графы неизоморфны.

Пример программы, реализующей алгоритм Ульмана на языке С/С++, приведен ниже:

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 100;
int n, m; // количество вершин и ребер в графах
int gr1[MAXN][MAXN], gr2[MAXN][MAXN]; // матрицы смежности графов
int p[MAXN], used1[MAXN], used2[MAXN]; // массивы для поиска паросочетания

bool find_path(int v, int t) {
    used1[v] = 1;
    for (int i = 0; i < n; ++i)
        if (gr1[v][i] && !used2[i]) {
            used2[i] = 1;
            if (p[i] == -1 || find_path(p[i], t)) {
                p[i] = v;
                return true;
            }
        }
    return false;
}

bool isomorph() {
    // Step 1
    vector<vector<int>> can_use(n, vector<int>());
    vector<vector<int>> forbidden(n, vector<int>());
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (gr1[i][j])
                for (int k = 0; k < n; ++k)
                    if (gr2[j][k])
                        can_use[i].push_back(k);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (gr1[i][j])
                for (int k = 0; k < n; ++k)
                    if (!gr2[j][k])
                        forbidden[i].push_back(k);

    // Step 2
    vector<vector<int>> bipartite(n, vector<int>());
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < can_use[i].size(); ++j) {
            int v = i, u = can_use[i][j];
            bipartite[v].push_back(u);
            bipartite[u].push_back(v);
        }

    // Step 3
    memset(p, -1, sizeof(p));
    for (int i = 0; i < n; ++i) {
        memset(used1, 0, sizeof(used1));
        memset(used2, 0, sizeof(used2));
        find_path(i, n - 1);
    }
    for (int i = 0; i < n; ++i)
        if (p[i] == -1)
            return false;
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int p, q;
        cin >> p >> q;
        gr1[p][q] = gr1[q][p] = 1;
    }
    for (int i = 0; i < m; ++i) {
        int p, q;
        cin >> p >> q;
        gr2[p][q] = gr2[q][p] = 1;
    }
    if (n == 1) cout << "YES" << endl;
    else if (isomorph()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Эта программа считывает два графа в виде матрицы смежности и проверяет, являются ли они изоморфными с помощью алгоритма Ульмана. Если графы изоморфны, программа выводит "YES", в противном случае - "NO".

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