강력한 연결성 증대

강한 연결 증가는 그래프 알고리즘의 수학적 연구에서 계산적인 문제로, 입력은 지시된 그래프이고 문제의 목표는 적은 수의 에지 또는 작은 총중량의 에지 집합을 추가하여 추가된 에지가 그래프를 강하게 연결된 그래프로 만드는 것이다.

강력한 연결성 증대 문제는 카팔리 에스워란과 로버트 타르잔(1976년)에 의해 공식화되었다.그들은 문제의 가중치가 있는 버전은 NP-완전이지만 가중치가 없는 문제는 선형 시간 내에 해결할 수 있다는 것을 보여주었다.^[1]후속 연구는 가중 문제의 근사 비율과 매개변수화된 복잡성을 고려했다.^[2][3]

가중치 없는 버전

가중치가 없는 강한 연결성 확대 문제에서 입력은 지시된 그래프이며, 목표는 결과를 강하게 연결된 그래프로 만들기 위해 가능한 한 적은 에지를 추가하는 것이다.에스워란과 타르잔의 미가중 사례 알고리즘은 주어진 그래프의 강하게 연결된 성분당 하나의 꼭지점을 갖는 방향의 아크릴 그래프인 주어진 지시된 그래프의 응결을 고려한다.$s{\displaystyle }$ ${\displaystyle s}$은(는) 응축의 소스 꼭지점 수(최소 하나의 송신 에지는 있지만 수신 에지는 없는 강하게 연결된 구성 요소)를 나타내고$$ t ${\displaysty$ t$}$은 응축의 싱크 꼭지점 수(수신 에지는 없지만 송신 에지는 없는 구성 요소) 및 $q{\displaystyle }$ ${\dis$)를 나타낸다$$.$Playstyle q}$은 응축에서 분리된 정점의 수를 나타내며$$(수신 또는 송신 에지가 없는 연결된 구성 요소) 추가될 가장자리 수는 최소한 ${\displaystyle max(s}$ ${\displaystyle +}$ ${\displaystyle q,t}$ + ${\displaystyle q}$ ${\displaystyle )}$ ${\displaystyle \max(s+q,t+q$인 것을 관찰한다.이는 $각{\displaystyle }$ 소스 또는 절연 정점에 대한 수신 에지를 제공하기 위해 s${\displaystyle }$+ ${\displaystyle q}$ ${\displaystyle s+q}$ 에지를$$ 추가해야 하며, 각 싱크 또는 절연 정점에 대한 송신 에지를 제공하기 위해 대칭적으로 최소 $t{\displaystyle }$+ ${\displaystyle q}$ ${\displaystyty t+$q$$} 에지를 추가해야 하기 때문이다.문제에 대한 이들의 알고리즘은 그래프에 추가할 정확히 ${\displaystyle 최대값}$ 집합${\displaystyle (s}$ +${\displaystyle q,}$ ${\displaystyle t}$ +${\displaystyle }$q $){\displaystyle \max(s+q,t+q)}$개의 가장자리를$$ 찾아 강하게 연결된다.^[1]

이들의 알고리즘은 응축에 대한 깊이 우선 검색을 사용하여 다음과 같은 특성을 가진 선원과 싱크 쌍의 컬렉션을 찾는다.^[1]

• 각 쌍의 출처는 주어진 그래프에서 경로를 통해 쌍의 싱크대에 도달할 수 있다.
• 쌍 중 하나에 없는 모든 선원은 쌍 중 하나에 있는 싱크대에 도달할 수 있다.
• 한 쌍에 없는 모든 싱크대는 한 쌍의 원천에서 도달할 수 있다.

소스와 싱크 쌍을 찾는 알고리즘 부분의 사소한 오류가 나중에 발견되어 수정되었다.^[4]

이러한 쌍이 발견되면 다음과 같은 세 가지 에지를 추가하여 강력한 연결 증대를 얻을 수 있다.^[1]

• 첫 번째 에지 세트는 쌍과 응결의 절연 정점을 단일 사이클로 연결하고, 쌍당 하나의 에지 또는 절연 정점으로 구성된다.
• 두 번째 가장자리 세트는 각각 나머지 싱크 중 하나를 나머지 소스 중 하나에 연결한다( 임의로).이것은 소스 쌍과 싱크 모두를 소스-싱크 쌍당 하나의 에지 비용으로 쌍과 분리된 정점들의 주기에 연결한다.
• 앞의 두 세트의 가장자리가 모든 소스를 소진하거나 모든 싱크대를 소진하면 세 번째 가장자리 세트는 각 남은 소스를 연결하거나 소스 또는 싱크당 하나의 가장자리를 더 추가함으로써 이 사이클로 싱크한다.

이 세트의 총 에지 수는 ${\displaystyle 최대(s}$ +${\displaystyle q,}$ ${\displaystyle t}$+ ${\displaystyle q}$ )${\displaystyle \max(s+q,t+q)}$ 입니다$.$^[1]

가중 및 매개 변수화된 버전

추가될 수 있는 각 가장자리의 가중치는 주어진 가중치를 가지며, 목표는 주어진 그래프를 강하게 연결시키는 최소 무게의 추가된 가장자리 집합을 선택하는 것이다.^[1]근사 비율 2의 근사 알고리즘은 프레드릭슨 & 자'Ja'(1981)에 의해 제공되었다.^[2]주어진 그래프를 강하게 연결하기 위해 최소 총 중량의 최대 $k{\displaystyle }$ ${\displaystyle k}$ 가장자리를$$ 추가해야 하는 문제의 매개변수화 및 가중치 버전은 고정 매개변수 추적 가능하다.^[3]

초당적 버전 및 그리드 브레이싱 애플리케이션

사각형 그리드가 격자 가장자리의 유연한 관절에 의해 서로 연결된 강체 로드(그리드 가장자리)로 만들어지면 전체적인 구조는 정사각형으로 남는 것이 아니라 여러 가지 방법으로 구부러질 수 있다.그리드 브레이싱 문제는 정사각형의 일부 내에 교차 브레이싱을 추가함으로써 그러한 구조를 안정화하는 방법을 묻는다.이 문제는 그래프 이론을 사용하여 모델화할 수 있으며, 각 행 또는 격자 내 정사각형 열에 대한 꼭지점과 주어진 행과 열의 정사각형이 교차 브레이싱될 때 이 두 꼭지점 사이의 가장자리를 가진 초당적 그래프를 만들 수 있다.각 사각형 내의 교차 브레이싱이 이 그래프를 완전히 경직하게 만들면 이 그래프는 방향을 잡지 않으며 연결된 그래프일 경우에만 경직된 구조를 나타낸다.^[5]그러나 사각형이 부분적으로만 브레이싱된 경우(예를 들어 확장 운동을 방지하지만 수축 운동을 방지하지 않는 끈이나 와이어로 반대쪽 두 모서리를 연결함으로써) 그래프가 방향화되고, 강하게 연결된 그래프인 경우에만 경직된 구조를 나타낸다.^[6]

관련 강력한 연결성 확대 문제는 정사각형 일부에 이미 부분 브레이싱이 있는 그리드에 더 많은 부분 브레이싱을 추가하는 방법을 묻는다.기존의 부분 브레이싱은 지시된 그래프로 나타낼 수 있으며 추가 부분 브레이싱은 해당 그래프의 강력한 연결성 확대를 형성해야 한다.강력한 연결 증분 문제에 대한 솔루션을 원래의 브레이싱 문제의 해결책으로 되돌릴 수 있으려면 추가 제한이 필요하다. 각 추가된 에지는 원래 그래프의 양분성을 존중해야 하며 행을 행이나 공동에 연결하려고 시도하지 않고 행 정점만 열 정점으로 연결해야 한다.기둥에 휘감다이 강력한 연결성 확대 문제의 제한된 버전은 선형 시간 내에 다시 해결될 수 있다.^[7]

참조