제거가 두 개의 다른 연결을 끊을 버텍스 찾기

Question

두 개의 버텍스 a와 b가 주어진 무향 그래프 G = (V, E)에 대해 O (V + E) 시간 실행되는 알고리즘을 만들려고합니다. 제거로 a와 b가 서로 끊어지게하는 정점 c를 찾습니다. 이것의 일부로서, a에서 b까지의 최단 경로가 V/2보다 큰 경우 G는 a와 b에 대해 'c'를 가져야한다고 주장하려고합니다.

그래프를 보면 왜 v/2보다 큰 경우 a에서 b까지의 길이가 a와 b의 초크 포인트를 가져야하는지 시각적으로 볼 수 있습니다. 그 이유는 길이가 v/2보다 작거나 같으면 a와 b가 다른 꼭지점없이 서로 연결될 수 있기 때문입니다.

알고리즘의 경우 Dijkstra의 알고리즘을 사용하여 a와 b 사이의 최단 경로를 찾은 다음 해당 경로를 따라 정점을 선택하고 제거하고 경로가 동일한 지 확인합니다. 이것은 그것에 대해 갈 길입니까 아니면 더 좋은 방법이 있습니까? 그래프가 너무 무향 때문에

Answer 1

, 정점 c가 존재하는 경우 c는 b 그 반대로 a의 모든 경로에 대한, 그들은 모두 c 통과해야 의미 brigde,

그래서 경우에만 당신은 Dijkstra를 사용할 필요가 없습니다. 간단한 Breadth First Search를 사용하고, BFS에 의해 발견 된 경로의 모든 정점을 시도해보십시오. 제거로 인해 a와 b가 끊어지면 c이됩니다.