Дан плоский ненаправленный граф с n точками, помеченными целым числом [1,2, .. n]
Задача состоит в том, чтобы найти все уникальные четырехугольники, под «уникальными», мы имеем в виду: если два четырехугольника имеют все четыре точки одинаковые, но различен только относительный порядок, то эти два считаются «одинаковыми» четырехугольник. Например, [1,2,3,4] и [1,3,2,4] - это один и тот же четырехугольник.
Ввод: график может быть сохранен в любом формате, который вы предпочитаете. Здесь мы используем смежную матрицу (для неориентированного графа каждое физическое ребро вводится один раз в следующем описании), первые два числа в 1-й строке - это номер вершины и номер ребра соответственно. Затем следующие строки вводят каждое ребро каждый раз.
Вывод: матрица M-4 или список массивов. M - это последний уникальный счетчик четырехугольников, который вы нашли.
На следующем неориентированном полном графике из пяти точек:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Существует только пять уникальных четырехугольников (игнорируйте относительный порядок последовательности вершин):
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
У меня сейчас нет идеального решения.
Следующее решение MATLAB может найти только каждый уникальный четырехугольник для Case-1, но не удалось в Case-2, то есть не может быть найдено четырехугольника.
%% Count Quadrangles
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For muilt-edge graph , Build the matrix for graph:
for i = 1:length(v)
G(v(i), t(i)) = G(v(i), t(i)) + 1;
G(t(i), v(i)) = G(v(i), t(i));
end
issymmetric(G)
max(max(G))
% For single edge graph, Build the matrix for graph:
% G(sub2ind(size(G),v, t))=1;
% G(sub2ind(size(G),t, v))=1; % fill the symmetric position
tic
quad_cnt = 0;
% G_ = graph(G);
quad_points = [];
%% O(N^3)
for i = 1:n
for j = i+1:n
if (j==i || G(i,j)==0)
continue;
end
for k = j+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j) == 0) )
continue;
end
for p = k+1:n
if ( p==i || p==j || p==k || G(p,i)==0 || G(p,k) == 0)
continue;
end
% otherwise, a quadrangle is ofund
quad_cnt = quad_cnt+1;
% save the vertices
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
toc
% 0.1571 sec
quad_cnt
% output each triangle:
quad_points
%% O(deg*(V^2))
Тестовые случаи
Пограничные входы с использованием индекса вершин (Примечание: начиная с «1», а не «0»):
Case-1:
Ввод:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Вывод:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Case-2:
Входной сигнал:
8 8
1 3
2 3
1 4
2 4
1 8
2 5
3 6
4 7
Выход:
1 2 3 4