Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 358534207 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 358534267 - Original comment: ** |
||
| Line 1: | Line 1: | ||
<h2>IMPORTED REVISION FROM WIKISPACES</h2> | <h2>IMPORTED REVISION FROM WIKISPACES</h2> | ||
This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | 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-18 21: | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-18 21:40:11 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>358534267</tt>.<br> | ||
: The revision comment was: <tt></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> | 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= | =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 // | 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 yhe //algebraic connectivity//. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity. | ||
The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.</pre></div> | The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.</pre></div> | ||
| Line 50: | Line 50: | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:6:&lt;h1&gt; --><h1 id="toc3"><a name="The Laplace Spectrum"></a><!-- ws:end:WikiTextHeadingRule:6 -->The Laplace Spectrum</h1> | <!-- ws:start:WikiTextHeadingRule:6:&lt;h1&gt; --><h1 id="toc3"><a name="The Laplace Spectrum"></a><!-- ws:end:WikiTextHeadingRule:6 -->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 <em>Laplace matrix</em> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em> | 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 <em>Laplace matrix</em> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em>Laplace spectrum</em>. 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 yhe <em>algebraic connectivity</em>. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.<br /> | ||
<br /> | <br /> | ||
The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.</body></html></pre></div> | The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.</body></html></pre></div> | ||