# How to determine if a graph is two-connected?

10 ビュー (過去 30 日間)
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!

サインインしてコメントする。

### 回答 (1 件)

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, :)));
figure;
plot(Gbin)
end
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 件のコメント表示非表示 2 件の古いコメント
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.

サインインしてコメントする。

R2020b

### Community Treasure Hunt

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

Start Hunting!

Translated by