주어진 Q 정점을 삭제한 후 주어진 그래프의 연결된 구성 요소 수

Q개의 지정된 정점을 제거한 후 그래프의 나머지 정점에 의해 생성된 연결이 끊긴 하위 그래프의 수는 연결된 구성 요소의 수로 표시됩니다. 개별 구성 요소 사이에는 가장자리 연결이 없습니다. 대신 연결된 각 구성 요소는 가장자리로 연결된 정점 모음으로 구성됩니다. Q 정점 제거로 인해 일부 정점이 고아가 되어 연결이 붕괴되고 새로운 구성요소가 형성될 수 있습니다. 이 방법은 결국 연결이 끊긴 하위 그래프의 수를 결정하는 것을 목표로 합니다. 네트워크 분석, 소셜 네트워크 연구, 최적화 방법을 포함한 많은 응용 프로그램에는 연결된 구성 요소 수에 대한 지식이 필요합니다.

사용방법

• 코사라주 알고리즘

• 행렬 기반 방법

코사라주 알고리즘

그래프에서 지정된 Q 정점을 제거한 후 Kosaraju의 알고리즘을 사용하여 네트워크에서 연결된 구성 요소의 수를 결정합니다. 두 단계로 깊이 우선 검색(DFS)을 사용합니다. 각 정점의 "완료 시간"을 얻기 위해 첫 번째 패스에서 원본 그래프를 연구합니다. 두 번째 패스에서는 그래프가 전치(모든 간선의 방향이 반대)되고, 변환된 그래프에 완료 시간이 가장 긴 정점부터 시작하여 DFS가 적용됩니다. 이 방법은 변경된 그래프에서 연결된 구성 요소 수를 결정하고, 프로세스에서 삭제된 Q 정점을 무시하여 정점 삭제 시 깨진 하위 그래프 수를 노출합니다.

알고리즘

• 초기 DFS 채널의 정점을 저장하려면 빈 스택을 생성하세요.

• 원래 그래프에서 첫 번째 DFS 순회를 실행합니다.

  DFS를 사용하여 탐색되지 않은 꼭짓점에서 시작하여 연결된 꼭짓점의 구성 요소를 탐색합니다.

  정점 주변의 모든 정점을 방문하면 Mark는 정점에 액세스하여 스택에 푸시합니다.

• 각 가장자리의 방향을 바꾸어 모양을 바꿉니다.

• 두 번째 DFS 패스의 경우 방문한 정점을 추적하는 부울 배열을 만듭니다.

• 두 번째 DFS 패스를 통해 수정된 그래프를 실행합니다.

  스택에서 각 정점을 차례로 제거합니다.

  DFS를 사용하여 정점의 관련 구성 요소(없는 경우)가 액세스되거나 파괴되지 않는지(Q에서는 아님) 탐색합니다. 그 과정 내내 마크는 정점을 방문했다.

• Q 꼭지점을 제거한 후 연결된 구성 요소의 수는 두 번째 DFS에 대한 호출 수와 같습니다.

• Q 정점을 제거한 후 이 프로세스는 네트워크에 연결된 구성요소 수를 생성합니다.

예

으아악

출력

으아악

행렬 기반 방법

인접 행렬 또는 인접 목록은 행렬 기반 방법에서 그래프를 나타내는 데 사용됩니다. 그런 다음 행렬에서 Q개의 지정된 정점을 제거합니다. 그런 다음 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)과 같은 그래프 순회 알고리즘을 사용하여 변경된 그래프의 연결된 구성 요소 수를 결정합니다. 재처리를 방지하기 위해 통과한 정점을 기록합니다. Q 정점을 제거한 후 그래프의 연결된 구성 요소 수는 순회 방법이 실행된 횟수에 해당합니다. 이 방법은 다양한 그래프 분석 및 네트워크 관련 애플리케이션에 대한 링크 구성 요소 수를 효율적으로 계산할 수 있습니다.

알고리즘

• 인접 행렬이나 인접 목록을 사용하여 그래프를 표현하세요.

• 수정된 그래프는 행렬이나 목록에서 지정된 Q 정점을 제거하여 생성됩니다.

• 연결된 구성요소 수를 추적하는 변수를 설정하세요.

• 처음에는 그래프의 각 정점을 반복적으로 업데이트합니다.

• 탐색되지 않은 각 정점에 그래프 순회 알고리즘(DFS 또는 BFS)을 적용합니다.

• 재처리를 방지하기 위해 순회 중에 방문한 정점을 표시합니다.

• 초기 정점과 관련된 모든 정점이 보일 때까지 계속 탐색합니다.

• 발견된 고유한 상호 연결된 정점 집합마다 방정식의 연결된 구성 요소 수를 1씩 늘립니다.

• 업데이트된 그래프의 모든 꼭짓점에 액세스하려면 필요에 따라 5~8단계를 반복하세요.

• 필요한 정점을 제거한 후 그래프에서 연결이 끊긴 하위 그래프의 총 수는 연결된 구성 요소 수의 최종 값으로 표시됩니다.

예

으아악

출력

으아악

결론

요약하자면, 네트워크 분석 및 관련 분야의 핵심 지표는 일정 개수의 꼭짓점을 제거한 후 그래프에 남아 있는 연결된 구성요소의 개수입니다. 행렬 기반 방법과 Kosaraju의 알고리즘은 모두 이 개수를 계산하는 효율적인 방법을 제공합니다. 행렬 기반 방법은 재설계된 그래프에서 DFS 또는 BFS와 같은 그래프 순회 알고리즘을 사용하여 연결된 구성 요소를 효율적으로 찾는 반면, Kosaraju 알고리즘은 두 순회에서 깊이 우선 검색을 사용하여 강하게 연결된 구성 요소를 식별합니다. 두 방법 모두 일부 정점을 제거한 후에도 신뢰할 수 있는 결과를 생성하므로 그래프의 연결성과 구조적 특성을 이해하는 데 도움이 됩니다. 그래프의 속성과 현재 과제의 특정 요구 사항에 따라 사용할 방법이 결정됩니다.

위 내용은 주어진 Q 정점을 삭제한 후 주어진 그래프의 연결된 구성 요소 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!