Scopri la matrice fondamentale di taglio nella teoria dei grafi: definizione costruzione passo-passo regole di orientamento e esempi con soluzioni.
Quando parliamo di matrice dei tagli in teoria dei grafi, generalmente ci riferiamo alla matrice fondamentale dei tagli. Un taglio è un insieme minimo di rami di un grafo connesso tale che, quando questi rami vengono rimossi dal grafo, esso si separa in due parti distinte chiamate sottografi e la matrice dei tagli è la matrice ottenuta prendendo uno per volta i tagli in riga. La matrice dei tagli è denotata dal simbolo [Qf].

Due sottografi sono ottenuti da un grafo selezionando tagli composti dai rami [1, 2, 5, 6].
In altre parole, possiamo dire che il taglio fondamentale di un dato grafo rispetto a un albero è un taglio formato con un ramo dell'albero (twig) e i restanti collegamenti (links). I twigs sono i rami dell'albero e i links sono i rami del co-albero.
Pertanto, il numero di tagli è uguale al numero di twigs.
[Numero di twigs = N – 1]
Dove, N è il numero di nodi del grafo o dell'albero tracciato.
L'orientamento del taglio è lo stesso di quello del twig e viene considerato positivo.
Ci sono alcuni passaggi che si dovrebbero seguire mentre si disegna la matrice dei tagli. I passaggi sono i seguenti-
Disegnare il grafo della rete o del circuito dato (se fornito).
Poi disegnarne l'albero. I rami dell'albero saranno i twigs.
Poi disegnare i restanti rami del grafo con una linea tratteggiata. Questi rami saranno i links.
Ogni ramo o twig dell'albero formerà un taglio indipendente.
Scrivere la matrice con le righe come tagli e le colonne come rami.
| Rami ⇒ | 1 | 2 | 3 | . | . | b | |
| Tagli | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = numero di tagli.
b = numero di rami.
Qij = 1; se il ramo J è nel taglio con orientamento uguale a quello del ramo dell'albero.
Qij = -1; se il ramo J è nel taglio con orientamento opposto a quello del ramo dell'albero.
Qij = 0; se il ramo J non è nel taglio.
Esempio 1
Disegnare la matrice dei tagli per il seguente grafo.
Risposta:
Passo 1: Disegnare l'albero per il seguente grafo.
Passo 2: Ora identificare il taglio. Il taglio sarà quel nodo che conterrà solo un twig e qualsiasi numero di links.
Qui C2, C3 e C4 sono tagli.
Passo 3: Ora disegnare la matrice.
| Rami ⇒ | 1 | 2 | 3 | 4 | 5 | 6 | |
| Tagli | |||||||
| C2 | +1 | ||||||