Graph-theoretic properties of scales: Difference between revisions

Line 1:

<h2>IMPORTED REVISION FROM WIKISPACES</h2>

This is an imported revision from Wikispaces. The revision metadata is included below for reference:

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:03:57 UTC</tt>.

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:17:38 UTC</tt>.

: The original revision id was <tt>~~358748103~~</tt>.

: The original revision id was <tt>358752181</tt>.

: The revision comment was: <tt></tt>

The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.

Line 26:

=The Laplace Spectrum=

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices.

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ > (π/V)^2 ε.

We can also relate the diameter d to the algebraic connectivity, since 4/Vλ ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.

Line 67:

<h1 id="toc3"><a name="The Laplace Spectrum"></a>The Laplace Spectrum</h1>

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the Laplace matrix of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the Laplace spectrum. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the algebraic connectivity. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices.

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the Laplace matrix of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the Laplace spectrum. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the algebraic connectivity. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ &gt; (π/V)^2 ε.

We can also relate the diameter d to the algebraic connectivity, since 4/Vλ ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.

@@ Line 1: / Line 1: @@
 <h2>IMPORTED REVISION FROM WIKISPACES</h2>
 This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br>
-: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:03:57 UTC</tt>.<br>
+: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:17:38 UTC</tt>.<br>
-: The original revision id was <tt>358748103</tt>.<br>
+: The original revision id was <tt>358752181</tt>.<br>
 : The revision comment was: <tt></tt><br>
 The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br>
@@ Line 26: / Line 26: @@
 =The Laplace Spectrum=
-If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices.
+If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ &gt; (π/V)^2 ε.
 We can also relate the diameter d to the algebraic connectivity, since 4/Vλ ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.
@@ Line 67: / Line 67: @@
 &lt;br /&gt;
 &lt;!-- ws:start:WikiTextHeadingRule:6:&amp;lt;h1&amp;gt; --&gt;&lt;h1 id="toc3"&gt;&lt;a name="The Laplace Spectrum"&gt;&lt;/a&gt;&lt;!-- ws:end:WikiTextHeadingRule:6 --&gt;The Laplace Spectrum&lt;/h1&gt;
-If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the &lt;em&gt;Laplace matrix&lt;/em&gt; of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the &lt;em&gt;Laplace spectrum&lt;/em&gt;. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the &lt;em&gt;algebraic connectivity&lt;/em&gt;. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices. &lt;br /&gt;
+If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the &lt;em&gt;Laplace matrix&lt;/em&gt; of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the &lt;em&gt;Laplace spectrum&lt;/em&gt;. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the &lt;em&gt;algebraic connectivity&lt;/em&gt;. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices; consequently λ &amp;gt; (π/V)^2 ε.&lt;br /&gt;
 &lt;br /&gt;
 We can also relate the diameter d to the algebraic connectivity, since 4/Vλ ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.&lt;br /&gt;