Finding bridge of not isolated vertices

3 Ansichten (letzte 30 Tage)
Lukas Marcinkevicius
Lukas Marcinkevicius am 2 Dez. 2020
Bearbeitet: Christine Tobler am 2 Dez. 2020
I need to create a cycle that goes through the array of graph edges and finds all non isolated bridges( its vertices have to be not isolated) in between two connected components.
Any suggestions or examples would be great. Thanks in advance.

Antworten (1)

Christine Tobler
Christine Tobler am 2 Dez. 2020
Bearbeitet: Christine Tobler am 2 Dez. 2020
There is no functionality for MATLAB's graph class that would compute the bridges / cut edges.
If performance is not a main concern, you could go by definition: For each edge, try removing that edge and check shortestpath to see if there is still a connection between those nodes. If no, that edge is a bridge. You'd need to look at rmedge and shortestpath functions for this. An alternative to calling shortestpath would be to call conncomp and check if the number of connected components has increased - this might be slightly more expensive.
One more thing you could do to limit the amount of edges that are candidates for being a bridge is to call biconncomp. The second output contains the articulation points (or cut vertices), and according to Wikipedia, "The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints." So if the two endpoints of an edge aren't articulation points, we know ahead of time that this edge cannot be a bridge.

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

Produkte


Version

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by