MATLAB Answers

How to determine if a graph is two-connected?

조회 수: 1(최근 30일)
Ephraim Bryski
Ephraim Bryski 2021년 1월 11일
댓글: Christine Tobler 2021년 1월 12일
Hi. I have a graph in MATLAB and I would like to determine if it is two-connected. I would also like to have the graphs which it can be separated into as outputs. Is there a way of doing this efficiently in MATLAB, either using built-in functionality, or writing code? Thanks!


Christine Tobler
Christine Tobler 2021년 1월 11일
The biconncomp function will split the edges of a graph into its biconnected components. If the output of biconncomp is a vector of all ones, that graph is two-connected.
Otherwise, here's some code that will extract each biconnected component as an individual graph as follows:
s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G);
bins = biconncomp(G);
for binNr = 1:max(bins)
st = G.Edges.EndNodes;
Gbin = subgraph(G, unique(st(bins == binNr, :)));
Keep in mind: For a graph without node names in MATLAB, nodes are numbered through 1, 2, ..., [number of nodes]. This means that the subgraph command can assign a new node index (e.g., if G has three nodes, subgraph(G, [1 3]) will return a graph where the previous node 3 is now node 2). You can avoid this by using node names.
  댓글 수: 3
Christine Tobler
Christine Tobler 2021년 1월 12일
If a graph is 3- or 4- connected, this means it is also two-connected (biconnected). The biconncomp function only answer the question of whether a graph is two-connected or how it can be split into biconnected components.
MATLAB doesn't have functionality for computing k-connectivity except for k=1 (conncomp) and k=2 (biconncomp). For the 3-connected case I think you're looking for, a quick wikipedia search suggests you might need to look at the concept of SPQR trees. An algorithm is described on that page, with reference to papers for details.

댓글을 달려면 로그인하십시오.




Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by