네트워크 취약성은 자연재해, 요소 장애, 적대적 공격 등 다양한 장애 발생 시 네트워크 성능이 얼마나 저하되는지를 나타냅니다. 네트워크는 종종 그래프로 표현되는데, 정점과 간선은 각각 노드와 링크에 해당합니다. 따라서 여기서는 네트워크와 그래프라는 용어를 혼용하여 사용합니다. 연결성은 삭제 시 연결이 끊어진 그래프 또는 단일 정점 그래프가 되는 정점의 최소 개수로 정의되며, 네트워크 취약성을 평가하는 가장 중요한 척도로 인식됩니다.

그럼에도 불구하고, 연결성은 그래프의 정점 삭제에 대한 저항성을 부분적으로만 반영합니다. 따라서 네트워크 취약성을 설명하기 위해 다른 지표들을 제안하는 많은 연구가 있었는데, 그중에서도 견고성과 산란수가 가장 널리 사용되는 것으로 보입니다. 견고성과 산란수의 기본 개념은 그래프에서 k개의 정점을 제거했을 때 얻어지는 최대 연결 성분 수입니다. 그래프 G에서 정확히 k개의 정점을 제거했을 때 얻어지는 최대 연결 성분 수를 ck(G)라고 하자. 그래프 G와 양의 정수 k가 주어졌을 때, ck(G)를 구하는 문제는 계산적으로 매우 어렵다는 것은 안타까운 일입니다.

그러나 구간 그래프와 같은 일부 그래프 클래스의 경우, ck(G)는 다항 시간으로 계산될 수 있습니다. 구간 그래프는 실수선 위의 (폐구간) 구간들의 교점 그래프로, 두 정점이 간선으로 연결될 때, 해당 구간들이 서로 교차하는 경우에만 해당 구간들이 연결됩니다. 이 구간들을 일반적으로 구간 표현이라고 합니다. 구간 그래프와 구간 표현의 예는 그림 E.1을 참조하십시오.

n개의 정점을 갖는 구간 그래프 G의 구간 표현이 주어졌을 때, {0, 1, …, k − 1}에 포함된 모든 k에 대해 ck(G)를 계산하는 효율적인 실행 프로그램을 작성해야 합니다. 예를 들어 그림 E.1(b)에 표시된 구간 표현이 주어졌을 때, ܿc0(G), c1(G), c2(G), c3(G), c4(G), c5(G), c6(G), c7(G)는 각각 1, 1, 1, 2, 2, 3, 2, 1입니다.

#4388 upload 5 done 1 how_to_reg 1

Network Vulnerability timer 3s memory 512MB

#4388

Network Vulnerability 3s 512MB