Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/agt/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 31.11.2022 mit Größe 14 kB image not shown  

Quelle  chap3.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/agt/doc/chap3.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (AGT) - Chapter 3: Spectra of graphs</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap2.html">[Previous Chapter]</a>    <a href="chap4.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X7A25E43B7F2F7119" name="X7A25E43B7F2F7119"></a></p>
<div class="ChapSects"><a href="chap3.html#X7A25E43B7F2F7119">3 <span class="Heading">Spectra of graphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X811034AF832F8BE9">3.1 <span class="Heading">Eigenvalues of regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X79AA0FEA8307F6C1">3.1-1 LeastEigenvalueInterval</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7A778BA880361164">3.1-2 SecondEigenvalueInterval</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X86F1FC147DB0DEE5">3.1-3 LeastEigenvalueFromSRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8778AC2E87B8DAD6">3.1-4 SecondEigenvalueFromSRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80A9778F8468A4DD">3.1-5 LeastEigenvalueMultiplicity</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8740396B80617B47">3.1-6 SecondEigenvalueMultiplicity</a></span>
</div></div>
</div>

<h3>3 <span class="Heading">Spectra of graphs</span></h3>

<p>In this chapter we give methods for investigating the eigenvalues of a graph.</p>

<p>Let <span class="SimpleMath">Γ</span> be a graph of order <span class="SimpleMath">v</span>. The <em>adjacency matrix</em> of <span class="SimpleMath">Γ</span>, <span class="SimpleMath">A(Γ)</span>, is the <span class="SimpleMath">v× v</span> matrix indexed by <span class="SimpleMath">V(Γ)</span> such that <span class="SimpleMath">A(Γ)_xy=1</span> if <span class="SimpleMath">xy∈ E(Γ)</span>, and <span class="SimpleMath">A(Γ)_xy=0</span> otherwise.</p>

<p>The <em>spectrum</em> of <span class="SimpleMath">Γ</span>, <span class="SimpleMath">Spec(Γ)</span>, is the multiset of eigenvalues of its adjacency matrix, and an <em>eigenvalue of </em><span class="SimpleMath">Γ</span> is a member of <span class="SimpleMath">Spec(Γ)</span>. The <em>multiplicity</em> of an eigenvalue <span class="SimpleMath">α</span> of <span class="SimpleMath">Γ</span> is the number of times <span class="SimpleMath">α</span> appears in <span class="SimpleMath">Spec(Γ)</span>. For information on most of the objects and results discussed in this chapter, see <a href="chapBib.html#biBBH_2011">[BH11]</a>.</p>

<p><a id="X811034AF832F8BE9" name="X811034AF832F8BE9"></a></p>

<h4>3.1 <span class="Heading">Eigenvalues of regular graphs</span></h4>

<p>In this section, we introduce methods for investigating eigenvalues of regular graphs. The input for these methods will be a specific graph or the parameters of a graph.</p>

<p>Let <span class="SimpleMath">Γ</span> be a regular graph with parameters <span class="SimpleMath">(v,k)</span>. Then <span class="SimpleMath">Γ</span> has largest eigenvalue <span class="SimpleMath">k</span> (see <a href="chapBib.html#biBBH_2011">[BH11]</a>). Therefore we do not implement a "LargestEigenvalue" function for regular graphs.</p>

<p>Let <span class="SimpleMath">Γ</span> be a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span>. The eigenvalues of <span class="SimpleMath">Γ</span> and their corresponding multiplicities are uniquely determined by the parameters <span class="SimpleMath">(v,k,a,b)</span> (see <a href="chapBib.html#biBBH_2011">[BH11]</a>). Using this knowledge, we provide methods which take as input feasible strongly regular graph parameters <span class="SimpleMath">(v,k,a,b)</span>. We also give methods which return an exact representation of the eigenvalues of a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span>, and their multiplicities.</p>

<p><a id="X79AA0FEA8307F6C1" name="X79AA0FEA8307F6C1"></a></p>

