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-24 17:37:11 UTC</tt>.

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

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

: The original revision id was <tt>359782165</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 37:

A graph is [[http://en.wikipedia.org/wiki/Planar_graph|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", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http://mathworld.wolfram.com/GraphGenus.html|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. Moreover, such an embedding can be converted into a planar diagram by allowing ~~depicting~~ some of the ~~vetices~~ in more than one place, on the edge of the diagram. 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. For small ~~enough~~ scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing the depiction of some of the vertices in more than one place, on the edge of the diagram. 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. For very small scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.

If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph.

Line 119:

A graph is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow">planar</a> 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;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphGenus.html" 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.

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing ~~depicting~~ some of the ~~vetices~~ in more than one place, on the edge of the diagram. 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. For small ~~enough~~ scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> can manage to finish computing after an acceptable amount of time.

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing the depiction of some of the vertices in more than one place, on the edge of the diagram. 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. For very small scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> can manage to finish computing after an acceptable amount of time.

If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph.

@@ 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-24 17:37:11 UTC</tt>.<br>
+: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-24 17:39:36 UTC</tt>.<br>
-: The original revision id was <tt>359781869</tt>.<br>
+: The original revision id was <tt>359782165</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 37: / Line 37: @@
 A graph is [[http://en.wikipedia.org/wiki/Planar_graph|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", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http://mathworld.wolfram.com/GraphGenus.html|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. Moreover, such an embedding can be converted into a planar diagram by allowing depicting some of the vetices in more than one place, on the edge of the diagram. 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. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.
+Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing the depiction of some of the vertices in more than one place, on the edge of the diagram. 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. For very small scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.
 If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph.
@@ Line 119: / Line 119: @@
   A graph is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow"&gt;planar&lt;/a&gt; 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 &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow"&gt;compact&lt;/a&gt;&lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow"&gt;orientable&lt;/a&gt; &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow"&gt;surface&lt;/a&gt; with &amp;quot;donut holes&amp;quot;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of &lt;a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphGenus.html" rel="nofollow"&gt;genus&lt;/a&gt; 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.&lt;br /&gt;
 &lt;br /&gt;
-Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing depicting some of the vetices in more than one place, on the edge of the diagram. Unfortunately, the problem of determining the genus and finding such an embedding is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow"&gt;NP-complete&lt;/a&gt;. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of &lt;a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow"&gt;SAGE&lt;/a&gt; can manage to finish computing after an acceptable amount of time.&lt;br /&gt;
+Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Moreover, such an embedding can be converted into a planar diagram by allowing the depiction of some of the vertices in more than one place, on the edge of the diagram. Unfortunately, the problem of determining the genus and finding such an embedding is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow"&gt;NP-complete&lt;/a&gt;. However, finding bounds on the genus is a much easier problem. For very small scales, the genus routine of &lt;a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow"&gt;SAGE&lt;/a&gt; can manage to finish computing after an acceptable amount of time.&lt;br /&gt;
 &lt;br /&gt;
 If the genus is g, the graph can also be drawn on any surface of genus greater than g; one way to accomplish that, but not the only way, is simply not to use more than g of the holes--that is, not to draw an edge passing through it. In fact, beyond a certain point you would not be able to use all of the holes and would have to leave some without edges drawn through them. The maximum number of holes, all of which can actually be used by having an edge pass through them, is called the maximal genus an is another invariant of the graph.&lt;br /&gt;