Conduttanza (teoria dei grafi)

In teoria dei grafi, la conduttanza è una misura utilizzata per quantificare la qualità di un taglio e l'espansione dei grafi. Essa indica quanto un grafo sia "ben collegato" o, in alternativa, quanto presenti strozzature (bottleneck) che separano il grafo in sottostrutture scarsamente interconnesse. La conduttanza trova applicazioni in informatica teorica, nell'analisi delle reti e nello studio delle catene di Markov, in quanto fornisce indizi sulla velocità di convergenza dei processi stocastici ed è strettamente legata alle proprietà spettrali dei grafi.

Definizione

Sia $G$ un grafo $d$ -regolare non diretto e con archi non pesati. La conduttanza $φ (G)$ è definita come $φ (G) = h (G) / d$ , dove $h (G)$ è la costante di Cheeger.

Più in generale, sia $G = ⟨ V, E ⟩$ un grafo diretto con pesi reali $a_{i j} \geq 0$ su ciascun arco $i j \in E$ . Sia $S \subseteq V$ in qualunque sottinsieme di vertici. La conduttanza $φ (S)$ del taglio $(S, \bar{S})$ è definita come

φ (S) = \frac{a (S, \bar{S})}{\min (v o l (S), v o l (\bar{S}))},

dove

a (S, T) = \sum_{i \in S} \sum_{j \in T} a_{i j},

e quindi $a (S, \bar{S})$ è il peso totale degli archi attraversati dal taglio $(S, \bar{S})$ e

v o l (S) = a (S, V) = \sum_{i \in S} \sum_{j \in V} a_{i j}

è il volume di $S$ , ovvero, il peso totale di tutti gli archi che partono da $S$ . Se $v o l (S)$ è uguale a $0$ , allora anche $a (S, \bar{S})$ è uguale $0$ e $φ (S)$ vale $1$ per definizione.

La conduttanza $φ (G)$ del grafo $G$ è quindi definita come la minima conduttanza tra tutti i possibili tagli:

φ (G) = \min_{S \subseteq V} φ (S) .

In modo equivalente, la conduttanza soddisfa:

φ (G) = \min {\frac{a (S, \bar{S})}{v o l (S)} : v o l (S) \leq \frac{v o l (V)}{2}} .

Bibliografia

Voci correlate

Teoria della percolazione

Template:Portale

Conduttanza (teoria dei grafi)

Definizione

Bibliografia

Voci correlate

Menu di navigazione

Ricerca