브릿지의 방향 지정 그래프 검사

주어진 방향 그래프에 브릿지가 포함되어 있는지 여부를 확인하기 위해 빠른 알고리즘을 찾고 있습니다 ...
그래프에 포함되어 있는지 여부 만 고려하십시오. 아닙니다.브릿지의 방향 지정 그래프 검사

2011-10-14 Ahmad Ibrahem

여기를보십시오 : http://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 – harold

@harold 그것은 직접적인 그래프입니다. –

방금 더 좋은 해결책을 찾았습니다.
간단한 노드를 선택하고 모든 노드가 방문했는지 확인한 다음 모든 노드를 반대로하고 동일한 노드에서 시작하여 방문 할 수 있는지 확인하십시오 모든 노드가 다시 그렇지 않으면 반드시 브리지가 포함됩니다.

출처

2011-12-22 11:24:09

에지가 어떤주기에도 포함되어 있지 않은 경우에만 브리지이므로 가장자리에 그래프가 강하게 연결되어 있지 않으면 브리지가 있어야합니다.

그래프에서 Tarjan strongly connected components algorithm을 실행하십시오. 결과가 다르면 그래프에 다리가 있습니다.

출처

2011-10-14 13:14:28

나는이 알고리즘에 대해 알고있다. 그러나 나는 브리지의 위치를 원하지 않기 때문에 이것을하는 더 쉬운 방법이 될 것이라고 생각했다 ... 나는 단지 그것이 강하게 연결되어 있는지 확인하려고한다. –

@ AhmadIbrahem 저는 이것이 가장 빠른 방법이라고 생각합니다 : http://en.wikipedia.org/wiki/Strongly_connected_component –

@SaeedAmiri 그래프가 강하게 연결되어 있으면 모든 엣지가주기에 포함됩니다 –

그래프가 방향성이있는 그래프의 경우와 마찬가지로, 에지가 이라는 강력한 브리지을 제거하면 그래프의 강하게 연결된 구성 요소의 수가 증가합니다. 유향 그래프에 강력한 브리지가 있는지 테스트하려면 논문에 설명 된 알고리즘을 실행해야합니다. Giuseppe F. Italiano, Luigi Laura, Federico Santaroni : 선형 시간에 강한 다리와 강한 관절 점 찾기. Theor. 계산. Sci. 447 : 74-84 (2012) http://dx.doi.org/10.1016/j.tcs.2011.11.011

출처

2013-06-14 11:37:02 Rogatienne

브릿지의 방향 지정 그래프 검사

답변

관련 문제