How can I verify an isomorphism relation between two graphs that join cube and octahedron vertices?

6 次查看（过去 30 天）

Catarina Pina 2024-6-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices

评论： Steven Lord 2024-6-4

I have two sets of nodes, corresponding to the vertices of the cube (S1 = {1,…,8}) and the octahedron (S2 = {1,…,6}), respectively. I construct each graph G joining vertices of S_1 to vertices of S_2. Having two graphs G_1 and G_2, how can I check if there is an isomorphism relation between these two graphs?

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Catarina Pina 2024-6-4

Example:

Graph G_1: [1 2 3 3 3 4 4 4 5 5 5 6 6 6 7 8],...

[1 1 1 4 5 1 2 5 6 2 3 6 4 3 6 6]);

Graph G_2: [1 2 3 3 3 4 4 4 5 5 5 6 6 6 7 8],...

[3 3 1 4 5 1 2 5 6 2 3 6 4 3 5 5]

Geometrically I see that G_1 and G_2 are isomorphic, but how can I verify using MATLAB? Thanks!

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Steven Lord 2024-6-4

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#answer_1467456

在 MATLAB Online 中打开

Build the two graph objects then call either isisomorphic or isomorphism on it.

G_1 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [1  1  1  4  5  1  2  5  6  2  3  6  4  3  6  6]);
G_2 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [3  3  1  4  5  1  2  5  6  2  3  6  4  3  5  5]);
isisomorphic(G_1, G_2)
ans = logical
   0
mapping = isomorphism(G_1, G_2) % Empty if there is no isomorphism
mapping =

     []

Let's look at your two graphs. If you have coordinates for the vertices you could pass them into the plot call by specifying the XData, YData, and (for a 3-D plot) ZData properties rather than letting MATLAB choose the layout itself.

subplot(1, 2, 1)

plot(G_1)

title("G_1")

subplot(1, 2, 2)

plot(G_2)

title("G_2")

Those don't look isomorphic to me. The most obvious difference is that G_1 has two nodes with a self loop while G_2 only has one. In addition the two leaves in G_1 are adjacent to one of the self-loop nodes while the two leaves in G_2 are not adjacent to the self-loop node. Are you sure you assembled the source and target vectors with which I created G_1 and G_2 correctly?