I circuiti di un grafo orientato rivestono un ruolo fondamentale in meccanica statistica di non-equilibrio, ove i rami dei grafi rappresentano le possibili transizioni tra stati, ed in termini di circuiti e alberi massimali si costruiscono le grandezze termodinamiche macrocopiche, come le correnti stazionarie e le forzanti esterne.
Per questo ero in cerca, tra libri e semplici calcoli, di qualche interessante relazione algebrica per caratterizzare i circuiti.
La matrice di incidenza e la laplaciana
Come noto, in teoria dei grafi sono definite molte utili matrici. Forse la più fondamentale è la matrice di incidenza, che per ogni ramo (
edge)
e ed ogni vertice
i associa un +1 se il ramo entra nel vertice, -1 se ne esce e 0 se non lo tocca*:
Se |E| è il numero di rami e |V| il numero dei vertici, la matrice di incidenza è una matrice |E|X|V|. Se se ne prende il prodotto matriciale per la matrice trasposta si ottiene la matrice |V|X|V| detta laplaciana (di cui lap(l)aciano è sicuramente un cultore):
ove d_j è il grado del sito, pari al numero di rami che vi afferiscono. Ma non è di questa che voglio parlare.
La matrice di "confluenza"
Molto più interessante per i miei scopi è la matrice |E|X|E| che si ottiene prendendo il prodotto inverso
che ha 2 sulla diagonale, +1 se i due rami confluiscono o provengono dallo stesso vertice e -1 se fluiscono attraverso i. Per questo battezzo la parte non diagonale di DD^T la matrice di "confluenza" F non avendone trovato menzione in letteratura (e lancio l’appello…). Quesa matrice si può intendere come un endomorfismo lineare in uno spazio vettoriale. Ogni sottografo o grafo che si possa ottenere considerando anche più ripetizioni dello stesso ramo orientato si può rappresentare come un vettore sul gruppo dei numeri interi. Esempi espliciti sono riportati più sotto.
Disclaimer: Tutte le affermazioni da qua in poi sono congetturali: nessuna dimostrazione, probabili toppe e pezze a venire.
L’operatore F sembra avere interessanti proprietà.
1) Dato un grafo non orientato G, si ha una rappresentazione della matrice di confluenza G per ogni possibile orientazione arbitraria dei rami del grafo. Congetturiamo (e dev’essere molto semplice dimostrare) che le congetture che seguono siano indipendenti dall’orientazione scelta.
2) F è invertibile (e quindi è un automorfismo) se (non saprei il "solo se") il grafo è privo di foglie ed è ridotto, ovverosia sono eliminati tutti i vertici cui confluiscono solo uno o due rami. In sostanza, partendo da un grafo qualsiasi facciamo la seguente "ristrutturazione":
fig. 1
Questo non deve risultare scandaloso, ha senso fisico: nello stato stazionario tra una foglia e il resto del sistema vige una condizione di bilancio dettagliato, che è locale. Rimuovere la foglia non modifica la termodinamica del resto del grafo. Sempre nello stato stazionario, la riduzione di due spigoli consiste nel sommare le relative "differenze di potenziale", mentre la corrente che fluisce, e per la quale vigono leggi di conservazione ad ogni vertice, è la stessa: ancora la termodinamica del resto del grafo rimane invariata. Per cui considero solo questo tipo di grafi.
3) Le proprietà interessanti di F riguardano i circuiti. E’ abbastanza semplice convincersi che D^TD = 2I + F si annulla in corrispondenza di tutti i (quasi)circuiti orientati, come questo:
fig. 2
Questi notoriamente formano un sottospazio lineare chiuso nello spazio dei sottografi, in quanto combinazioni lineari di circuiti orientati sono ancora circuiti orientati. Infatti sono tutti autovalori relativi all’autovalore -2 dell’operatore F. Per esempio il grafo in figura è scomponibile in 4 circuiti fondamentali (essendo planare, si può scegliere come base i circuiti che tagliano porzioni finite di piano). In verità questa non è una proprietà di F, ma della matrice di incidenza D stessa.
4) Più interessante è cercare di capire che cosa combina F su un qualsiasi grafo, andando alla ricerca degli autovettori rimanenti. Per questo ho soltanto l’analisi spiccia di un paio di esempi. Considero il grafo planare (ma non k-regolare, il che dà problemi)
fig 3
La matrice di confluenza è (scusate il segno meno, non avevo voglia di cambiare tutte le entries)
i cui autovalori sono -2,-2,-2,-2,-2,3,3,3,1 (tranquilli, non li ho calcolati a mano). Si notano con il segno negativo i cinque autovalori relativi all’autospazio di dimensione 5 dei circuiti, e due autospazi relativi ad autovalori positivi. La somma degli autovalori è nulla, essendo pari alla traccia che è un invariante.
5) Trovare gli autovettori di una matrice, si sa, è una bella rottura. Sarebbe bello avere una ricetta meccanica per individuare i sottografi che costituiscono gli autovettori relativi agli autovalori positivi, ed una espressione esplicita per il loro relativo autovalore in termini di loro proprietà "topologiche" come connettività, grado etc. Una prima ipotesi è quella di cercare tra i cocicli, insiemi minimali di rami che dividono il grafo in due sottografi disgiunti, in qualche modo duali ai circuiti, ma purtroppo non funziona (ma il "purtroppo" in matematica non esiste: le cose sono o non sono, e non c’è da dispiacersi altrimenti). Per i circuiti c’è un tale trucco, ed è abbastanza semplice. Si può per esempio partire da un albero, aggiungere una corda e buttare via quello che non serve. Per i sottospazi ortogonali, so’ cazzi. Ma sto diventando abbastanza bravo a trovare gli autovettori per via grafica, con un po’ di fantasia.
Prendo due vertici opposti e disegno tutti i percorsi dal primo al secondo che contengono due rami, conteggiando due volte un percorso diretto. Faccio in modo di toccare tutti i vertici del grafo. Se i due vertici sono collegati direttamente, ottengo un autovettore relativo all’autovalore 1, altrimenti ne avrete uno relativo all’autovalore 3:

