Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

6
voti

Teoria dei grafi, distanza resistiva e indice di Kirchhoff

Indice

Abstract

In questo breve articolo tratterò il concetto di distanza resistiva e di indice di Kirchhoff. Lo scopo principale è pertanto quello di far conoscere questi due aspetti intimamente legati alla teoria delle reti e alla teoria dei grafi.

Nonostante possa apparire strano, tali valori trovano larga diffusione nella teoria dei grafi applicata alle scienze chimiche.

Nel paragrafo di introduzione discuterò brevemente i concetti di grafo, matrice d'incidenza e matrice di adiacenza. Nel secondo paragrafo, invece, tratterò il concetto di distanza resistiva e di indice di Kirchhoff.

Introduzione

Quando applichiamo la teoria dei grafi allo studio delle reti elettriche, sostituiamo ogni elemento della rete in oggetto con un lato o ramo e alle estremità di ogni lato disegniamo due nodi o vertici. Alla fine di questa operazione otteniamo un disegno chiamato grafo delle rete.

Nella figura seguente è rappresentata una rete elettrica con il relativo grafo.

Figura 1 - Esempio di rete elettrica e relativo grafo.

Il grafo della figura 1 ha quattro nodi e cinque lati. A livello intuitivo possiamo capire che il grafo di una rete elettrica è un insieme di lati e di nodi e ogni lato inizia e termina in un nodo. L'esempio che abbiamo appena visto riguarda un grafo non orientato. In altre parole, i lati del grafo non hanno una direzione di riferimento.

Considerando le convenzioni associate utilizzate in elettrotecnica, possiamo disegnare il grafo orientato della rete elettrica. Questa volta, i lati del grafo hanno una direzione di riferimento. Riproponiamo l'esempio della figura 1, orientando il grafo.

Figura 2 - Esempio di rete elettrica e relativo grafo orientato.

A questo punto possiamo scrivere le seguenti definizioni.

Definizione 1 (di grafo): Un grafo \text{G}\left ( \text{V},\text{E}\right ), o semplicemente G, è costituito da un insieme V di elementi detti nodi e da un insieme E di coppie non ordinate di elementi in V, \left ( i,j\right ) o \left ( j,i\right ), chiamati lati (anche rami o archi).
Definizione 2 (di grafo orientato): Un grafo orientato \text{G}\left ( \text{V},\text{E}\right ), o semplicemente G, è costituito da un insieme V di elementi detti nodi e da un insieme E di coppie ordinate di elementi in V, \left ( i,j\right ), chiamati lati orientati (anche rami o archi orientati).
Definizione 3 (di grafo connesso): Un grafo si dice connesso se ogni coppia dei suoi nodi sono connessi (collegati) da un percorso, indipendentemente dalla eventuale direzione assegnata ai lati.

Informalmente, possiamo dire che un grafo connesso è formato da un solo disegno. Per chiarire meglio questo aspetto informale, facciamo riferimento alla figura seguente.

Figura 3 - Esempio di grafo connesso e grafo non connesso.


Inoltre, vale il seguente teorema:

Teorema 1: Un grafo connesso con n vertici ha almeno n-1 lati.


Anticipiamo subito che le definizioni e la terminologia utilizzate nell'ambito delle teoria dei grafi e delle relative applicazioni non è univoca, pertanto è possibile trovare in letteratura termini e definizioni differenti rispetto a quanto riportato in questo articolo.

Le definizioni qui riportate sono quelle più intuitive e trovano un riscontro immediato nella teoria delle reti. Si precisa che faremo riferimento esclusivamente a grafi semplici, quindi grafi il cui insieme E è formato da elementi tutti distinti e senza cappi.

Matrice d'incidenza

Consideriamo un grafo (orientato o non orientato) con n nodi e l lati.

Chiamiamo matrice di incidenza Aa (di nodi-lati) una matrice rettangolare di n righe e l colonne i cui elementi sono così definiti:

