Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 27.8.2025 mit Größe 12 kB image not shown  

Quellcode-Bibliothek chap4_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/chap4_mj.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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (Digraphs) - Chapter 4: Operators</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="chap4"  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="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chapA_mj.html">A</a>  <a href="chapB_mj.html">B</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="chap3_mj.html">[Previous Chapter]</a>    <a href="chap5_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4.html">[MathJax off]</a></p>
<p><a id="X7AD6F77E7D95C996" name="X7AD6F77E7D95C996"></a></p>
<div class="ChapSects"><a href="chap4_mj.html#X7AD6F77E7D95C996">4 <span class="Heading">Operators</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X84E0B5B88358C96B">4.1 <span class="Heading">Operators for digraphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4_mj.html#X829B911D7EFD2D85">4.1-1 IsSubdigraph</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4_mj.html#X833C3299787E2309">4.1-2 IsUndirectedSpanningTree</a></span>
</div></div>
</div>

<h3>4 <span class="Heading">Operators</span></h3>

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

<h4>4.1 <span class="Heading">Operators for digraphs</span></h4>


<dl>
<dt><strong class="Mark"><code class="code"><var class="Arg">digraph1</var> = <var class="Arg">digraph2</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var> have the same vertices, and <code class="code">DigraphEdges(<var class="Arg">digraph1</var>) = DigraphEdges(<var class="Arg">digraph2</var>)</code>, up to some re-ordering of the edge lists.</p>

<p>Note that this operator does not compare the vertex labels of <var class="Arg">digraph1</var> and <var class="Arg">digraph2</var>.</p>

</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">digraph1</var> < <var class="Arg">digraph2</var></code></strong></dt>
<dd><p>This operator returns <code class="keyw">true</code> if one of the following holds:</p>


<ul>
<li><p>The number <span class="SimpleMath">\(n_1\)</span> of vertices in <var class="Arg">digraph1</var> is less than the number <span class="SimpleMath">\(n_2\)</span> of vertices in <var class="Arg">digraph2</var>;</p>

</li>
<li><p><span class="SimpleMath">\(n_1 = n_2\)</span>, and the number <span class="SimpleMath">\(m_1\)</span> of edges in <var class="Arg">digraph1</var> is less than the number <span class="SimpleMath">\(m_2\)</span> of edges in <var class="Arg">digraph2</var>;</p>

</li>
<li><p><span class="SimpleMath">\(n_1 = n_2\)</span>, <span class="SimpleMath">\(m_1 = m_2\)</span>, and <code class="code">DigraphEdges(<var class="Arg">digraph1</var>)</code> is less than <code class="code">DigraphEdges(<var class="Arg">digraph2</var>)</code> after having both of these sets have been sorted with respect to the lexicographical order.</p>

</li>
</ul>
</dd>
</dl>
<p><a id="X829B911D7EFD2D85" name="X829B911D7EFD2D85"></a></p>

