# Algorithm for edge connectivity of a digraph?

18 ビュー (過去 30 日間)
Arif Billah 2023 年 7 月 27 日
コメント済み: Christine Tobler 2023 年 11 月 16 日
Hi,
What is the best way to compute edge connectivity of a digraph? Is there an algorithm or built-in matlab function I can use?
I don't have much experience with graph theory, and am trying to calculate the edge connectivity of a few digraphs with 50 nodes. Thanks!

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

### 採用された回答

Christine Tobler 2023 年 7 月 27 日

There is no direct method in MATLAB for computing the edge connectivity. Based on the Wikipedia page, you should be able to compute it quite efficiently for small graphs by calling maxflow in a loop:
% Completely connected graph:
g = graph(ones(4));
edgeConnectivity(g)
ans = 3
% Line graph:
g = graph(1:4, 2:5);
edgeConnectivity(g)
ans = 1
% Circle graph:
g = graph(1:4, [2:4 1]);
edgeConnectivity(g)
ans = 2
% Completely connected graph with 50 nodes:
g = graph(ones(50));
tic
edgeConnectivity(g)
ans = 49
toc
Elapsed time is 0.014921 seconds.
function k = edgeConnectivity(g)
% Make sure the graph is unweighted:
if contains("Weight", g.Edges.Properties.VariableNames)
g.Edges.Weight = [];
end
% Compute the maximum flow from node 1 to every other node
mf = zeros(1, numnodes(g)-1);
for ii=2:numnodes(g)
mf(ii-1) = maxflow(g, 1, ii);
end
% The edge connectivity is the minimum of these maximum flows
k = min(mf);
end
"A simple algorithm would, for every pair (u,v), determine the maximum flow from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).
[...]
An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices. This [...] is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex.
"
Note this isn't the most efficient implementation in terms of code complexity, but the timing looks quite good for a graph with 50 nodes.
##### 3 件のコメント1 件の古いコメントを表示1 件の古いコメントを非表示
Alain 2023 年 11 月 16 日
As far as I understand the output of the proposed function is not the edge-connectivity of the graph. As quoted in the comment, to obtain the edge-connectivity one needs to consider all pairs (u,v). In the code, u is fixed to 1.
Christine Tobler 2023 年 11 月 16 日
This is because of the second part of the citation from wikipedia above: "An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices." I have arbitrarily fixed vertex u to 1 in the above code.

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

### その他の回答 (1 件)

Mrutyunjaya Hiremath 2023 年 7 月 27 日
• To compute the edge connectivity of a directed graph (digraph) in MATLAB, you can use the built-in function "edgeconncomp". This function calculates the edge connectivity of a graph by finding the minimum number of edges that need to be removed to disconnect the graph.
% Create your directed graph (digraph) using the 'digraph' function or other methods.
% For example:
% G = digraph(edges, nodes); % Replace 'edges' and 'nodes' with your actual graph data.
% Compute the edge connectivity using the 'edgeconncomp' function.
connectivity = edgeconncomp(G);
% 'connectivity' will contain the minimum number of edges that need to be removed to disconnect the graph.
disp(['Edge Connectivity: ', num2str(connectivity)]);
##### 1 件のコメント-1 件の古いコメントを表示-1 件の古いコメントを非表示
Arif Billah 2023 年 7 月 27 日
Hi,
Thank you for your answer. When I run the code, I am hit with "Unrecognized function or variable 'edgeconncomp' ". Is there any particular toolbox that I need to have for this? I have searched matlab documentation, Add-on explorer and on google, couldn't find anything on the function 'edgeconncomp'.

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

### カテゴリ

Help Center および File ExchangeGraph and Network Algorithms についてさらに検索

### Community Treasure Hunt

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

Start Hunting!

Translated by