a_{i,j}=\left\{\begin{matrix}
1 & \textrm{se \,il\, lato\, j \,esce\, dal\, nodo\, i}\\ 
-1 & \textrm{se\, il\, lato\, j \,entra \,nel \,nodo\, i}\\ 
0 & \textrm{altrimenti\, (lato\, j\, non \,incide\, col \,nodo\, i)}
\end{matrix}\right.

Questa è chiaramente la matrice d'incidenza di un grafo orientato.

Una matrice simile si può definire anche nel caso di grafo non orientato:

a_{i,j}=\left\{\begin{matrix}
1 & \textrm{se\, il \,lato \,j \,incide \,il\, nodo\, i}\\ 

0 & \textrm{altrimenti \,(lato\, j \,non\, incide \,col\, nodo \,i)}
\end{matrix}\right.

Assegnato un grafo orientato, dopo aver numerato i suoi nodi e i suoi lati, è possibile scrivere la matrice d'incidenza. Viceversa, data la matrice d'incidenza è possibile ricavarne il relativo grafo orientato.

La matrice d'incidenza è di fondamentale importanza per molti metodi di risoluzioni delle reti in quanto permette di descrivere la topologia della rete in modo abbastanza agevole.

Alla matrice d'incidenza sono associati due importanti teoremi.

Teorema 2: Il determinante di qualsiasi matrice d'incidenza (quadrata) di un albero è uguale a \pm 1.
Teorema 3: Il rango di una matrice d'incidenza di un grafo connesso con n vertici è pari a n − 1.

Matrice d'adiacenza

Consideriamo un grafo orientato con n nodi e l lati senza lati in parallelo.

La matrice d'adiacenza M è una matrice quadrata n\times n così definita:

m_{i,j}=\left\{\begin{matrix}

1 & \textrm{se\,}\left ( v_{i},v{j} \right )\in E\\ 


0 & \textrm{altrimenti}

\end{matrix}\right.

La matrice d'adiacenza è nota anche come tabella di connessione.

Distanza resistiva e indice di Kirchhoff

In questo paragrafo introduciamo i concetti principali di questo articolo: la distanza resistiva e l'indice di Kirchhoff.

Questi concetti sono relativamente recenti e si possono incontrare esclusivamente su riviste specializzate o articoli scientifici che si occupano di teoria di grafi applicate alle scienze.

A partire dall'inizio del 2000 la produzione di articoli scientifici riguardanti questi aspetti è aumentata considerevolmente, soprattutto quando si è intuito che i concetti di distanza resistiva e indice di Kirchhoff permettono di generalizzare e armonizzare molti aspetti della teoria delle reti e in generale della teoria dei grafi, legandoli ancor di più alla teoria della misura.

Prima di introdurre i due concetti, scriviamo la definizione generale di distanza fra due vertici di un grafo.

Definizione 4 (di distanza): Si definisce distanza tra due vertici, \text{d}\left ( v_{i},v_{j} \right ), la lunghezza del cammino più breve.

Il concetto di distanza resistiva esiste da molto tempo, soprattutto nell'ambito della teoria delle reti, ma non era mai stato formalizzato. Molti autori affermano che il primo articolo scientifico riguardante la formalizzazione di distanza resistiva è stato pubblicato nel 1993 da Klein e Randić nel Journal Mathematical Chemistry nell'ambito della teoria dei grafi e delle strutture chimiche.

Le due matrici che abbiamo introdotto nel paragrafo precedente giocano un ruolo fondamentale nel calcolo delle due grandezze, ma non sono le uniche. Strumenti ben più importanti permettono di definire la distanza resistiva e l'indice di Kirchhoff, in varie forme alternative, come la matrice laplaciana e la relativa pseudo-inversa Moore-Penrose.

Intuitivamente, la distanza resistiva fra un coppia di nodi di un grafo G è la resistenza effettiva vista fra la coppia di nodi della relativa rete elettrica. In altre parole, la distanza resistiva fra due nodi è la differenza di potenziale fra i due nodi stessi quando iniettiamo una corrente di 1 A nel primo nodo.

L'indice di Kirchhoff, legato anch'esso alla topologia del grafo, fornisce una misura di tutte le distanze resistive. Da questo punto di vista possiamo definirlo una sorta di aggregatore. Esistono diverse formulazioni equivalenti per definire l'indice di Kirchhoff. Noi riportiamo la seguente:

 \text{K}_{I}=\frac{1}{2}\sum_{i,j\in V}r\left ( i,j \right )

indicando con r\left ( i,j \right ) la distanza resistiva.

In tale ambito, le pubblicazioni scientifiche, oltre a formalizzare e armonizzare fra loro vari concetti elettrici e non, cercano di impostare vari metodi di calcolo e formule utili per la valutazione di queste due grandezze.

Conclusione

I libri di elettrotecnica e teoria delle reti, anche specialistici, non riportano i concetti di distanza resistiva e di indice di Kirchhoff, pertanto con questo articolo ho voluto semplicemente far conoscere ai miei ultimi 25 lettori questi due nuovi strumenti di analisi delle reti.

Lo studente più attento dovrebbe scrivere un appunto su queste questioni e ritornarci appena la propria preparazione matematica glielo permetterà. Per la maggior parte degli articoli, infatti, è necessario conoscere vari aspetti della matematica (analisi, teoria dei grafi, passeggiate aleatorie, catene di Markov, algebre di tutti i tipi e tanto altro).

Riferimenti

[1] RenzoDF, Resistenze e Simmetria 1.

[2] RenzoDF, Resistenze e Simmetria 2.

5

Commenti e note

Inserisci un commento

di ,

Ok, ora mi tornano molto meglio alcuni passaggi che prima erano poco chiari. Ora che mi hai stimolato la curiosità, appena posso andrò senz'altro a leggere gli articoli che mi hai indicato, in modo da entrare maggiormente nell'argomento! Ciao e a presto.

Rispondi

di ,

Leggi l'articolo 2 di RenzoDF (parafrafo laplaciano) e il ref 2 riportato in fondo all'articolo. Si può dimostrare che quel rapporto dipende da un bel po' di alberi :)

Rispondi

di ,

Non era mia intenzione inserire tutte le definizioni dei termini richiamati nell'articolo, comunque ho aggiunto quella di grafo connesso e un disegno esplicativo. L'albero di un grafo e' un insieme di lati collegati tali che: 1) passa per tutti i nodi del grafo e 2) non forma nessuna maglia chiusa. Diciamo che un albero esclude percorsi alternativi per raggiungere un nodo (in un albero non ci sono percorsi multipli per raggiungere un nodo). Come ho scritto nell'articolo, la matrice di incidenza e' di tipo nodi-lati. Il primo indice (i) indica l'i-esimo nodo e il secondo indice j indica il j-esimo lato (qui abbiamo una 'sorta' di abuso di notazione in quanto con j avevamo indicato il j-esimo nodo). In pratica devi numerare tutti i lati del grafo (un lato e' stato definito come la coppia di numeri (i,j) ). Non voglio inserire nessuna formula per la distanza resistiva in quanto sarei obbligato a definire la matrice laplaciana, relativi cofattori e un paio di teoremi e l'articolo diventerebbe poco fruibile sul web, a mio avviso. Comunque, cerca tra i riferimenti dell'articolo [2] di RenzoDF :).

Rispondi

di ,

Buongiorno, vorrei chiedere alcune delucidazioni: quale è la definizione usata per grafo connesso? cosa si intende esattamente per albero? nella definizione di matrice d'incidenza, con j si intende il generico lato, cioè si suppongono i lati, definiti da delle coppie ordinate, numerati da 1 a l? Nonostante le comprensibili difficoltà, puoi esporre una delle possibili definizioni di distanza resistiva, magari quella più comprensibile tenuto conto degli altri argomenti presentati? Grazie!!

Rispondi

di ,

Bello!

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.