2

I'm theoretical chemist, and I want to find all bonds which (when broken) split the molecule to two disconnected parts. In other words I want to find all such bonds which are not-redudant - meaning, if you break them, there is no other connection (between the two parts of molecule) left.

I guess this should be some standard problem from graph-theory (considering molecule is graph where atoms are nodes and bonds are edges)

I can write some brute-force algorithm which test each bond, wheather it is redudant or not (by traversing the graph from one side of the bond, and checking if I can reach the node form the other side of the bond). But this seems quite inefficient to me. And I believe there should be more efficient algorithm which can find all such bonds by traversing the graph just once (of just few time - much less than number of bonds).

There is illustration example. I wan't to find the red bonds. enter image description here

Prokop Hapala
  • 2,424
  • 2
  • 30
  • 59
  • 6
    These are called [bridges](https://en.wikipedia.org/wiki/Bridge_(graph_theory)). There is indeed a [linear time](https://stackoverflow.com/questions/11218746/bridges-in-a-connected-graph) algorithm for finding all of them. – kcsquared Mar 07 '22 at 14:28

0 Answers0