加载中…【数理化】图“同构”的判断
(2015-12-19 10:33:00)
标签：
数学科普 |
分类： 数理化和工程 |
有两个图，如何判断它们是同构的，可以用下面的方法验证；
生成一个矩阵，表示图的联通
n=1200;
A=zeros(n,n);
for i=1:n
A(i,i)=1.0;
end
for i=1:n
for
j=1:n
if( i>j)
r = rand;
%根据下面规则生成节点的联通，可以修改
if( r > 0.5)
A(i,j)=1.0;
end
end
end
end
%对称化
for i=1:n
for
j=1:n
if( i>j )
A(i,j) =A(j,i);
end
end
end
disp('生成一个矩阵，表示一个图');
A;
disp('求矩阵的特征值和特征向量')
[V1,D] = eig(A);
D1 = diag(D);
%交换矩阵的行列，
%表示另外一个图
%表示交换第1行、第1200行并交换第1列、第1200列
i=1;
j=1200;
P=A(i,1:n);
Q=A(j,1:n);
A(i,1:n) = Q;
A(j,1:n) = P;
P=A(1:n,i);
Q=A(1:n,j);
A(1:n,i) = Q;
A(1:n,j) = P;
A;
[V2,D] = eig(A);
D2 = diag(D);
%表示两个图的特征值的排列，matlab的算法已经从小到大排列了
[D1 D2];
%如何同构，特征值相等。
%检查对应的特征向量，由于MATLAB特征值的计算算法，特征向量可能多了一个负号
[V1(1:n,1) V2(1:n,1) V1(1:n,1)+V2(1:n,1)];
[V1(1:n,1) V2(1:n,1) V1(1:n,1)-V2(1:n,1)];
plot(V1(1:n,1)+V2(1:n,1))
plot(V1(1:n,1)-V2(1:n,1))
总结一下：有两个图，先写出联通矩阵，求特征值，如果特征值相等，则同构。
生成一个矩阵，表示图的联通
n=1200;
A=zeros(n,n);
for i=1:n
end
for i=1:n
end
%对称化
for i=1:n
end
disp('生成一个矩阵，表示一个图');
A;
disp('求矩阵的特征值和特征向量')
[V1,D] = eig(A);
D1 = diag(D);
%交换矩阵的行列，
%表示另外一个图
%表示交换第1行、第1200行并交换第1列、第1200列
i=1;
j=1200;
P=A(i,1:n);
Q=A(j,1:n);
A(i,1:n) = Q;
A(j,1:n) = P;
P=A(1:n,i);
Q=A(1:n,j);
A(1:n,i) = Q;
A(1:n,j) = P;
A;
[V2,D] = eig(A);
D2 = diag(D);
%表示两个图的特征值的排列，matlab的算法已经从小到大排列了
[D1 D2];
%如何同构，特征值相等。
%检查对应的特征向量，由于MATLAB特征值的计算算法，特征向量可能多了一个负号
[V1(1:n,1) V2(1:n,1) V1(1:n,1)+V2(1:n,1)];
[V1(1:n,1) V2(1:n,1) V1(1:n,1)-V2(1:n,1)];
plot(V1(1:n,1)+V2(1:n,1))
plot(V1(1:n,1)-V2(1:n,1))
总结一下：有两个图，先写出联通矩阵，求特征值，如果特征值相等，则同构。
喜欢
0
赠金笔
后一篇：【数理化】N皇后问题的矩阵特性