Select edges that connect subgraphs together

Question

NA 2020-4-8

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/516383-select-edges-that-connect-subgraphs-together

编辑： NA 2020-4-9

I have a graph like this

M = [1 2; 2 3; 1 3; 4 5; 5 6; 6 7; 4 7;2 4; 5 7; 5 8;11 8; 8 9; 9 10; 10 11;4 12; 12,13; 13 14;12 14];
g = graph(M(:, 1), M(:, 2));
h = plot(g);

I want to find edges that connect subgraphs together

result should be

A = [2,4; 5 8; 4 12]

2 个评论
显示无隐藏无

Sean de Wolski 2020-4-8

So trying to verbalize the rule: return any edge whose two end nodes are connected to at least two other nodes?

(Also, your data do not include nodes 12/13/14 so [4 12] wouldn't be returned)

NA 2020-4-9

Thanks. I corrected edge set.

请先登录，再进行评论。

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

Answer 1

Sean de Wolski 2020-4-8

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/516383-select-edges-that-connect-subgraphs-together#answer_424830

在 MATLAB Online 中打开

This works for your sample data set (which does not include nodes 12:14 as shown in the plot. Please test test this, I'm not a graph theory expert so there may be cases where this does not work.

M = [1 2; 2 3; 1 3; 4 5; 5 6; 6 7; 4 7;2 4; 5 7; 5 8;11 8; 8 9; 9 10; 10 11];
g = graph(M(:, 1), M(:, 2));
h = plot(g);
bcg = biconncomp(g).'; % biconnected components
[count, group] = groupcounts(bcg); % How many of each?
edgeidx = ismember(bcg, group(count==1)); % Edges with one count
g.Edges(edgeidx, 1) % Extract
ans =
  2×1 table
    EndNodes
    ________
     2    4 
     5    8 