\inline \Delta=(d_{ij}), di dimensione n x n, costruita come segue: d_{ii} è il grado del nodo i,d_{ij}=-1 se i e j sono connessi,d_{ij}=0 se i e j non sono connessi.La cosa interessante è che il Laplaciano di un grafo ha alcune proprietà in comune col Laplaciano su un aperto di
\inline \mathbb R^d. Ad esempio, le soluzioni dell'equazione\Delta v=0sono tutte e solo le funzioni v che sono costanti sulle componenti connesse del grafo. Una direzione è facile da capire: se v è costante (diciamo di valore 1) su una componente connessa degl grafo, e 0 altrimenti, allora
\inline \Delta v ha per ogni componente un contributo positivo pari al grado del nodo corrispondente e un contributo negativo per ogni nodo con cui è collegata: quindi tutto si semplifica dando 0. Divertente, no?Un altro bel teorema per il Laplaciano di un grafo è il Teorema di Kirchhoff sul numero degli spanning trees. Mi chiedo se anche questo abbia un corrispettivo per il Laplaciano di un aperto.
8 commenti:
tieni conto che ci sono tre o quattro diversi concetti di "laplaciano" di un grafo. questo usato da te è quello classico, negli ultimi anni è diventato parecchio famoso quello introdotto da fan chung, perché (pur meno intuitivo) e molto piú flessibile, permette di formulare asserti ristretti a classi di grafi molto piú generali e permette di caratterizzare molte piú proprietà.
nell'articolo di von luxburg che ti ho segnalato mesi fa ci sono ulteriori generalizzazioni del laplaciano. nel libro di fan chung e negli articoli di mohar ci sono varie relazioni (per esempio legate a problemi isoperimetrici) tra laplaciano su un grafo e su una varietà.
conosci l'articolo si Schnakenberg su grafi e termodinamica lontano dall'equilibiro, in cui si identificano gli spanning trees con lo stato stazionario di una master equation e i circuiti con le forze macroscopiche? volevo scrivere sul mio blog alcune speculazioni a riguardo, magari ti possono interessare
@delio: sul rapporto fra Laplaciano di un grafo e varietà ci sarebbe anche da leggere il libro di Soardi (che comunque ti consiglio: è citato nella mia tesi). Io ci sono arrivato leggiucchiadomi gli articoli di Atay: ma lo sai che mi piace veramente quello che fa? Penso che quello che interessa molto da queste parti sia la teoria spettrale dei grafi; magari se hai una o due review sull'argomento e me le mandi ti sono grato.
@tomate: non conosco l'articolo, ma suona 1) molto fisico e 2) altrettanto interessante. Mi mandi un link che mi piacerebbe dargli un'occhiate?
D'altra parte Kirchhoff era un fisico.
L'articolo è piuttosto vecchio (qui) ma l'argomento è tornato in voga recentemente per cui è facile che ci sia qualche cosa di più recente. Se non puoi accedere alle riviste non ho problemi a mandartelo (ma questo messaggio si augodistruggerà).
Io ci ho dedicato un capitolo della mia (troppo lunga) tesi di laurea.
Il concetto è che i vertici del grafo vengono identificati con stati in uno spazio delle fasi e gli spigoli con possibili transizioni tra stati, ognuno con una propria probabilità di transizione per unità di tempo. I flussi di probabilità sono descritti da una legge di conservazione (master equation). Si identiicano poi correnti e forze termodinamiche e un concetto di entropia. Se il sistema è ergodico c'è un unico stato stazionario di non-equilibrio (produzione di entropia nonnulla) e questo ha un'espressione in termini di alberi.
La cosa interessante è che mentre gli stati stazionari di equilibrio in fisica vengono spesso descritti con una misura in uno spazio dei cammini (in quantum field theory e in meccanica statistica), uno stato di non-equilibrio sembra caratterizzato da una misura in uno spazio degli alberi, che è qualcosa di ben più complesso. In un ipotetico limite al continuo mi viene da immaginare che questo diventi un integrale su cammini in uno spazio dei cammini... qualcosa di cardinalità 2^2^continuo... ma sto parlando a vanvera.
tomate, suona come una specie di random walk su un grafo. è una pura assonanza o è davvero lì che si va a finire?
stefano: direttamente dalla pagina di mohar, ecco a te il suo bel survey. conciso e comprensibile e incuriosente, come ogni survey dovrebbe essere.
i random walk richiedono l'equiprobabilità delle transizioni in tutte le direzioni, ma possono avere una memoria lunga, mentre qui si parla di generici processi di markov ergodici - insomma la controparte discreta alle equazioni di diffusione. e' curioso che in meccanica statistica si parli di diffusioni e teoria dei network, in matematica si parli di diffusioni sui network ma sembra di parlare di due cose diverse, se non altro in lingue diverse. sarei veramente curioso di capire se è una pura coincidenza.
ho dato uno sguardo allo Schnackenberg: in effetti è sostanzialmente un random walk su un grafo pesato (per delio: più o meno quello che fanno i tubinghesi), dove l'autore calcola delle relazioni interessanti fra la struttura del grafo e le soluzioni stazionarie.
Comunque è bello! Grazie per la segnalazione!
e allora, già che ci siamo, segnalo anche questo bel libriccino di doyle e snell:
Random Walks and Electrical Networks
Posta un commento