Conductance (graph)

From Wikipedia, the free encyclopedia

 This article requires authentication or verification by an expert.
Please assist in recruiting an expert or improve this article yourself. See the talk page for details. This article has been tagged since May 2008.

In graph theory, a branch of mathematics, conductance of a graph G = (V,E) measures how "well-knit" the graph is. The conductance of a cut (S, \bar S) in a graph is defined as:

  • \varphi(S) = \frac{\sum_{i \in S, j \not\in S}a_{ij}}{\min(a(S), a(\bar S))}


  • a(S) = \sum_{i \in S} \sum_{j \in V} a_{ij}


The conductance of the whole graph is the minimum conductance over all the possible cuts:

\phi(G) = \min_{S \subseteq V}\varphi(S).\,

[edit] References