그래프 이론에서 절단 집합 행렬을 이야기할 때는 일반적으로 기본 절단 집합 행렬을 의미합니다. 절단 집합은 연결 그래프의 최소한의 가지들로 구성되며, 이러한 가지들을 그래프에서 제거하면 그래프가 두 개의 서로 다른 부분인 하위 그래프로 분리됩니다. 절단 집합 행렬은 각각의 절단 집합을 한 번에 행으로 취하여 얻어진 행렬입니다. 절단 집합 행렬은 [Qf] 기호로 표시됩니다.

그래프에서 [1, 2, 5, 6] 가지로 구성된 절단 집합을 선택하여 두 개의 하위 그래프를 얻습니다.
즉, 주어진 그래프와 트리를 기준으로 기본 절단 집합은 하나의 트위그와 나머지 링크로 구성된 절단 집합을 말합니다. 트위그는 트리의 가지이고 링크는 코-트리의 가지입니다.
따라서, 절단 집합의 수는 트위그의 수와 같습니다.
[트위그의 수 = N – 1]
여기서, N은 주어진 그래프 또는 그린 트리의 노드 수입니다.
절단 집합의 방향은 트위그의 방향과 동일하며, 이를 양수로 취합니다.
다음은 절단 집합 행렬을 그리는 데 따라야 하는 몇 가지 단계입니다.
주어진 네트워크 또는 회로의 그래프를 그립니다 (주어진 경우).
그 다음 트리를 그립니다. 트리의 가지들은 트위그가 됩니다.
그 다음 그래프의 나머지 가지들을 점선으로 그립니다. 이러한 가지들은 링크가 됩니다.
트리의 각 가지 또는 트위그는 독립적인 절단 집합을 형성합니다.
행으로 절단 집합, 열로 가지를 갖는 행렬을 작성합니다.
| 가지 ⇒ | 1 | 2 | 3 | . | . | b | |
| 절단 집합 | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = 절단 집합의 수.
b = 가지의 수.
Qij = 1; 가지 J가 트리 가지와 같은 방향으로 절단 집합에 있을 때.
Qij = -1; 가지 J가 트리 가지와 반대 방향으로 절단 집합에 있을 때.
Qij = 0; 가지 J가 절단 집합에 있지 않을 때.
예제 1
다음 그래프에 대한 절단 집합 행렬을 그립니다.
답변:
단계 1: 다음 그래프의 트리를 그립니다.
단계 2: 이제 절단 집합을 식별합니다. 절단 집합은 하나의 트위그와 임의의 링크 수를 포함하는 노드가 될 것입니다.
여기서 C2, C3 및 C4는 절단 집합입니다.
단계 3: 이제 행렬을 그립니다.