[Elettrotecnica] Insiemi di taglio
Ho letto la definizione di insieme di taglio, ma non capisco questi esempi.
Mi trovo con gli insiemi di taglio T1 e T6, perché se rimossi lasciano i lati 1,3 nel primo caso e 2,4 nel secondo caso. Tali lati sono sottografi connessi e sono tra loro separati, ma un lato a caso dell'insieme di taglio è capace di ricollegarli.
Tutti gli altri insiemi di taglio, però, non creano due sottografi connessi separati. Ad esempio, se rimuovo T2 restano i lati 2,3 collegati dal nodo 3, e dunque non separati.
Perché sono considerabili insiemi di taglio?
Risposte
Con quelle figure è chiaro che non lo puoi capire, ma ti rispondo chiedendoti:
i) come è definito un "grafo" ?
ii) come è definito un "taglio" ?
iii) come è definito un "insieme di taglio" ?
i) come è definito un "grafo" ?
ii) come è definito un "taglio" ?
iii) come è definito un "insieme di taglio" ?
Un grafo è una funzione dei nodi e dei lati di un circuito. Crea una matrice d'incidenza che relaziona nodi e lati tramite un elemento uguale ad 1 se il lato è uscente dal nodo, -1 se entrante, 0 se non collegati direttamente.
Un taglio permette di dividere in due sottoinsiemi i nodi di un circuito.
Un insieme di taglio è un insieme di lati che divide un grafo connesso in due sottografi connessi ma separati tra loro. Inoltre la rimozione di tutti i lati dell'insieme di taglio tranne uno rende i due sottografi di nuovo connessi.
Per questo non mi trovo con gli esempi T2, T3, T4 e T5.
Un taglio permette di dividere in due sottoinsiemi i nodi di un circuito.
Un insieme di taglio è un insieme di lati che divide un grafo connesso in due sottografi connessi ma separati tra loro. Inoltre la rimozione di tutti i lati dell'insieme di taglio tranne uno rende i due sottografi di nuovo connessi.
Per questo non mi trovo con gli esempi T2, T3, T4 e T5.
Esatto, un "grafo" è un insieme di nodi e rami , un "taglio" è una partizione dell'insieme dei nodi, a cui corrisponde un "insieme di taglio" [nota]Volendo essere precisi, per un generico grafo costituito da N parti separate, un "insieme di taglio" è un'insieme di lati del grafo che soddisfa alle seguenti proprietà:
1. la rimozione di tutti i lati dell’insieme di taglio fa sì che il restante grafo abbia N + 1 parti separate;
2. la rimozione di tutti i lati dell’insieme di taglio eccetto uno arbitrario lascia il grafo in N parti separate.[/nota] costituito dall'insieme di tutti i rami che vanno a connettere le coppie di nodi dei due sottoinsiemi.
Nell'immagine da te postata, doveve essere evidenziato che l'insieme di taglio è costituito dai soli lati e non dai nodi.
Prendendo ad esempio il taglio T2, avrai quindi che la partizione dei nodi sarà {1,2,4} , {3} e l'insieme di taglio associato sarà costituito dai lati [2,3,5], ne segue che il primo sottografo sarà costituito dai nodi {1,2,4} e dai rami [1,4], il secondo grafo [nota]Grafo degenere.[/nota] dal solo nodo {3}.
1. la rimozione di tutti i lati dell’insieme di taglio fa sì che il restante grafo abbia N + 1 parti separate;
2. la rimozione di tutti i lati dell’insieme di taglio eccetto uno arbitrario lascia il grafo in N parti separate.[/nota] costituito dall'insieme di tutti i rami che vanno a connettere le coppie di nodi dei due sottoinsiemi.
Nell'immagine da te postata, doveve essere evidenziato che l'insieme di taglio è costituito dai soli lati e non dai nodi.
Prendendo ad esempio il taglio T2, avrai quindi che la partizione dei nodi sarà {1,2,4} , {3} e l'insieme di taglio associato sarà costituito dai lati [2,3,5], ne segue che il primo sottografo sarà costituito dai nodi {1,2,4} e dai rami [1,4], il secondo grafo [nota]Grafo degenere.[/nota] dal solo nodo {3}.
Non ho capito molto bene.
Nel caso di T2, l'insieme di taglio non dovrebbe essere formato dai lati 1,4,5? (come nell'immagine?) Mentre la partizione dei nodi dovrebbe essere {1}, {2, 3, 4}.
E soprattutto non vedo ancora perché l'insieme dei tre lati 1,4,5 rimosso dal grafo dovrebbe creare due sottografi non connessi, dato che ciò che resta del grafo iniziale sono i due lati 2,3 che costituiscono un grafo connesso perché uniti dal nodo 3.
In pratica vorrei capire perché nel caso di T1 e T6, rimuovendo i lati dell'insieme di taglio, venga rispettata la definizione (perché restano rispettivamente i lati 1,3 e 2,4 del grafo, che sono separati) mentre negli altri casi no.
Nel caso di T2, l'insieme di taglio non dovrebbe essere formato dai lati 1,4,5? (come nell'immagine?) Mentre la partizione dei nodi dovrebbe essere {1}, {2, 3, 4}.
E soprattutto non vedo ancora perché l'insieme dei tre lati 1,4,5 rimosso dal grafo dovrebbe creare due sottografi non connessi, dato che ciò che resta del grafo iniziale sono i due lati 2,3 che costituiscono un grafo connesso perché uniti dal nodo 3.
In pratica vorrei capire perché nel caso di T1 e T6, rimuovendo i lati dell'insieme di taglio, venga rispettata la definizione (perché restano rispettivamente i lati 1,3 e 2,4 del grafo, che sono separati) mentre negli altri casi no.
"maxira":
Non ho capito molto bene.
Nel caso di T2, l'insieme di taglio non dovrebbe essere formato dai lati 1,4,5? (come nell'immagine?) Mentre la partizione dei nodi dovrebbe essere {1}, {2, 3, 4}. ...
Sì, scusa, ho confuso T2 con T5.
"maxira":
... E soprattutto non vedo ancora perché l'insieme dei tre lati 1,4,5 rimosso dal grafo dovrebbe creare due sottografi non connessi, dato che ciò che resta del grafo iniziale sono i due lati 2,3 che costituiscono un grafo connesso perché uniti dal nodo 3. ...
Rimossi i tre lati 1,4,5, il primo sottografo sarà costituito dal solo punto {1}, che è comunque, per definizione, un grafo "connesso", mentre il secondo sottografo (connesso) sarà costituito dal nodo 3 e dai lati 2 e 3.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo