Finding bridge of not isolated vertices

3 visualizaciones (últimos 30 días)
Lukas Marcinkevicius
Lukas Marcinkevicius el 2 de Dic. de 2020
Editada: Christine Tobler el 2 de Dic. de 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.

Respuestas (1)

Christine Tobler
Christine Tobler el 2 de Dic. de 2020
Editada: Christine Tobler el 2 de Dic. de 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.

Categorías

Más información sobre Graph and Network Algorithms en Help Center y File Exchange.

Productos


Versión

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by