How to determine if a graph is two-connected?

2 次查看(过去 30 天)
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
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 个评论
Image Analyst
Image Analyst 2021-1-11
Visualization (for other people):
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);
subplot(2, 3, 1);
p = plot(G);
bins = biconncomp(G);
for binNr = 1:max(bins)
st = G.Edges.EndNodes;
Gbin = subgraph(G, unique(st(bins == binNr, :)));
subplot(2, 3, binNr + 1);
plot(Gbin)
caption = sprintf('Bin #%d', binNr);
title(caption, 'FontSize', 15);
end
g = gcf;
g.WindowState = 'maximized';
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.

请先登录,再进行评论。

类别

Help CenterFile Exchange 中查找有关 Graph and Network Algorithms 的更多信息

产品


版本

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by