 |
This Conductance (graph) is in need of attention from an expert on the subject. Please help recruit one or improve this article yourself. See the for details. Please consider using {{Expert-subject}} to associate this request with a WikiProject |
In graph theory, a branch of mathematics, conductance of a graph <math>G=(V,E)</math> measures how "well-knit" the graph is. The conductance of a cut <math>(S, \bar S)</math> in a graph is defined as:
- <math>\varphi(S) = \frac{\sum_{i \in S, j \not\in S}a_{ij}}{\min(a(S), a(\bar S))}</math>
- <math>a(S) = \sum_{i \in S} \sum_{j \in V} a_{ij}</math>
- <math>a_{ij}</math> are entries of the adjacency matrix for graph <math>G</math>.
The conductance of the whole graph is the minimum conductance over all the possible cuts:
- <math>\phi(G) = \min_{S \subseteq V}\varphi(S).\,</math>
