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

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

Quelle  chap2.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/agt/doc/chap2.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 2: Regular 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="chap2"  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="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2_mj.html">[MathJax on]</a></p>
<p><a id="X7DE253B0786AF3CD" name="X7DE253B0786AF3CD"></a></p>
<div class="ChapSects"><a href="chap2.html#X7DE253B0786AF3CD">2 <span class="Heading">Regular graphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X7DE253B0786AF3CD">2.1 <span class="Heading">Regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X805E414884F74B4E">2.1-1 RGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8506FD9C84FD1D88">2.1-2 IsRG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X859728CC8117B2C1">2.1-3 IsFeasibleRGParameters</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X852488AC7C59D75F">2.2 <span class="Heading">Edge-regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7CF02EC580D221E8">2.2-1 ERGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X811393AE7E816FFA">2.2-2 IsERG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8578C5A7817E2754">2.2-3 IsFeasibleERGParameters</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X87124C8C7EBA8FA4">2.3 <span class="Heading">Strongly regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7DBE09557F9F6ABD">2.3-1 SRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X80992E527F0BD206">2.3-2 IsSRG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8436E237851A17BC">2.3-3 IsFeasibleSRGParameters</a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Regular graphs</span></h3>

<p>In this chapter we give functions used to identify graphs with various regularity properties and determine their parameters.</p>

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

<h4>2.1 <span class="Heading">Regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k)</span> if <span class="SimpleMath">Γ</span> is simple and undirected, it has order <span class="SimpleMath">v</span>, and every vertex of <span class="SimpleMath">Γ</span> has degree <span class="SimpleMath">k</span>.</p>

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

<h5>2.1-1 RGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RGParameters</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list or <code class="keyw">fail</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns the regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not a regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=HammingGraph(3,4);;                              </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RGParameters(gamma);</span>
[ 64, 9 ]
    
  </pre></div>

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

<h5>2.1-2 IsRG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRG</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns <code class="keyw">true</code> if <var class="Arg">gamma</var> is a regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=TriangularGraph(6);;                             </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
true
    
  </pre></div>

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

<h5>2.1-3 IsFeasibleRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFeasibleRGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a list of integers of length 2, <var class="Arg">[v,k]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v</var>, <var class="Arg">k</var> )</span> is a feasible parameter tuple for a regular graph. Otherwise, the function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">(v, k)</span> is a <em>feasible</em> parameter tuple for a regular graph if it satisfies the following well-known conditions:</p>


<ul>
<li><p><span class="SimpleMath">v>k≥ 0</span>;</p>

</li>
<li><p><span class="SimpleMath">2</span> divides <span class="SimpleMath">vk</span>.</p>

</li>
</ul>
<p>Any regular graph must have parameters that satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleRGParameters([15,9]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleRGParameters([16,9]);</span>
true
    
  </pre></div>

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

<h4>2.2 <span class="Heading">Edge-regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>edge-regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k,a)</span> if it is regular with parameters <span class="SimpleMath">(v,k)</span>, it has at least one edge, and every pair of adjacent vertices have exactly <span class="SimpleMath">a</span> common neighbours.</p>

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

<h5>2.2-1 ERGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ERGParameters</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list or <code class="keyw">fail</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns the edge-regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not an edge-regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ERGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(7,3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ERGParameters(gamma);</span>
[ 35, 12, 5 ]
    
  </pre></div>

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

<h5>2.2-2 IsERG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsERG</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns <code class="keyw">true</code> if <var class="Arg">gamma</var> is an edge-regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsERG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(7,3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsERG(gamma);</span>
true
    
  </pre></div>

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

<h5>2.2-3 IsFeasibleERGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFeasibleERGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a list of integers of length 3, <var class="Arg">[v,k,a]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v, k, a</var> )</span> is a feasible parameter tuple for an edge-regular graph. Otherwise, the function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">( v, k, a )</span> is a <em>feasible</em> parameter tuple for an edge-regular graph if it satisfies the following well-known conditions:</p>


<ul>
<li><p><span class="SimpleMath">(v,k)</span> is a feasible regular graph parameter tuple;</p>

</li>
<li><p><span class="SimpleMath">k>a≥ 0</span>;</p>

</li>
<li><p><span class="SimpleMath">2</span> divides <span class="SimpleMath">ka</span> and <span class="SimpleMath">6</span> divides <span class="SimpleMath">vka</span>;</p>

</li>
<li><p><span class="SimpleMath">v-2k+a ≥ 0</span>.</p>

</li>
</ul>
<p>Any edge-regular graph must have parameters which satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleERGParameters([15,9,6]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleERGParameters([16,9,4]);</span>
true
    
  </pre></div>

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

<h4>2.3 <span class="Heading">Strongly regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>strongly regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k,a,b)</span> if it is edge-regular with parameters <span class="SimpleMath">(v,k,a)</span>, it has at least one pair of distinct non-adjacent vertices, and every pair of distinct non-adjacent vertices have exactly <span class="SimpleMath">b</span> common neighbours.</p>

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

<h5>2.3-1 SRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SRGParameters</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list or <code class="keyw">fail</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns the strongly regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not a strongly regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=CompleteGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SRGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(5,3);;            </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SRGParameters(gamma);</span>
[ 10, 6, 3, 4 ]
    
  </pre></div>

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

<h5>2.3-2 IsSRG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSRG</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a graph <var class="Arg">gamma</var>, this function returns <code class="keyw">true</code> if <var class="Arg">gamma</var> is a strongly regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=CompleteGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSRG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(5,3);;         </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSRG(gamma);</span>
true
    
  </pre></div>

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

<h5>2.3-3 IsFeasibleSRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFeasibleSRGParameters</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: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Given a list of integers of length 4, <var class="Arg">[v,k,a,b]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v, k, a, b</var> )</span> is a feasible parameter tuple for a strongly regular graph. Otherwise, this function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">(v,k,a,b)</span> is a <em>feasible</em> parameter tuple for a strongly regular graph if it satisfies the following well-known conditions:</p>


<ul>
<li><p><span class="SimpleMath">(v,k,a)</span> is a feasible edge-regular graph parameter tuple;</p>

</li>
<li><p><span class="SimpleMath">k≥ b</span>;</p>

</li>
<li><p><span class="SimpleMath">(v-k-1)b = k(k-a-1)</span>;</p>

</li>
<li><p><span class="SimpleMath">v-2-2k+b ≥ 0</span>;</p>

</li>
<li><p>the formulae for the multiplicities of the eigenvalues of a strongly regular graph with these parameters evaluate to positive integers (see <a href="chapBib.html#biBBH_2011">[BH11]</a>).</p>

</li>
</ul>
<p>Any strongly regular graph must have parameters which satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleSRGParameters([15,9,4,7]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleSRGParameters([10,3,0,1]);</span>
true
    
  </pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.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.15 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.





                                                                                                                                                                                                                                                                                                                                                                                                     

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