<h5>4.1-1 IsSubdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubdigraph</code>( <var class="Arg">super</var>, <var class="Arg">sub</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If <var class="Arg">super</var> and <var class="Arg">sub</var> are digraphs, then this operation returns <code class="keyw">true</code> if <var class="Arg">sub</var> is a subdigraph of <var class="Arg">super</var>, and <code class="keyw">false</code> if it is not.</p>

<p>A digraph <var class="Arg">sub</var> is a <em>subdigraph</em> of a digraph <var class="Arg">super</var> if <var class="Arg">sub</var> and <var class="Arg">super</var> share the same number of vertices, and the collection of edges of <var class="Arg">super</var> (including repeats) contains the collection of edges of <var class="Arg">sub</var> (including repeats).</p>

<p>In other words, <var class="Arg">sub</var> is a subdigraph of <var class="Arg">super</var> if and only if <code class="code">DigraphNrVertices(<var class="Arg">sub</var>) = DigraphNrVertices(<var class="Arg">super</var>)</code>, and for each pair of vertices <code class="code">i</code> and <code class="code">j</code>, there are at least as many edges of the form <code class="code">[i, j]</code> in <var class="Arg">super</var> as there are in <var class="Arg">sub</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Digraph([[2, 3], [1], [2, 3]]);</span>
<immutable digraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">h := Digraph([[2, 3], [], [2]]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(g, h);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(h, g);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(CompleteDigraph(4), CycleDigraph(4));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(CycleDigraph(4), ChainDigraph(4));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Digraph([[2, 2], [1]]);</span>
<immutable multidigraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">h := Digraph([[2], [1]]);</span>
<immutable digraph with 2 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(g, h);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(h, g);</span>
false</pre></div>

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

<h5>4.1-2 IsUndirectedSpanningTree</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsUndirectedSpanningTree</code>( <var class="Arg">super</var>, <var class="Arg">sub</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">‣ IsUndirectedSpanningForest</code>( <var class="Arg">super</var>, <var class="Arg">sub</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>The operation <code class="code">IsUndirectedSpanningTree</code> returns <code class="keyw">true</code> if the digraph <var class="Arg">sub</var> is an undirected spanning tree of the digraph <var class="Arg">super</var>, and the operation <code class="code">IsUndirectedSpanningForest</code> returns <code class="keyw">true</code> if the digraph <var class="Arg">sub</var> is an undirected spanning forest of the digraph <var class="Arg">super</var>.</p>

<p>An <em>undirected spanning tree</em> of a digraph <var class="Arg">super</var> is a subdigraph of <var class="Arg">super</var> that is an undirected tree (see <code class="func">IsSubdigraph</code> (<a href="chap4_mj.html#X829B911D7EFD2D85"><span class="RefLink">4.1-1</span></a>) and <code class="func">IsUndirectedTree</code> (<a href="chap6_mj.html#X80FC20FA7AC4BC2A"><span class="RefLink">6.6-9</span></a>)). Note that a digraph whose <code class="func">MaximalSymmetricSubdigraph</code> (<a href="chap3_mj.html#X829E3EAC7C4B3B1E"><span class="RefLink">3.3-5</span></a>) is not connected has no undirected spanning trees (see <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F"><span class="RefLink">6.6-3</span></a>)).</p>

<p>An <em>undirected spanning forest</em> of a digraph <var class="Arg">super</var> is a subdigraph of <var class="Arg">super</var> that is an undirected forest (see <code class="func">IsSubdigraph</code> (<a href="chap4_mj.html#X829B911D7EFD2D85"><span class="RefLink">4.1-1</span></a>) and <code class="func">IsUndirectedForest</code> (<a href="chap6_mj.html#X80FC20FA7AC4BC2A"><span class="RefLink">6.6-9</span></a>)), and is not contained in any larger such subdigraph of <var class="Arg">super</var>. Equivalently, an undirected spanning forest is a subdigraph of <var class="Arg">super</var> whose connected components coincide with those of the <code class="func">MaximalSymmetricSubdigraph</code> (<a href="chap3_mj.html#X829E3EAC7C4B3B1E"><span class="RefLink">3.3-5</span></a>) of <var class="Arg">super</var> (see <code class="func">DigraphConnectedComponents</code> (<a href="chap5_mj.html#X842FAD6A7B835977"><span class="RefLink">5.4-9</span></a>)).</p>

<p>Note that an undirected spanning tree is an undirected spanning forest that is connected.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteDigraph(4);</span>
<immutable complete digraph with 4 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">tree := Digraph([[3], [4], [1, 4], [2, 3]]);</span>
<immutable digraph with 4 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(D, tree) and IsUndirectedTree(tree);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUndirectedSpanningTree(D, tree);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">forest := EmptyDigraph(4);</span>
<immutable empty digraph with 4 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(D, forest) and IsUndirectedForest(forest);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUndirectedSpanningForest(D, forest);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubdigraph(tree, forest);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DigraphDisjointUnion(CycleDigraph(2), CycleDigraph(2));</span>
<immutable digraph with 4 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUndirectedTree(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUndirectedForest(D) and IsUndirectedSpanningForest(D, D);</span>
true</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap3_mj.html">[Previous Chapter]</a>    <a href="chap5_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="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chapA_mj.html">A</a>  <a href="chapB_mj.html">B</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

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

100%


¤ 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.0.21Bemerkung:  (vorverarbeitet)  ¤

*Bot Zugriff




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.