Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 358534393 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 358548817 - 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- | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-19 01:08:18 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>358548817</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 28: | Line 28: | ||
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 vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity. | 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 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. | ||
=The Genus= | |||
A graph is //planar// if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes". If a surface has g holes, it is of [[http://en.wikipedia.org/wiki/Genus_(mathematics)|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. | |||
Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem.</pre></div> | |||
<h4>Original HTML content:</h4> | <h4>Original HTML content:</h4> | ||
<div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Graph-theoretic properties of scales</title></head><body><!-- ws:start:WikiTextTocRule: | <div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Graph-theoretic properties of scales</title></head><body><!-- ws:start:WikiTextTocRule:10:&lt;img id=&quot;wikitext@@toc@@flat&quot; class=&quot;WikiMedia WikiMediaTocFlat&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/flat?w=100&amp;h=16&quot;/&gt; --><!-- ws:end:WikiTextTocRule:10 --><!-- ws:start:WikiTextTocRule:11: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:11 --><!-- ws:start:WikiTextTocRule:12: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:12 --><!-- ws:start:WikiTextTocRule:13: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:13 --><!-- ws:start:WikiTextTocRule:14: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:14 --><!-- ws:start:WikiTextTocRule:15: --> | <a href="#The Genus">The Genus</a><!-- ws:end:WikiTextTocRule:15 --><!-- ws:start:WikiTextTocRule:16: --> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:16 --><br /> | ||
<!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Graph of a scale"></a><!-- ws:end:WikiTextHeadingRule:0 -->Graph of a scale</h1> | <!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Graph of a scale"></a><!-- ws:end:WikiTextHeadingRule:0 -->Graph of a scale</h1> | ||
Given a <a class="wiki_link" href="/periodic%20scale">periodic scale</a>, meaning a scale whose steps repeat, and assuming some multiple of the period is an interval of equivalence (usually this means the octave, ie interval of 2, which from now on we will assume is the interval of equivalence) then we may reduce the scale to a finite set S of pitch classes. This relates to the usual way of defining a scale, as used for instance by <a class="wiki_link" href="/Scala">Scala</a>. If we say 1-9/8-5/4-4/3-3/2-5/3-15/8-2 is a scale, we mean that each step of it represents a class of octave-equivalent pitches, so that &quot;5/4&quot; represents {...5/8, 5/4, 5/2, 5, 10 ...} and both &quot;1&quot; and &quot;2&quot; mean {...1/4, 1/2, 1, 2, 4...}. Suppose we have a finite set of pitches C strictly within the octave, so that s∊C entails 1 &lt; s &lt; 2, and suppose if s∊C then also 2/s∊C. The elements of C represent consonant pitch classes exclusive of the unison-octave class. <br /> | Given a <a class="wiki_link" href="/periodic%20scale">periodic scale</a>, meaning a scale whose steps repeat, and assuming some multiple of the period is an interval of equivalence (usually this means the octave, ie interval of 2, which from now on we will assume is the interval of equivalence) then we may reduce the scale to a finite set S of pitch classes. This relates to the usual way of defining a scale, as used for instance by <a class="wiki_link" href="/Scala">Scala</a>. If we say 1-9/8-5/4-4/3-3/2-5/3-15/8-2 is a scale, we mean that each step of it represents a class of octave-equivalent pitches, so that &quot;5/4&quot; represents {...5/8, 5/4, 5/2, 5, 10 ...} and both &quot;1&quot; and &quot;2&quot; mean {...1/4, 1/2, 1, 2, 4...}. Suppose we have a finite set of pitches C strictly within the octave, so that s∊C entails 1 &lt; s &lt; 2, and suppose if s∊C then also 2/s∊C. The elements of C represent consonant pitch classes exclusive of the unison-octave class. <br /> | ||
| Line 52: | Line 57: | ||
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 the <em>algebraic connectivity</em>. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.<br /> | 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 the <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.<br /> | ||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:8:&lt;h1&gt; --><h1 id="toc4"><a name="The Genus"></a><!-- ws:end:WikiTextHeadingRule:8 -->The Genus</h1> | |||
A graph is <em>planar</em> if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow">compact</a><a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow">orientable</a> <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow">surface</a> with &quot;donut holes&quot;. If a surface has g holes, it is of <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Genus_(mathematics)" rel="nofollow">genus</a> g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. <br /> | |||
<br /> | |||
Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow">NP-complete</a>. However, finding bounds on the genus is a much easier problem.</body></html></pre></div> | |||