<?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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>