<h5>3.1-1 LeastEigenvalueInterval</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeastEigenvalueInterval</code>( <var class="Arg">gamma</var>, <var class="Arg">eps</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeastEigenvalueInterval</code>( <var class="Arg">parms</var>, <var class="Arg">eps</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list.</p>

<p>Given a graph <var class="Arg">gamma</var> and rational number <var class="Arg">eps</var>, this function returns an interval containing the least eigenvalue of <var class="Arg">gamma</var>.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var> and rational number <var class="Arg">eps</var>, this function returns an interval containing the least eigenvalue of a strongly regular graph with parameters <var class="Arg">parms</var>.</p>

<p>The interval returned is in the form of a list, <var class="Arg">[y,z]</var> of rationals <span class="SimpleMath"><var class="Arg">y</var>≤ <var class="Arg">z</var></span> with the property that <span class="SimpleMath"><var class="Arg">z</var>-<var class="Arg">y</var>≤ <var class="Arg">eps</var></span>. If the eigenvalue is rational this function will return a list <var class="Arg">[y,z]</var>, where <span class="SimpleMath"><var class="Arg">y</var>=<var class="Arg">z</var></span>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueInterval(gamma,1/10);            </span>
[ -13/8, -25/16 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">parms:=SRGParameters(gamma);</span>
[ 5, 2, 0, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueInterval(parms,1/10);         </span>
[ -13/8, -25/16 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueInterval(JohnsonGraph(7,3),1/20);</span>
[ -3, -3 ]
    
  </pre></div>

<p><a id="X7A778BA880361164" name="X7A778BA880361164"></a></p>

<h5>3.1-2 SecondEigenvalueInterval</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SecondEigenvalueInterval</code>( <var class="Arg">gamma</var>, <var class="Arg">eps</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SecondEigenvalueInterval</code>( <var class="Arg">parms</var>, <var class="Arg">eps</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list.</p>

<p>Given a regular graph <var class="Arg">gamma</var> and rational number <var class="Arg">eps</var>, this function returns an interval containing the second largest eigenvalue of <var class="Arg">gamma</var>.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var> and rational number <var class="Arg">eps</var>, this function returns an interval containing the second largest eigenvalue of a strongly regular graph with parameters <var class="Arg">parms</var>.</p>

<p>The interval returned is in the form of a list, <var class="Arg">[y,z]</var> of rationals <span class="SimpleMath"><var class="Arg">y</var>≤ <var class="Arg">z</var></span> with the property that <span class="SimpleMath"><var class="Arg">z</var>-<var class="Arg">y</var>≤ <var class="Arg">eps</var></span>. If the eigenvalue is rational this function will return a list <var class="Arg">[y,z]</var>, where <span class="SimpleMath"><var class="Arg">y</var>=<var class="Arg">z</var></span>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueInterval(gamma,1/10);           </span>
[ 9/16, 5/8 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">parms:=SRGParameters(gamma);</span>
[ 5, 2, 0, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueInterval(parms,1/10);           </span>
[ 9/16, 5/8 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueInterval(JohnsonGraph(7,3),1/20);</span>
[ 5, 5 ]
    
  </pre></div>

<p><a id="X86F1FC147DB0DEE5" name="X86F1FC147DB0DEE5"></a></p>

<h5>3.1-3 LeastEigenvalueFromSRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeastEigenvalueFromSRGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">b</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer or an element of a cyclotomic field.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">[v, k, a, b]</var> this function returns the least eigenvalue of a strongly regular graph with parameters <span class="SimpleMath">(<var class="Arg">v,k,a,b</var>)</span>. If the eigenvalue is integer, the object returned is an integer. If the eigenvalue is irrational, the object returned lies in a cyclotomic field.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueFromSRGParameters([5,2,0,1]); </span>
E(5)^2+E(5)^3
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueFromSRGParameters([10,3,0,1]);</span>
-2
    
  </pre></div>

<p><a id="X8778AC2E87B8DAD6" name="X8778AC2E87B8DAD6"></a></p>

<h5>3.1-4 SecondEigenvalueFromSRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SecondEigenvalueFromSRGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">b</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer or an element of a cyclotomic field.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">[v, k, a, b]</var>, this function returns the second largest eigenvalue of a strongly regular graph with parameters <span class="SimpleMath">(<var class="Arg">v,k,a,b</var>)</span>. If the eigenvalue is integer, the object returned is an integer. If the eigenvalue is irrational, the object returned lies in a cyclotomic field.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueFromSRGParameters([5,2,0,1]);</span>
E(5)+E(5)^4
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueFromSRGParameters([10,3,0,1]);</span>
1
    
  </pre></div>

<p><a id="X80A9778F8468A4DD" name="X80A9778F8468A4DD"></a></p>

<h5>3.1-5 LeastEigenvalueMultiplicity</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeastEigenvalueMultiplicity</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">b</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">[v, k, a, b]</var> this function returns the multiplicity of the least eigenvalue of a strongly regular graph with parameters <span class="SimpleMath">(<var class="Arg">v,k,a,b</var>)</span>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueMultiplicity([16,9,4,6]); </span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">LeastEigenvalueMultiplicity([25,12,5,6]);</span>
12
    
  </pre></div>

<p><a id="X8740396B80617B47" name="X8740396B80617B47"></a></p>

<h5>3.1-6 SecondEigenvalueMultiplicity</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SecondEigenvalueMultiplicity</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">b</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</p>

<p>Given feasible strongly regular graph parameters <var class="Arg">[v, k, a, b]</var> this function returns the multiplicity of the second eigenvalue of a strongly regular graph with parameters <span class="SimpleMath">(<var class="Arg">v,k,a,b</var>)</span>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueMultiplicity([16,9,4,6]); </span>
9
<span class="GAPprompt">gap></span> <span class="GAPinput">SecondEigenvalueMultiplicity([25,12,5,6]);</span>
12
    
  </pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap2.html">[Previous Chapter]</a>    <a href="chap4.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

100%


¤ Dauer der Verarbeitung: 0.33 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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 ist noch experimentell.