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 138 kB image not shown  

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);</span>
rec( distances := [ [ 0, 1, 3 ], [ 5, 0, 2 ], [ 3, 4, 0 ] ], 
  edges := [ [ fail, 1, 1 ], [ 1, fail, 1 ], [ 1, 1, fail ] ], 
  parents := [ [ fail, 1, 1 ], [ 2, fail, 2 ], [ 3, 3, fail ] ] )</pre></div>

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

<h5>6.3-6 EdgeWeightedDigraphShortestPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphShortestPath</code>( <var class="Arg">digraph</var>, <var class="Arg">source</var>, <var class="Arg">dest</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A pair of lists, or <code class="keyw">fail</code>.</p>

<p>If <var class="Arg">digraph</var> is an edge-weighted digraph with vertices <var class="Arg">source</var> and <var class="Arg">dest</var>, this operation returns a directed path from <var class="Arg">source</var> to <var class="Arg">dest</var> with the smallest possible total weight. The output is a pair of lists <code class="code">[v, a]</code> of the form described in <code class="func">DigraphPath</code> (<a href="chap5.html#X8039170B82A32257"><span class="RefLink">5.4-23</span></a>).</p>

<p>If <span class="SimpleMath"><var class="Arg">source</var> = <var class="Arg">dest</var></span> or no path exists, then <code class="keyw">fail</code> is returned.</p>

<p>If <var class="Arg">digraph</var> contains a negative-weighted cycle, then there is currently no applicable method for this attribute.</p>

<p>See <code class="func">EdgeWeightedDigraphShortestPaths</code> (<a href="chap6.html#X7EDB9C9A840F6A84"><span class="RefLink">6.3-5</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">EdgeWeightedDigraphShortestPath(D, 1, 4);</span>
[ [ 1, 2, 4 ], [ 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EdgeWeightedDigraphShortestPath(D, 3, 2);</span>
fail</pre></div>

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

<h5>6.3-7 DigraphMaximumFlow</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximumFlow</code>( <var class="Arg">digraph</var>, <var class="Arg">start</var>, <var class="Arg">destination</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of lists of integers.</p>

<p>If <var class="Arg">digraph</var> is an edge-weighted digraph with vertices <var class="Arg">start</var> and <var class="Arg">destination</var>, this returns a record representing the maximum flow from <var class="Arg">start</var> to <var class="Arg">destination</var> in the digraph.</p>

<p>A <em>flow</em> is a function from the weighted edges of <var class="Arg">digraph</var> to the positive real numbers, such that:</p>


<ul>
<li><p>Each edge's flow is no more than its weight;



</li>
<li><p>For each vertex other than <var class="Arg">start</var> and <var class="Arg">destination</var>, the sum of flows for all incoming edges is equal to the sum of flows for all outgoing edges;</p>

</li>
<li><p>The sum of flows of edges leaving <var class="Arg">start</var> is equal to the sum of flows of edges entering <var class="Arg">destination</var> (this sum is denoted <span class="SimpleMath">M</span>).</p>

</li>
</ul>
<p>A <em>maximum flow</em> is a flow that maximises the value of <span class="SimpleMath">M</span>.</p>

<p>The flow is represented as a list of lists where each entry is a number representing the flow on the edge in the corresponding position in <code class="code">OutNeighbours(<var class="Arg">digraph</var>)</code>. Note that the value <span class="SimpleMath">M</span> of the flow can be found with <code class="code">Sum(DigraphMaximumFlow(<var class="Arg">digraph</var>, <var class="Arg">start</var>, <var class="Arg">destination</var>)[<var class="Arg">start</var>])</code>.</p>

<p>This attribute is computed by an implementation of the push–relabel maximum flow algorithm, which has time complexity <span class="SimpleMath">O(v^2 e)</span> where <span class="SimpleMath">v</span> is the number of vertices of the digraph, and <span class="SimpleMath">e</span> is the number of edges.</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([[2, 2], [3], []], [[3, 2], [1], []]);</span>
<immutable multidigraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">flow := DigraphMaximumFlow(g, 1, 3);</span>
[ [ 1, 0 ], [ 1 ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Sum(flow[1]);</span>
1</pre></div>

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

<h5>6.3-8 RandomUniqueEdgeWeightedDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomUniqueEdgeWeightedDigraph</code>( [<var class="Arg">filt</var>, ]<var class="Arg">n</var>[, <var class="Arg">p</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An edge-weighted digraph.</p>

<p>This operation returns a random edge-weighted digraph.</p>

<p>Its behaviour is the same as that of <code class="func">RandomDigraph</code> (<a href="chap3.html#X86CF9F66788B2A24"><span class="RefLink">3.4-1</span></a>) but the returned digraph will additionally have the <code class="func">EdgeWeights</code> (<a href="chap6.html#X8639092D8689333D"><span class="RefLink">6.3-1</span></a>) attribute populated with random unique weights from the set <code class="code">[1 .. m]</code> where <code class="code">m</code> is the number of edges in the digraph.</p>

<p>If the optional first argument <var class="Arg">filt</var> is present, then this should specify the category or representation the digraph being created will belong to. For example, if <var class="Arg">filt</var> is <code class="func">IsMutableDigraph</code> (<a href="chap3.html#X7D7EDF83820ED6F5"><span class="RefLink">3.1-2</span></a>), then the digraph being created will be mutable, if <var class="Arg">filt</var> is <code class="func">IsImmutableDigraph</code> (<a href="chap3.html#X7CAFAA89804F80BD"><span class="RefLink">3.1-3</span></a>), then the digraph will be immutable. If the optional first argument <var class="Arg">filt</var> is not present, then <code class="func">IsImmutableDigraph</code> (<a href="chap3.html#X7CAFAA89804F80BD"><span class="RefLink">3.1-3</span></a>) is used by default.</p>

<p>If <var class="Arg">n</var> is a non-negative integer, then the returned digraph will have <var class="Arg">n</var> vertices. If the optional second argument <var class="Arg">p</var> is a float with value <span class="SimpleMath">0 ≤</span> <var class="Arg"> p </var> <span class="SimpleMath">≤ 1</span>, then an edge will exist between each pair of vertices with probability approximately <var class="Arg">p</var>. If <var class="Arg">p</var> is not specified, then a random probability will be assumed (chosen with uniform probability).</p>

<p>For more information on the arguments and behaviour of this operation, see <code class="func">RandomDigraph</code> (<a href="chap3.html#X86CF9F66788B2A24"><span class="RefLink">3.4-1</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomUniqueEdgeWeightedDigraph(5);</span>
<immutable digraph with 5 vertices, 21 edges>
--> --------------------

--> maximum size reached

--> --------------------

99%


¤ Dauer der Verarbeitung: 0.82 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.