Aprenda sobre a matriz de corte fundamental na teoria dos grafos: definição construção passo a passo regras de orientação e exemplos com soluções
Quando falamos de matriz de corte em teoria dos grafos, geralmente nos referimos à matriz fundamental de corte. Um conjunto de corte é um conjunto mínimo de ramos de um grafo conexo tal que, quando esses ramos são removidos do grafo, o grafo se separa em duas partes distintas chamadas subgrafos e a matriz de corte é a matriz obtida ao tomar um conjunto de corte de cada vez, linha por linha. A matriz de corte é denotada pelo símbolo [Qf].

Dois subgrafos são obtidos a partir de um grafo selecionando conjuntos de corte compostos pelos ramos [1, 2, 5, 6].
Assim, em outras palavras, podemos dizer que o conjunto fundamental de corte de um dado grafo, com referência a uma árvore, é um conjunto de corte formado com um ramo da árvore (trepadeira) e os demais links. Trepadeiras são os ramos da árvore e links são os ramos do co-árvore.
Portanto, o número de conjuntos de corte é igual ao número de trepadeiras.
[Número de trepadeiras = N – 1]
Onde, N é o número de nós do grafo ou árvore desenhada.
A orientação do conjunto de corte é a mesma da trepadeira e é considerada positiva.
Existem alguns passos que devem ser seguidos ao desenhar a matriz de corte. Os passos são os seguintes-
Desenhe o grafo da rede ou circuito dado (se fornecido).
Em seguida, desenhe sua árvore. Os ramos da árvore serão as trepadeiras.
Em seguida, desenhe os ramos restantes do grafo com linha pontilhada. Esses ramos serão os links.
Cada ramo ou trepadeira da árvore formará um conjunto de corte independente.
Escreva a matriz com as linhas como conjuntos de corte e as colunas como ramos.
| Ramos ⇒ | 1 | 2 | 3 | . | . | b | |
| Conjuntos de Corte | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = número de conjuntos de corte.
b = número de ramos.
Qij = 1; se o ramo J estiver no conjunto de corte com a mesma orientação do ramo da árvore.
Qij = -1; se o ramo J estiver no conjunto de corte com orientação oposta ao ramo da árvore.
Qij = 0; se o ramo J não estiver no conjunto de corte.
Exemplo 1
Desenhe a matriz de corte para o seguinte grafo.
Resposta:
Passo 1: Desenhe a árvore para o seguinte grafo.
Passo 2: Agora identifique o conjunto de corte. O conjunto de corte será o nó que conterá apenas uma trepadeira e qualquer número de links.
Aqui, C2, C3 e C4 são conjuntos de corte.
Passo 3: Agora, desenhe a matriz.
| Ramos ⇒ | 1 | 2 | 3 | 4 | 5 | 6 | |
| Conjuntos de Corte | |||||||
| C2 | +1 | ||||||