23 次查看(过去 30 天)
显示 更早的评论
Catarina Pina 2024-6-4,13:48
评论: Steven Lord 2024-6-4,16:49
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更早的评论
显示 -1更早的评论隐藏 -1更早的评论
Catarina Pina 2024-6-4,14:05
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#comment_3179191
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,14:23
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
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?
4 个评论 显示 2更早的评论隐藏 2更早的评论
显示 2更早的评论隐藏 2更早的评论
Christine Tobler 2024-6-4,14:42
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#comment_3179226
I think I see what was meant here: The first input and second input to the G_1, G_2 constructors are meant to be addressing two separate sets of nodes (first input is the vertices of the cube, and second input the vertices of the octagon).
You need to add a shift so that the nodes of the octagon are indices 9, 10, ..., 14 instead of reusing the indices 1, 2, ... 6 that are already used for the cube. Then, the two graphs are isomorphic:
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]+8);
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]+8);
isisomorphic(G_1, G_2)
ans = logical
1
mapping = isomorphism(G_1, G_2)
mapping = 14x1
1 2 5 6 3 4 7 8 11 12
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
subplot(1, 2, 1)
plot(G_1)
title("G_1")
subplot(1, 2, 2)
plot(G_2)
title("G_2")
Catarina Pina 2024-6-4,14:50
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#comment_3179231
I have tried something similar with digraph, but without sucess. The problem is that there are two disctint sets of indices. In both graphs we have that vertex 1 of cube is connected only with vertex 1 (G_1) or vertex 3 (G_2) of the octaedron. But in graphs representations, we have vertex 1 joining with 1, 2, 3 and 4 (G_1; as vertex 1 of the cube is connected with vertex 1 of the octaedron and vertices 2, 3 and 4 of the cube are connected with vertex 1 of the octaedron) and 3 and 4 (G_2), so I think that thouse representations do not correspond to G_1 and G_2. And I'm not figuring out how to represent these situation.
Catarina Pina 2024-6-4,14:55
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#comment_3179256
Yes, is that! Thank you so much!
Steven Lord 2024-6-4,16:49
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2125356-how-can-i-verify-an-isomorphism-relation-between-two-graphs-that-join-cube-and-octahedron-vertices#comment_3179311
Good catch, Christine!
请先登录,再进行评论。
请先登录,再回答此问题。
发生错误
由于页面发生更改,无法完成操作。请重新加载页面以查看其更新后的状态。
选择网站
选择网站以获取翻译的可用内容,以及查看当地活动和优惠。根据您的位置,我们建议您选择:。
您也可以从以下列表中选择网站:
美洲
- América Latina (Español)
- Canada (English)
- United States (English)
欧洲
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom(English)
亚太
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 简体中文Chinese
- English
- 日本Japanese (日本語)
- 한국Korean (한국어)
联系您当地的办事处