June 12, 2017
Изоморфизм графов $G_{1}$ и $G_{2}$ — это биекция (взаимно-однозначное соответствие) $\phi$ из $V(G_{1})$ в $V(G_{2})$ такая, что ребро $(uv)$ в графе $G_{1}$ существует тогда и только тогда, когда в графе $G_{2}$ существует ребро $(\phi (u) \phi (v))$. Иными словами, изоморфизм — это способ перенумеровать вершины графа $G_{1}$ так, чтобы получился в точности граф $G_{2}$. Соответственно, два графа называются изоморфными, если существует изоморфизм.
Отношение “быть изоморфными” является отношением эквивалентности, и все графы разбиваются на классы изоморфных.
Фактически, изоморфные графы одинаковы, если не обращать внимания на нумерацию вершин. Поэтому все свойства графов, которые не зависят от нумерации, должны сохраняться при изоморфизме. То же можно сказать и про свойства вершин, если они не зависят от нумерации.
Задача изоморфизма графов состоит в том, чтобы по двум графам определить, изоморфны ли они.
На данный момент неизвестно, разрешима ли в общем случае задача изоморфизма графов за полиномиальное время. Относительно недавно был создан алгоритм, работающий за квазиполиномиальное время. В то же время не доказано, что задача является NP-полной.
Мы рассмотрим очень частный случай этой задачи, когда оба графа являются деревьями. Понятно, что если у них разный размер, то они неизоморфны. Далее будем общий размер этих графов обозначать за $n$. В этом случае задача разрешима за время $O(n \log n)$.
Ещё немного упростим себе задачу. Выделим в обоих деревьях корни $r_{1}$ и $r_{2}$ и потребуем, чтобы изоморфизм переводил один корень в другой, то есть $\phi (r_{1}) = r_{2}$.
Понятно, что изоморфизм переводит путь в графе $G_{1}$ в соответствующий путь в графе $G_{2}$, а значит сохраняет расстояние между вершинами. Следовательно, в случае корневых деревьев изоморфизм сохраняет высоту вершины (как расстояние от корня). А это значит, что если $u$ была родителем $v$ в $G_{1}$, то $\phi (u)$ будем родителем $\phi (v)$ в $G_{2}$, так как ребро между ними сохраняется, а $h( \phi (v) ) = h(v) = h(u) + 1 = h( \phi (u) ) + 1$.
Что нужно, чтобы деревья с корнями $r_{1}$ и $r_{2}$ были изоморфны? У $r_{1}$ и $r_{2}$ должно быть одинаковое число детей, и их можно сопоставить друг другу так, чтобы соответствующие поддеревья были изоморфны.
Аналогично обычному изоморфизму, изоморфизм корневых деревьев является отношением эквивалентности. Сопоставим каждому поддереву с корнем $v$ уникальный номер его класса эквивалентности $c_{v}$ (мы пока не умеем их вычислять).
Рассмотрим вершину $v$. Пусть для всех её сыновей $u$ мы вычислили $c_{u}$. Тогда с точки зрения изоморфизма поддерево $v$ полностью определяется мультимножеством $c_{u}$. Действительно, если у двух вершин эти множества разные, то либо они разного размера, либо не существует сопоставления детей такого, что соответствующие поддеревья детей изоморфны. То есть в любом случае поддеревья не изоморфны. Если же мультимножества совпадают, то и размеры равны, и отображение на детях есть. А мультимножество, в свою очередь, однозначно определяется отсортированным вектором значений.
В итоге получаем следующий алгоритм вычисления $c_{v}$:
map или unordered map.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N = 100100;
vector<int> g[N];
map<vector<int>, int> toId;
int getId(vector<int> p)
{
if (toId.count(p)) return toId[p];
int m = toId.size();
toId[p] = m;
return m++;
}
int dfs(int v, int par)
{
vector<int> a;
for (int u : g[v]) {
if (u == par) continue;
a.push_back(dfs(u, v));
}
sort(a.begin(), a.end());
return getId(a);
}
int main()
{
int root = read(); //read first tree
int c1 = dfs(root, -1);
root = read(); //read second tree
int c2 = dfs(root, -1);
if (c1 == c2)
printf("Isomorphic\n");
else
printf("Not isomorphic\n");
return 0;
}
Суммарный размер всех векторов есть $O(n)$, поэтому сложность всего алгоритма составит $O(n \log n)$.
Можно просто перебрать, куда перейдет фиксированная вершина $G_{1}$, и получить алгоритм за $O(n^{2} \log n)$. Но мы пойдём дальше и ограничимся двумя проверками. Для этого нам нужно вспомнить, что такое центроид дерева.
Свойство “быть центроидом” не зависит от нумерации вершин, поэтому центроид одного дерева при изоморфизме должен переходить в центроид другого. Мы знаем, что центроидов у дерева не больше 2, поэтому можно перебрать, в какой из центроидов второго дерева перейдёт какой-то из центроидов первого.
Сложность алгоритма составит $O(n \log n)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 100100;
vector<int> g[2][N];
map<vector<int>, int> toId;
int getId(vector<int> p)
{
if (toId.count(p)) return toId[p];
int m = toId.size();
toId[p] = m;
return m++;
}
int dfs(int k, int v, int par)
{
vector<int> a;
for (int u : g[k][v]) {
if (u == par) continue;
a.push_back(dfs(k, u, v));
}
sort(a.begin(), a.end());
return getId(a);
}
vector<int> getCentroids(int k, int v); //returns all centroids of k-th tree
int main()
{
read(); //read trees
vector<int> centr1 = getCentroids(0, 0), centr2 = getCentroids(1, 0);
if ((int)centr1.size() != (int)centr2.size()) {
printf("Not isomorphic\n");
return 0;
}
for (int v : centr2) {
if (dfs(0, centr1[0], -1) == dfs(1, v, -1)) {
printf("Isomorphic\n");
return 0;
}
}
printf("Not isomorphic\n");
return 0;
}
На самом деле мы научились за $O(n \log n)$ для дерева получать информацию достаточную для того, чтобы проверять его изоморфизм с любым другим деревом за $O(1)$ — это классы эквивалентности корневых деревьев с корнями во всех центроидах.
Рассмотрим следующую задачу: Дано $k$ деревьев суммарного размера $N$, нужно отвечать на запросы, являются ли деревья с номерами $a$ и $b$ изоморфными.
Эту задачу мы научились решать за $O(1)$ на запрос в онлайне с $O(N \log N)$ предподсчёта.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int K = 100100;
vector<vector<int>> g[K];
vector<int> c[K];
int k;
map<vector<int>, int> toId;
int getId(vector<int> p)
{
if (toId.count(p)) return toId[p];
int m = toId.size();
toId[p] = m;
return m++;
}
int dfs(int id, int v, int par)
{
vector<int> a;
for (int u : g[k][v]) {
if (u == par) continue;
a.push_back(dfs(k, u, v));
}
sort(a.begin(), a.end());
return getId(a);
}
vector<int> getCentroids(int id, int v); //returns all centroids of id-th tree
int main()
{
read(); //read trees
for (int i = 0; i < k; i++) {
vector<int> centr = getCentroids(i, 0);
for (int v : centr)
c[i].push_back(dfs(i, v, -1));
sort(c[i].begin(), c[i].end());
}
int q;
scanf("%d", &q);
while(q--) {
int a, b;
scanf("%d%d", &a, &b);
if (c[a] == c[b])
printf("Isomorphic\n");
else
printf("Not isomorphic\n");
}
return 0;
}