Quelle aboutMetrics.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/hap/www/SideLinks/About/aboutMetrics.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta http-equiv="content-type"
content="text/html; charset=ISO-8859-1">
  <title>AboutHap</title>
</head>
<body
style="color: rgb(0, 0, 153); background-color: rgb(204, 255, 255);"
link="#000066" vlink="#000066" alink="#000066">
<br>
<table
style="text-align: left; margin-left: auto; margin-right: auto; color: rgb(0, 0, 102);"
border="0" cellpadding="20" cellspacing="10">
  <tbody>
    <tr align="center">
      <th style="vertical-align: top;">
      <table style="width: 100%; text-align: left;" cellpadding="2"
cellspacing="2">
        <tbody>
          <tr>
            <td style="vertical-align: top;"><a
href="aboutPersistent.html"><small style="color: rgb(0, 0, 102);">Previous</small></a><br>
            </td>
            <td
style="text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><big><span
style="font-weight: bold;">About HAP: Metric Spaces<br>
            </span></big></td>
            <td style="text-align: right; vertical-align: top;"><a
href="aboutTDA.html"><small style="color: rgb(0, 0, 102);">next</small></a><br>
            </td>
          </tr>
        </tbody>
      </table>
      <big><span style="font-weight: bold;"></span></big><br>
      </th>
    </tr>
    <tr align="center">
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big><span
style="font-weight: bold;">1. Metrics on Vectors</span></big><br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">The

      <a href="data.txt">data file</a> contains a list L of
400 vectorsi in <span style="font-weight: bold;">R</span><sup>3</sup>.
The following commands produce the 400×400 symmetric matrix whose
(i,j)-entry is the Manhattan distance between L[i] and L[j].
(Alternative choices of metric include the Euclidean squared metric and
Hamming metric.)<br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
ReadPackage("hap","www/SideLinks/About/data.txt");
#This
reads
in
the
list
L<br>
gap> S:=VectorsToSymmetricMatrix(L,ManhattanMetric);;<br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following command uses GraphViz software to display the graph G(S,t) on
400
vertices with edge between i and j precisely when <br>
      <br>
      <div style="text-align: center;">S[i][j] <= tM / 100 <br>
      </div>
      <br>
where M is the maximum value of the entries in S. Thus the threshold t
should be chosen in the range from 0 to 100. We choose t=8. We also
choose to give the first 200 vertices a common colour distinct from the
remaining vertices. The display shows that the first 200 vertices lie
in one path-component of G(S,8), and the remaining 200 vertices lie in
a second path-component. Each path-component "has the shape" of a
cylinder
or annulus. <br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
SymmetricMatDisplay(S,8,
[
[1..200],
[201..400]
]
);<br>
      <br>
      <div style="text-align: center;"><img
style="width: 600px; height: 284px;" alt="" src="colourgraph.gif"><br>
      </div>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands construct the graph G=G(S,10) and then display it. <br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
M:=Maximum(Maximum(S));;

      <br>
gap> G:=SymmetricMatrixToGraph(S,10*M/100); <br>
Graph on 400 vertices.<br>
      <br>
gap>
GraphDisplay(G);<br>
      <div style="text-align: center;"><img
style="width: 384px; height: 347px;" alt="" src="400graph.gif"><br>
      </div>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">We
use the term  <span style="font-style: italic;">simplicial nerve</span>
of G to mean the simplicial complex
NG which has the same vertices and edges as G; a collection of vertices
is a simplex in NG if and only if each pair of edges in the collection
is connected by an edge in G. The following commands determine a
subgraph H in G such that the simplicial nerves NG and NH are homotopy
equivalent. The commands replace G by H and then display the subgraph. </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
ContractGraph(G);;<br>
gap> G;<br>
Graph on 248 vertices.<br>
      <br>
gap> GraphDisplay(G);<br>
      <div style="text-align: center;"><img
style="width: 384px; height: 178px;" alt=""
src="400contractedgraph.gif"><br>
      </div>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands illustrate <span style="font-weight: bold;">two</span>
methods for calculating the low-dimensional homology of NG. The second
method is more efficient in degrees 0 and 1 but has yet to be properly
implemented in higher degrees.<br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
#Method
One<br>
gap> NG:=SimplicialNerveOfGraph(G,3);; <br>
gap> NG:=SimplicialComplexToRegularCWComplex(NG);<br>
Regular CW-complex of dimension 3<br>
gap> Homology(NG,0);<br>
[ 0, 0 ]<br>
gap> Homology(NG,1);<br>
[ 0, 0 ]<br>
      <br>
gap> #Method Two<br>
gap> C:=RipsChainComplex(G,1);<br>
Sparse chain complex of length 2 in characteristic 0 . <br>
      <br>
gap> Bettinumbers(C,0);<br>
2<br>
gap> Bettinumbers(C,1);<br>
2<br>
      </td>
    </tr>
    <tr align="center">
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big><span
style="font-weight: bold;">2. Metrics on Permutations</span></big><br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">There
are
a
number of standard metrics d(x,y) on permutations x, y <sub> </sub>such
as
the Kendall metric (=number of neighbouring
transpositions (i,i+1) needed to express x*y^-1), the Cayley metric (=
number of transpositions (i,j) needed to express x*y^-1) and the
Hamming metric (= #{ i :  x*y^-1(i) differs from i  } ). The
following commands display the Sylow 2-subgroup of S<sub>10</sub> with
respect to the Cayley metric.<br>
      </td>
    </tr>
    <tr>
      <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
G:=SymmetricGroup(10);;

      <br>
gap> P:=SylowSubgroup(G,2);;<br>
gap> P:=Elements(P);;<br>
gap> S:=NullMat(Size(P),Size(P));;<br>
gap> for i in [1..Size(P)] do<br>
> for j in [1..Size(P)] do<br>
> S[i][j]:=CayleyMetric(P[i],P[j],10);<br>
> od;od;<br>
gap> SymmetricMatDisplay(S,50);<br>
      <div style="text-align: center;"><br>
      <img style="width: 355px; height: 384px;" alt=""
src="sylowS10.gif"><br>
      <div style="text-align: left;"><br>
gap> SymmetricMatDisplay(S,15);<br>
      <br>
      <div style="text-align: center;"><img
style="width: 355px; height: 384px;" alt="" src="sylowS1015.gif"><br>
      </div>
      </div>
      </div>
      </td>
    </tr>
    <tr>
      <td style="vertical-align: top;">
      <table
style="margin-left: auto; margin-right: auto; width: 100%; text-align: left;"
border="0" cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="vertical-align: top;"><a
style="color: rgb(0, 0, 102);" href="aboutPersistent.html">Previous
Page</a><br>
            </td>
            <td style="text-align: center; vertical-align: top;"><a
href="aboutContents.html"><span style="color: rgb(0, 0, 102);">Contents</span></a><br>
            </td>
            <td style="text-align: right; vertical-align: top;"><a
href="aboutTDA.html"><span style="color: rgb(0, 0, 102);">Next
page</span><br>
            </a> </td>
          </tr>
        </tbody>
      </table>
      <a href="aboutTopology.html"><br>
      </a> </td>
    </tr>
  </tbody>
</table>
<br>
<br>
</body>
</html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.11 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.