Back Cheeger-állandó Hungarian Константа Чигера (теория графов) Russian Konstantja Çiger (teoria e grafeve) Albanian Стала Чіґера (теорія графів) Ukrainian

Cheeger constant (graph theory)

This article is about the Cheeger constant in graph theory. For a different use in Riemannian geometry, see Cheeger constant.
Here, a subset A of the graph G (denoted red) has 3 vertices, and 3 edges leaving its subset (denoted green and dashed). The number of edges leaving the subset divided by the size of the subset is denoted , which here is .

The Cheeger constant is the minimum of all subsets of the graph G which are not empty and whose size is less than or equal to half the size of G. For this graph G, this subset A has the smallest value , and therefore 1 is the Cheeger constant of G

In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.

The Cheeger constant is named after the mathematician Jeff Cheeger.

Rich TVX News Network Site

Rich TVX News Network Info

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search