|
|
|
|
Quelle chap6.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/digraphs/doc/chap6.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 (Digraphs) - Chapter 6: Properties of digraphs</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="chap6" 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="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapA.html">A</a> <a href="chapB.html">B</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="chap5.html">[Previous Chapter]</a> <a href="chap7.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X7ADDEFD478D470D5" name="X7ADDEFD478D470D5"></a></p>
<div class="ChapSects"><a href="chap6.html#X7ADDEFD478D470D5">6 <span class="Heading">Properties of digraphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7D6A52AB7C69A9CA">6.1 <span class="Heading">Vertex properties</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X82DBFFF17E708803">6.1-1 DigraphHasAVertex</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78E16B8B7DF55B59">6.1-2 DigraphHasNoVertices</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7F49388F8245F0E9">6.2 <span class="Heading">Edge properties</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7D92935C7D535187">6.2-1 DigraphHasLoops</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DB1BC2286FC08E2">6.2-2 IsAntiSymmetricDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X860CFB0C8665F356">6.2-3 IsBipartiteDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X790A4DBF8533516E">6.2-4 IsCompleteBipartiteDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X81F28D4D879FE3B2">6.2-5 IsCompleteDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7FD1A15779FEC341">6.2-6 IsCompleteMultipartiteDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E894CCF7B1C27AE">6.2-7 IsEmptyDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X83762C257DED2751">6.2-8 IsEquivalenceDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E8F37E585DAED52">6.2-9 IsFunctionalDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X793FB02C7C59D85B">6.2-10 IsPermutationDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BB84CFC7E8B2B26">6.2-11 IsMultiDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E14AE1F7CA23141">6.2-12 IsNonemptyDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8462D8E2792B23F6">6.2-13 IsReflexiveDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X81B3EA7887219860">6.2-14 IsSymmetricDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DD8D1A185EBE865">6.2-15 IsTournament</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F0835667F29F0C0">6.2-16 IsTransitiveDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X85A9843E80A9B590">6.3 <span class="Heading">Edge Weights</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8639092D8689333D">6.3-1 EdgeWeights</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E14055A84A52A07">6.3-2 EdgeWeightedDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X810B2DD7794AFBE8">6.3-3 EdgeWeightedDigraphTotalWeight</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E5060AB7FB4F31C">6.3-4 EdgeWeightedDigraphMinimumSpanningTree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EDB9C9A840F6A84">6.3-5 EdgeWeightedDigraphShortestPaths</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DAF81B779BD9165">6.3-6 EdgeWeightedDigraphShortestPath</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X869EFE9F818C6E22">6.3-7 DigraphMaximumFlow</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8194E7078167A9E4">6.3-8 RandomUniqueEdgeWeightedDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X86424F167BD4F629">6.4 <span class="Heading">Orders</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8617726C7829F796">6.4-1 IsPreorderDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X82BAE6D37D49A145">6.4-2 IsPartialOrderDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78D3E17B7F737516">6.4-3 IsMeetSemilatticeDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X84F4711F7FA36848">6.4-4 DigraphMeetTable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X786213437E99065B">6.4-5 IsOrderIdeal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7A1D8F4582F8EA53">6.4-6 IsOrderFilter</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DEDCD177E5AE824">6.4-7 IsUpperSemimodularDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B566B4A86E18F45">6.4-8 IsDistributiveLatticeDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80659D5784790B52">6.4-9 IsModularLatticeDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7AAF896982EC22FA">6.5 <span class="Heading">Regularity</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7A3F78B37E31D9E1">6.5-1 IsInRegularDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F0A806E7BCB413C">6.5-2 IsOutRegularDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7AF9DB1E7DB12306">6.5-3 IsRegularDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E2082AC7CAE59CD">6.5-4 IsDistanceRegularDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X780DAEB37C5E07FD">6.6 <span class="Heading">Connectivity and cycles</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BD08D4478218F77">6.6-1 IsAcyclicDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79563B297C220FB5">6.6-2 IsChainDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X83C08C0B7EC1A91F">6.6-3 IsConnectedDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X838FAF2D825977BE">6.6-4 IsBiconnectedDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7D2A6572820B7F24">6.6-5 IsBridgelessDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B37B9467C68C208">6.6-6 IsStronglyConnectedDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80E883967EBE839E">6.6-7 IsAperiodicDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B46EA6C7B2DF2FB">6.6-8 IsDirectedTree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80FC20FA7AC4BC2A">6.6-9 IsUndirectedTree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79DFBB198525544E">6.6-10 IsEulerianDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79EFEBC37C2D262D">6.6-11 IsHamiltonianDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E91320B8028F5D8">6.6-12 IsCycleDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7E2305528492DDC0">6.7 <span class="Heading">Planarity</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8606D415858C40AA">6.7-1 IsPlanarDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8251E8B187E7F059">6.7-2 IsOuterPlanarDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X83DC8AD283C41326">6.8 <span class="Heading">Homomorphisms and transformations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78C0B2637985648B">6.8-1 IsDigraphCore</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8361CA6E8401FF26">6.8-2 IsEdgeTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B26E4447A1611E9">6.8-3 IsVertexTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7FB8789A7BF847E6">6.8-4 Is2EdgeTransitive</a></span>
</div></div>
</div>
<h3>6 <span class="Heading">Properties of digraphs</span></h3>
<p><a id="X7D6A52AB7C69A9CA" name="X7D6A52AB7C69A9CA"></a></p>
<h4>6.1 <span class="Heading">Vertex properties</span></h4>
<p><a id="X82DBFFF17E708803" name="X82DBFFF17E708803"></a></p>
<h5>6.1-1 DigraphHasAVertex</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphHasAVertex</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> has at least one vertex, and <code class="keyw">false</code> if it does not.</p>
<p>See also <code class="func">DigraphHasNoVertices</code> (<a href="chap6.html#X78E16B8B7DF55B59"><span class="RefLink">6.1-2</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([]);</span>
<immutable empty digraph with 0 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasAVertex(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[]]);</span>
<immutable empty digraph with 1 vertex>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasAVertex(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], [1]]);</span>
<immutable digraph with 2 vertices, 1 edge>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasAVertex(D);</span>
true</pre></div>
<p><a id="X78E16B8B7DF55B59" name="X78E16B8B7DF55B59"></a></p>
<h5>6.1-2 DigraphHasNoVertices</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphHasNoVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is the unique digraph with zero vertices, and <code class="keyw">false</code> otherwise.</p>
<p>See also <code class="func">DigraphHasAVertex</code> (<a href="chap6.html#X82DBFFF17E708803"><span class="RefLink">6.1-1</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([]);</span>
<immutable empty digraph with 0 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasNoVertices(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[]]);</span>
<immutable empty digraph with 1 vertex>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasNoVertices(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], [1]]);</span>
<immutable digraph with 2 vertices, 1 edge>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasNoVertices(D);</span>
false</pre></div>
<p><a id="X7F49388F8245F0E9" name="X7F49388F8245F0E9"></a></p>
<h4>6.2 <span class="Heading">Edge properties</span></h4>
<p><a id="X7D92935C7D535187" name="X7D92935C7D535187"></a></p>
<h5>6.2-1 DigraphHasLoops</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphHasLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> has loops, and <code class="keyw">false</code> if it does not. A loop is an edge with equal source and range.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[1, 2], [2]]);</span>
<immutable digraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphEdges(D);</span>
[ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasLoops(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[2, 3], [1], [2]]);</span>
<immutable digraph with 3 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphEdges(D);</span>
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 3, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasLoops(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteDigraph(IsMutableDigraph, 4);</span>
<mutable digraph with 4 vertices, 12 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphHasLoops(D);</span>
false</pre></div>
<p><a id="X7DB1BC2286FC08E2" name="X7DB1BC2286FC08E2"></a></p>
<h5>6.2-2 IsAntiSymmetricDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAntiSymmetricDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAntisymmetricDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is antisymmetric, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is <em>antisymmetric</em> if whenever there is an edge with source <code class="code">u</code> and range <code class="code">v</code>, and an edge with source <code class="code">v</code> and range <code class="code">u</code>, then the vertices <code class="code">u</code> and <code class="code">v</code> are equal.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr1 := Digraph([[2], [1, 3], [2, 3]]);</span>
<immutable digraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAntisymmetricDigraph(gr1);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphEdges(gr1){[1, 2]};</span>
[ [ 1, 2 ], [ 2, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 := Digraph([[1, 2], [3, 3], [1]]);</span>
<immutable multidigraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAntisymmetricDigraph(gr2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphEdges(gr2);</span>
[ [ 1, 1 ], [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 1 ] ]
</pre></div>
<p><a id="X860CFB0C8665F356" name="X860CFB0C8665F356"></a></p>
<h5>6.2-3 IsBipartiteDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBipartiteDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is bipartite, and <code class="keyw">false</code> if it is not. A digraph is bipartite if and only if the vertices of <var class="Arg">digraph</var> can be partitioned into two non-empty sets such that the source and range of any edge of <var class="Arg">digraph</var> lie in distinct sets. Equivalently, a digraph is bipartite if and only if it is 2-colorable; see <code class="func">DigraphGreedyColouring</code> (<a href="chap7.html#X7AB7200D831013C1"><span class="RefLink">7.3-16</span></a>).</p>
<p>See also <code class="func">DigraphBicomponents</code> (<a href="chap5.html#X7F1B5A2782F598B1"><span class="RefLink">5.4-13</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := ChainDigraph(4);</span>
<immutable chain digraph with 4 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartiteDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CycleDigraph(3);</span>
<immutable cycle digraph with 3 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartiteDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);</span>
<mutable digraph with 9 vertices, 40 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartiteDigraph(D);</span>
true</pre></div>
<p><a id="X790A4DBF8533516E" name="X790A4DBF8533516E"></a></p>
<h5>6.2-4 IsCompleteBipartiteDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCompleteBipartiteDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is a complete bipartite digraph, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is a <em>complete bipartite digraph</em> if it is bipartite, see <code class="func">IsBipartiteDigraph</code> (<a href="chap6.html#X860CFB0C8665F356"><span class="RefLink">6.2-3</span></a>), and there exists a unique edge with source <code class="code">i</code> and range <code class="code">j</code> if and only if <code class="code">i</code> and <code class="code">j</code> lie in different bicomponents of <var class="Arg">digraph</var>, see <code class="func">DigraphBicomponents</code> (<a href="chap5.html#X7F1B5A2782F598B1"><span class="RefLink">5.4-13</span></a>).</p>
<p>Equivalently, a bipartite digraph with bicomponents of size <span class="SimpleMath">m</span> and <span class="SimpleMath">n</span> is complete precisely when it has <span class="SimpleMath">2mn</span> edges, none of which are multiple edges.</p>
<p>See also <code class="func">CompleteBipartiteDigraph</code> (<a href="chap3.html#X8795B0AD856014FA"><span class="RefLink">3.5-14</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CycleDigraph(2);</span>
<immutable cycle digraph with 2 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteBipartiteDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CycleDigraph(4);</span>
<immutable cycle digraph with 4 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartiteDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteBipartiteDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);</span>
<mutable digraph with 9 vertices, 40 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteBipartiteDigraph(D);</span>
true</pre></div>
<p><a id="X81F28D4D879FE3B2" name="X81F28D4D879FE3B2"></a></p>
<h5>6.2-5 IsCompleteDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCompleteDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is complete, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is <em>complete</em> if it has no loops, and for all <em>distinct</em> vertices <code class="code">i</code> and <code class="code">j</code>, there is exactly one edge with source <code class="code">i</code> and range <code class="code">j</code>. Equivalently, a digraph with <span class="SimpleMath">n</span> vertices is complete precisely when it has <span class="SimpleMath">n(n - 1)</span> edges, no loops, and no multiple edges.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[2, 3], [1, 3], [1, 2]]);</span>
<immutable digraph with 3 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[2, 2], [1]]);</span>
<immutable multidigraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);</span>
<mutable digraph with 9 vertices, 40 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteDigraph(D);</span>
false</pre></div>
<p><a id="X7FD1A15779FEC341" name="X7FD1A15779FEC341"></a></p>
<h5>6.2-6 IsCompleteMultipartiteDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCompleteMultipartiteDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property returns <code class="keyw">true</code> if <var class="Arg">digraph</var> is a complete multipartite digraph, and <code class="keyw">false</code> if not.</p>
<p>A digraph is a <em>complete multipartite digraph</em> if and only if its vertices can be partitioned into at least two maximal independent sets, where every possible edge between these independent sets occurs in the digraph exactly once.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteMultipartiteDigraph([2, 4, 6]);</span>
<immutable complete multipartite digraph with 12 vertices, 88 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteMultipartiteDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteBipartiteDigraph(IsMutableDigraph, 5, 4);</span>
<mutable digraph with 9 vertices, 40 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCompleteMultipartiteDigraph(D);</span>
true</pre></div>
<p><a id="X7E894CCF7B1C27AE" name="X7E894CCF7B1C27AE"></a></p>
<h5>6.2-7 IsEmptyDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEmptyDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNullDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is empty, and <code class="keyw">false</code> if it is not. A digraph is <em>empty</em> if it has no edges.</p>
<p><code class="func">IsNullDigraph</code> is a synonym for <code class="func">IsEmptyDigraph</code>. See also <code class="func">IsNonemptyDigraph</code> (<a href="chap6.html#X7E14AE1F7CA23141"><span class="RefLink">6.2-12</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], []]);</span>
<immutable empty digraph with 2 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEmptyDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNullDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], [1]]);</span>
<immutable digraph with 2 vertices, 1 edge>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEmptyDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNullDigraph(D);</span>
false</pre></div>
<p><a id="X83762C257DED2751" name="X83762C257DED2751"></a></p>
<h5>6.2-8 IsEquivalenceDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEquivalenceDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>A digraph is an equivalence digraph if and only if the digraph satisfies all of <code class="func">IsReflexiveDigraph</code> (<a href="chap6.html#X8462D8E2792B23F6"><span class="RefLink">6.2-13</span></a>), <code class="func">IsSymmetricDigraph</code> (<a href="chap6.html#X81B3EA7887219860"><span class="RefLink">6.2-14</span></a>) and <code class="func">IsTransitiveDigraph</code> (<a href="chap6.html#X7F0835667F29F0C0"><span class="RefLink">6.2-16</span></a>). A partial order <var class="Arg">digraph</var> corresponds to an equivalence relation.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[1, 3], [2], [1, 3]]);</span>
<immutable digraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEquivalenceDigraph(D);</span>
true
</pre></div>
<p><a id="X7E8F37E585DAED52" name="X7E8F37E585DAED52"></a></p>
<h5>6.2-9 IsFunctionalDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFunctionalDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is functional.</p>
<p>A digraph is <em>functional</em> if every vertex is the source of a unique edge.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr1 := Digraph([[3], [2], [2], [1], [6], [5]]);</span>
<immutable digraph with 6 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFunctionalDigraph(gr1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 := Digraph([[1, 2], [1]]);</span>
<immutable digraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFunctionalDigraph(gr2);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gr3 := Digraph(3, [1, 2, 3], [2, 3, 1]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFunctionalDigraph(gr3);</span>
true
</pre></div>
<p><a id="X793FB02C7C59D85B" name="X793FB02C7C59D85B"></a></p>
<h5>6.2-10 IsPermutationDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPermutationDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is functional and each node has only one in-neighbour.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr1 := Digraph([[3], [2], [2], [1], [6], [5]]);</span>
<immutable digraph with 6 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermutationDigraph(gr1);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 := Digraph([[1, 2], [1]]);</span>
<immutable digraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermutationDigraph(gr2);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gr3 := Digraph(3, [1, 2, 3], [2, 3, 1]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermutationDigraph(gr3);</span>
true
</pre></div>
<p><a id="X7BB84CFC7E8B2B26" name="X7BB84CFC7E8B2B26"></a></p>
<h5>6.2-11 IsMultiDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMultiDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>A <em>multidigraph</em> is one that has at least two edges with equal source and range.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph(["a", "b", "c"], ["a", "b", "b"], ["b", "c", "a"]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DigraphFromDigraph6String("&Bug");</span>
<immutable digraph with 3 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDuplicateFree(DigraphEdges(D));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[1, 2, 3, 2], [2, 1], [3]]);</span>
<immutable multidigraph with 3 vertices, 7 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDuplicateFree(DigraphEdges(D));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DigraphMutableCopy(D);</span>
<mutable multidigraph with 3 vertices, 7 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiDigraph(D);</span>
true</pre></div>
<p><a id="X7E14AE1F7CA23141" name="X7E14AE1F7CA23141"></a></p>
<h5>6.2-12 IsNonemptyDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNonemptyDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is nonempty, and <code class="keyw">false</code> if it is not. A digraph is <em>nonempty</em> if it has at least one edge.</p>
<p>See also <code class="func">IsEmptyDigraph</code> (<a href="chap6.html#X7E894CCF7B1C27AE"><span class="RefLink">6.2-7</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], []]);</span>
<immutable empty digraph with 2 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNonemptyDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[], [1]]);</span>
<immutable digraph with 2 vertices, 1 edge>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNonemptyDigraph(D);</span>
true</pre></div>
<p><a id="X8462D8E2792B23F6" name="X8462D8E2792B23F6"></a></p>
<h5>6.2-13 IsReflexiveDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsReflexiveDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is reflexive, and <code class="keyw">false</code> if it is not. A digraph is <em>reflexive</em> if it has a loop at every vertex.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[1, 2], [2]]);</span>
<immutable digraph with 2 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReflexiveDigraph(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[3, 1], [4, 2], [3], [2, 1]]);</span>
<immutable digraph with 4 vertices, 7 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReflexiveDigraph(D);</span>
false
</pre></div>
<p><a id="X81B3EA7887219860" name="X81B3EA7887219860"></a></p>
<h5>6.2-14 IsSymmetricDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSymmetricDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is symmetric, and <code class="keyw">false</code> if it is not.</p>
<p>A <em>symmetric digraph</em> is one where for each non-loop edge, having source <code class="code">u</code> and range <code class="code">v</code>, there is a corresponding edge with source <code class="code">v</code> and range <code class="code">u</code>. If there are <code class="code">n</code> edges with source <code class="code">u</code> and range <code class="code">v</code>, then there must be precisely <code class="code">n</code> edges with source <code class="code">v</code> and range <code class="code">u</code>. In other words, a symmetric digraph has a symmetric adjacency matrix <code class="func">AdjacencyMatrix</code> (<a href="chap5.html#X7DC2CD70830BEE60"><span class="RefLink">5.2-1</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr1 := Digraph([[2], [1, 3], [2, 3]]);</span>
<immutable digraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSymmetricDigraph(gr1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">adj1 := AdjacencyMatrix(gr1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(adj1);</span>
[ [ 0, 1, 0 ],
[ 1, 0, 1 ],
[ 0, 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">adj1 = TransposedMat(adj1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gr1 = DigraphReverse(gr1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 := Digraph([[2, 3], [1, 3], [2, 3]]);</span>
<immutable digraph with 3 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSymmetricDigraph(gr2);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">adj2 := AdjacencyMatrix(gr2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(adj2);</span>
[ [ 0, 1, 1 ],
[ 1, 0, 1 ],
[ 0, 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">adj2 = TransposedMat(adj2);</span>
false
</pre></div>
<p><a id="X7DD8D1A185EBE865" name="X7DD8D1A185EBE865"></a></p>
<h5>6.2-15 IsTournament</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTournament</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is a tournament, and <code class="keyw">false</code> if it is not.</p>
<p>A tournament is an orientation of a complete (undirected) graph. Specifically, a tournament is a digraph which has a unique directed edge (of some orientation) between any pair of distinct vertices, and no loops.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[2, 3, 4], [3, 4], [4], []]);</span>
<immutable digraph with 4 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTournament(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[2], [1], [3]]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTournament(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CycleDigraph(IsMutableDigraph, 3);</span>
<mutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTournament(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphRemoveEdge(D, 1, 2);</span>
<mutable digraph with 3 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTournament(D);</span>
false
</pre></div>
<p><a id="X7F0835667F29F0C0" name="X7F0835667F29F0C0"></a></p>
<h5>6.2-16 IsTransitiveDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTransitiveDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is transitive, and <code class="keyw">false</code> if it is not. A digraph is <em>transitive</em> if whenever <code class="code">[ i, j ]</code> and <code class="code">[ j, k ]</code> are edges of the digraph, then <code class="code">[ i, k ]</code> is also an edge of the digraph.</p>
<p>Let <span class="SimpleMath">n</span> be the number of vertices of an arbitrary digraph, and let <span class="SimpleMath">m</span> be the number of edges. For general digraphs, the methods used for this property use a version of the Floyd-Warshall algorithm, and have complexity <span class="SimpleMath">O(n^3)</span>. However for digraphs which are topologically sortable [<code class="func">DigraphTopologicalSort</code> (<a href="chap5.html#X785C30378064CF47"><span class="RefLink">5.1-10</span></a>)], then methods with complexity <span class="SimpleMath">O(m + n + m ⋅ n)</span> will be used when appropriate.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([[1, 2], [3], [3]]);</span>
<immutable digraph with 3 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveDigraph(D);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 := Digraph([[1, 2, 3], [3], [3]]);</span>
<immutable digraph with 3 vertices, 5 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveDigraph(gr2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gr2 = DigraphTransitiveClosure(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gr3 := Digraph([[1, 2, 2, 3], [3, 3], [3]]);</span>
<immutable multidigraph with 3 vertices, 7 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveDigraph(gr3);</span>
true
</pre></div>
<p><a id="X85A9843E80A9B590" name="X85A9843E80A9B590"></a></p>
<h4>6.3 <span class="Heading">Edge Weights</span></h4>
<p><a id="X8639092D8689333D" name="X8639092D8689333D"></a></p>
<h5>6.3-1 EdgeWeights</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeights</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of lists of integers, floats or rationals.</p>
<p><code class="code">EdgeWeights</code> returns the list of lists of edge weights of the edges of the digraph <var class="Arg">digraph</var>.</p>
<p>More specifically, <code class="code">weights[i][j]</code> is the weight given to the <code class="code">j</code>th edge from vertex <code class="code">i</code>, according to the ordering of edges given by <code class="code">OutNeighbours(digraph)[i]</code>.</p>
<p>The function <code class="code">EdgeWeights</code> returns an immutable list of immutable lists, whereas the function <code class="code">EdgeWeightsMutableCopy</code> returns a copy of <code class="code">EdgeWeights</code> which is a mutable list of mutable lists.</p>
<p>The edge weights of a digraph cannot be computed and must be set either using <code class="code">SetEdgeWeights</code> or <code class="func">EdgeWeightedDigraph</code> (<a href="chap6.html#X7E14055A84A52A07"><span class="RefLink">6.3-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr := EdgeWeightedDigraph([[2], [3], [1]], [[5], [10], [15]]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeights(gr);</span>
[ [ 5 ], [ 10 ], [ 15 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a := EdgeWeightsMutableCopy(gr);</span>
[ [ 5 ], [ 10 ], [ 15 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a[1][1] := 100;</span>
100
<span class="GAPprompt">gap></span> <span class="GAPinput">a;</span>
[ [ 100 ], [ 10 ], [ 15 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b := EdgeWeights(gr);</span>
[ [ 5 ], [ 10 ], [ 15 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b[1][1] := 534;</span>
Error, List Assignment: <list> must be a mutable list
</pre></div>
<p><a id="X7E14055A84A52A07" name="X7E14055A84A52A07"></a></p>
<h5>6.3-2 EdgeWeightedDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraph</code>( <var class="Arg">digraph</var>, <var class="Arg">weights</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A digraph or <code class="keyw">fail</code></p>
<p>The argument <var class="Arg">digraph</var> may be a digraph or a list of lists of integers, floats or rationals.</p>
<p><var class="Arg">weights</var> must be a list of lists of integers, floats or rationals of an equal size and shape to <code class="code">OutNeighbours(digraph)</code>, otherwise it will fail.</p>
<p>This will create a digraph and set the EdgeWeights to <var class="Arg">weights</var>.</p>
<p>See <code class="func">EdgeWeights</code> (<a href="chap6.html#X8639092D8689333D"><span class="RefLink">6.3-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := EdgeWeightedDigraph(Digraph([[2], [1]]), [[5], [15]]);</span>
<immutable digraph with 2 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := EdgeWeightedDigraph([[2], [1]], [[5], [15]]);</span>
<immutable digraph with 2 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeights(g);</span>
[ [ 5 ], [ 15 ] ]
</pre></div>
<p><a id="X810B2DD7794AFBE8" name="X810B2DD7794AFBE8"></a></p>
<h5>6.3-3 EdgeWeightedDigraphTotalWeight</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphTotalWeight</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer, float or rational.</p>
<p>If <var class="Arg">digraph</var> is a digraph with edge weights, then this attribute returns the sum of the weights of its edges.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.</p>
<p>See <code class="func">EdgeWeights</code> (<a href="chap6.html#X8639092D8689333D"><span class="RefLink">6.3-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := EdgeWeightedDigraph([[2], [1], [1, 2]],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[12], [5], [6, 9]]);</span>
<immutable digraph with 3 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeightedDigraphTotalWeight(D);</span>
32</pre></div>
<p><a id="X7E5060AB7FB4F31C" name="X7E5060AB7FB4F31C"></a></p>
<h5>6.3-4 EdgeWeightedDigraphMinimumSpanningTree</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphMinimumSpanningTree</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A digraph.</p>
<p>If <var class="Arg">digraph</var> is a connected digraph with edge weights, then this attribute returns a digraph which is a minimum spanning tree of <var class="Arg">digraph</var>.</p>
<p>A <em>spanning tree</em> of a digraph is a subdigraph with the same vertices but a subset of its edges that form an undirected tree. It is <em>minimum</em> if it has the smallest possible total weight for a spanning tree of that digraph.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.</p>
<p>See <code class="func">EdgeWeights</code> (<a href="chap6.html#X8639092D8689333D"><span class="RefLink">6.3-1</span></a>), <code class="func">EdgeWeightedDigraphTotalWeight</code> (<a href="chap6.html#X810B2DD7794AFBE8"><span class="RefLink">6.3-3</span></a>) and <code class="func">IsConnectedDigraph</code> (<a href="chap6.html#X83C08C0B7EC1A91F"><span class="RefLink">6.6-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := EdgeWeightedDigraph([[2], [1], [1, 2]],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[12], [5], [6, 9]]);</span>
<immutable digraph with 3 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := EdgeWeightedDigraphMinimumSpanningTree(D);</span>
<immutable digraph with 3 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeights(T);</span>
[ [ ], [ 5 ], [ 6 ] ]</pre></div>
<p><a id="X7EDB9C9A840F6A84" name="X7EDB9C9A840F6A84"></a></p>
<h5>6.3-5 EdgeWeightedDigraphShortestPaths</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphShortestPaths</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphShortestPaths</code>( <var class="Arg">digraph</var>, <var class="Arg">source</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A record.</p>
<p>If <var class="Arg">digraph</var> is an edge-weighted digraph, this attribute returns a record describing the paths of lowest total weight (the <em>shortest paths</em>) connecting each pair of vertices. If the optional argument <var class="Arg">source</var> is specified and is a vertex of <var class="Arg">digraph</var>, then the output will only contain information on paths originating from that vertex.</p>
<p>In the two-argument form, the value returned is a record containing three components: <code class="code">distances</code>, <code class="code">parents</code> and <code class="code">edges</code>. Each of these is a list of integers with one entry for each vertex <code class="code">v</code> as follows:</p>
<ul>
<li><p><code class="code">distances[v]</code> is the total weight of the shortest path from <var class="Arg">source</var> to <code class="code">v</code>.</p>
</li>
<li><p><code class="code">parents[v]</code> is the final vertex before <code class="code">v</code> on the shortest path from <var class="Arg">source</var> to <code class="code">v</code>.</p>
</li>
<li><p><code class="code">edges[v]</code> is the index of the edge of lowest weight going from <code class="code">parents[v]</code> to <code class="code">v</code>.</p>
</li>
</ul>
<p>Using these three components together, you can find the shortest edge weighted path to all other vertices from a starting vertex.</p>
<p>If no path exists from <var class="Arg">source</var> to <code class="code">v</code>, then <code class="code">parents[v]</code> and <code class="code">edges[v]</code> will both be <code class="keyw">fail</code>. The distance from <var class="Arg">source</var> to itself is considered to be 0, and so both <code class="code">parents[<var class="Arg">source</var>]</code> and <code class="code">edges[<var class="Arg">source</var>]</code> are <code class="keyw">fail</code>. Edge weights can have negative values, but there is currently no implemented method for this operation if a negative-weighted cycle exists.</p>
<p>In the one-argument form, the value returned is also a record containing components <code class="code">distances</code>, <code class="code">parents</code> and <code class="code">edges</code>, but each of these will instead be a list of lists in which the <code class="code">i</code>th entry is the list that corresponds to paths starting at <code class="code">i</code>.</p>
<p>For a simple way of finding the shortest path between two specific vertices, see <code class="func">EdgeWeightedDigraphShortestPath</code> (<a href="chap6.html#X7DAF81B779BD9165"><span class="RefLink">6.3-6</span></a>). See also the non-weighted operation <code class="func">DigraphShortestPath</code> (<a href="chap5.html#X80E9D645843973A6"><span class="RefLink">5.4-24</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := EdgeWeightedDigraph([[2, 3], [4], [4], []],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[5, 1], [6], [11], []]);</span>
<immutable digraph with 4 vertices, 4 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeightedDigraphShortestPaths(D, 1);</span>
rec( distances := [ 0, 5, 1, 11 ], edges := [ fail, 1, 2, 1 ],
parents := [ fail, 1, 1, 2 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">D := EdgeWeightedDigraph([[2], [3], [1]], [[1], [2], [3]]);</span>
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeightedDigraphShortestPaths(D);</ | | |