fig 4
fig 5
Purtroppo la stessa costruzione non funziona benissimo per altri due vertici a caso; ma ci dev’essere qualcosa sotto.
6) Se il grafo è completo, la ricetta qua sopra è esatta e lo spazio ortogonale ha rango |V| - rk(F + 2I). Interessante in questo caso è andare ad analizzare gli operatori di proiezione, ma sarà fatto in un’altra puntata.
7) Può essere interessante domandarsi se esiste una matrice che sta ai cocicli come F sta ai cicli.
8) L’operatore F agisce in uno spazio vettoriale definito su un gruppo, non su un corpo. La cosa non dà problemi perché F ha solo autovalori interi, e quindi ogni vettore si può scrivere come combinazione lineare intera degli autovettori di F. L’analisi dello spettro di questo operatore permette di dare una decomposizione esplicita di OGNI grafo (di quelli che consideriamo noi) in termini di circuiti e… un’entità ancora abbastanza informe.
* Il motivo per cui mi sono addentrato nei risvolti della matrice di incidenza è perché questa permette di transitare da una rappresentazione in rami ad una rappresentazione in vertici del grafo; la matrice di incidenza in un certo senso è l’operatore che calcola il "bordo" di un insieme di vertici, e si può definire analogalmente un operatore di "cobordo". I circuiti orientati sono grafi senza bordo. Mi interessano molto le analogie tra teoria dei grafi e la teoria di Hodge-deRham, di cui parleremo un’altra volta. Segno solo un appunto. Le grandezze termodinamiche (e.g. le forze microscopiche A) che ci interessano sono antisimmetriche per inversione del senso dei rami de grafo. Le due possibili rappresentazioni che ne possiamo dare sono come un vettore nello spazio lineare dei rami del grafo, o come matrice antisimmetrica in rappresentazione "vertici":

Questo dualismo tra un vettore ed una forma antisimmetrica ricorda il duale di Hodge, che per esempio associa al differenziale esterno della 2-forma "campo magnetico" (e quindi ad una 3-forma) il vettore "rotore del campo magnetico". Notare che D si comporta come un operatore di Dirac, dato che DD^T = laplaciano.
ERRATA. Niente di sostanziale. Il grafo in fig 3 non corrisponde alla matrice F sotto riportata; bisogna bensì collegare con il ramo curvilineo gli altri due vertici opporti.