Anforderungen  |   Konzepte  |   Entwurf  |   Entwicklung  |   Qualitätssicherung  |   Lebenszyklus  |   Steuerung
 
 
 
 

products/sources/formale Sprachen/GAP/doc/hpc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 18.9.2025 mit Größe 954 B image not shown  

Quelle  chap3_mj.html   Sprache: unbekannt

 
<?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>
<script type="text/javascript"
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap2_mj.html">[Previous Chapter]</a>    <a href="chap4_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X7A25E43B7F2F7119" name="X7A25E43B7F2F7119"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X7A25E43B7F2F7119">3 <span class="Heading">Spectra of graphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X79AA0FEA8307F6C1">3.1-1 LeastEigenvalueInterval</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7A778BA880361164">3.1-2 SecondEigenvalueInterval</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X86F1FC147DB0DEE5">3.1-3 LeastEigenvalueFromSRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8778AC2E87B8DAD6">3.1-4 SecondEigenvalueFromSRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X80A9778F8468A4DD">3.1-5 LeastEigenvalueMultiplicity</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.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">\(\Gamma\)</span> be a graph of order <span class="SimpleMath">\(v\)</span>. The <em>adjacency matrix</em> of <span class="SimpleMath">\(\Gamma\)</span>, <span class="SimpleMath">\(A(\Gamma)\)</span>, is the <span class="SimpleMath">\(v\times v\)</span> matrix indexed by <span class="SimpleMath">\(V(\Gamma)\)</span> such that <span class="SimpleMath">\(A(\Gamma)_{xy}=1\)</span> if <span class="SimpleMath">\(xy\in E(\Gamma)\)</span>, and <span class="SimpleMath">\(A(\Gamma)_{xy}=0\)</span> otherwise.</p>

<p>The <em>spectrum</em> of <span class="SimpleMath">\(\Gamma\)</span>, <span class="SimpleMath">\(Spec(\Gamma)\)</span>, is the multiset of eigenvalues of its adjacency matrix, and an <em>eigenvalue of </em><span class="SimpleMath">\(\Gamma\)</span> is a member of <span class="SimpleMath">\(Spec(\Gamma)\)</span>. The <em>multiplicity</em> of an eigenvalue <span class="SimpleMath">\(\alpha\)</span> of <span class="SimpleMath">\(\Gamma\)</span> is the number of times <span class="SimpleMath">\(\alpha\)</span> appears in <span class="SimpleMath">\(Spec(\Gamma)\)</span>. For information on most of the objects and results discussed in this chapter, see <a href="chapBib_mj.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">\(\Gamma\)</span> be a regular graph with parameters <span class="SimpleMath">\((v,k)\)</span>. Then <span class="SimpleMath">\(\Gamma\)</span> has largest eigenvalue <span class="SimpleMath">\(k\)</span> (see <a href="chapBib_mj.html#biBBH_2011">[BH11]</a>). Therefore we do not implement a "LargestEigenvalue" function for regular graphs.</p>

<p>Let <span class="SimpleMath">\(\Gamma\)</span> be a strongly regular graph with parameters <span class="SimpleMath">\((v,k,a,b)\)</span>. The eigenvalues of <span class="SimpleMath">\(\Gamma\)</span> and their corresponding multiplicities are uniquely determined by the parameters <span class="SimpleMath">\((v,k,a,b)\)</span> (see <a href="chapBib_mj.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">\(\textit{y}\leq \textit{z}\)</span> with the property that <span class="SimpleMath">\(\textit{z}-\textit{y}\leq \textit{eps}\)</span>. If the eigenvalue is rational this function will return a list <var class="Arg">[y,z]</var>, where <span class="SimpleMath">\(\textit{y}=\textit{z}\)</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">\(\textit{y}\leq \textit{z}\)</span> with the property that <span class="SimpleMath">\(\textit{z}-\textit{y}\leq \textit{eps}\)</span>. If the eigenvalue is rational this function will return a list <var class="Arg">[y,z]</var>, where <span class="SimpleMath">\(\textit{y}=\textit{z}\)</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">\((\textit{v,k,a,b})\)</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">\((\textit{v,k,a,b})\)</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">\((\textit{v,k,a,b})\)</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">\((\textit{v,k,a,b})\)</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_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap2_mj.html">[Previous Chapter]</a>    <a href="chap4_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.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%


[ zur Elbe Produktseite wechseln0.40Quellennavigators  Analyse erneut starten  ]

                                                                                                                                                                                                                                                                                                                                                                                                     

Neuigkeiten

     Aktuelles
     Motto des Tages

Software

     Produkte
     Quellcodebibliothek

Aktivitäten

     Artikel über Sicherheit
     Anleitung zur Aktivierung von SSL

Muße

     Gedichte
     Musik
     Bilder
Jenseits des Üblichen ....

Besucherstatistik

Besucherstatistik

Monitoring

Montastic status badge