Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 27.8.2025 mit Größe 249 kB

SSL chap5.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/chap5.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 5: Attributes and operations</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="chap5" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <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="chap4.html">[Previous Chapter]</a> <a href="chap6.html">[Next Chapter]</a> </div>

<a href="chap5_mj.html">[MathJax on]</a>
<a id="X8739F6CD78C90B14" name="X8739F6CD78C90B14"></a>
<div class="ChapSects"><a href="chap5.html#X8739F6CD78C90B14">5 Attributes and operations</a>
<div class="ContSect"> <a href="chap5.html#X7E814B6478F7D015">5.1 Vertices and edges</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7C45F7D878D896AC">5.1-1 DigraphVertices</a>
 <a href="chap5.html#X7C6F19B57CB2E882">5.1-2 DigraphNrVertices</a>
 <a href="chap5.html#X7D1C6A4D7ECEC317">5.1-3 DigraphEdges</a>
 <a href="chap5.html#X85E1CFDD7E164AD0">5.1-4 DigraphNrEdges</a>
 <a href="chap5.html#X7BD5D255809C859E">5.1-5 DigraphNrAdjacencies</a>
 <a href="chap5.html#X7E53E728795BB862">5.1-6 DigraphNrAdjacenciesWithoutLoops</a>
 <a href="chap5.html#X7BDABAF07917462B">5.1-7 DigraphNrLoops</a>
 <a href="chap5.html#X85D5E08280914EE4">5.1-8 DigraphSinks</a>
 <a href="chap5.html#X7F5C6268839BE98C">5.1-9 DigraphSources</a>
 <a href="chap5.html#X785C30378064CF47">5.1-10 DigraphTopologicalSort</a>
 <a href="chap5.html#X7CA91E4B7904F793">5.1-11 DigraphVertexLabel</a>
 <a href="chap5.html#X7E51F2FE87140B32">5.1-12 DigraphVertexLabels</a>
 <a href="chap5.html#X79FAEACC7F438C2F">5.1-13 DigraphEdgeLabel</a>
 <a href="chap5.html#X7C24851087D4A8FB">5.1-14 DigraphEdgeLabels</a>
 <a href="chap5.html#X7EFAF01B7A155157">5.1-15 DigraphInEdges</a>
 <a href="chap5.html#X7BECFE6687ECD028">5.1-16 DigraphOutEdges</a>
 <a href="chap5.html#X7BB8ED88835F07B4">5.1-17 IsDigraphEdge</a>
 <a href="chap5.html#X848FED0B7B4ACD1F">5.1-18 IsMatching</a>
 <a href="chap5.html#X7B7A67277B1C9A02">5.1-19 DigraphMaximalMatching</a>
 <a href="chap5.html#X78E9847A858788D1">5.1-20 DigraphMaximumMatching</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X7D7CE8328187D0DF">5.2 Neighbours and degree</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7DC2CD70830BEE60">5.2-1 AdjacencyMatrix</a>
 <a href="chap5.html#X87FA0A727CDB060B">5.2-2 CharacteristicPolynomial</a>
 <a href="chap5.html#X8507DC4F794780C1">5.2-3 BooleanAdjacencyMatrix</a>
 <a href="chap5.html#X7AFCE34A7A04D5C1">5.2-4 DigraphAdjacencyFunction</a>
 <a href="chap5.html#X7FDEBF3279759961">5.2-5 DigraphRange</a>
 <a href="chap5.html#X7E9880767AE68E00">5.2-6 OutNeighbours</a>
 <a href="chap5.html#X85C7AA5A81DA6E11">5.2-7 InNeighbours</a>
 <a href="chap5.html#X7F5ACE807D1BC2E2">5.2-8 OutDegrees</a>
 <a href="chap5.html#X7ADDFBFD7A365775">5.2-9 InDegrees</a>
 <a href="chap5.html#X7A09EB648070276D">5.2-10 OutDegreeOfVertex</a>
 <a href="chap5.html#X83315B0186850806">5.2-11 OutNeighboursOfVertex</a>
 <a href="chap5.html#X7C9CD0527CB9E6EF">5.2-12 InDegreeOfVertex</a>
 <a href="chap5.html#X7C0DA18B8291F302">5.2-13 InNeighboursOfVertex</a>
 <a href="chap5.html#X83271F607BD809CF">5.2-14 DigraphLoops</a>
 <a href="chap5.html#X7BEAE1C78267F54D">5.2-15 DegreeMatrix</a>
 <a href="chap5.html#X865390B08331936B">5.2-16 LaplacianMatrix</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X86424F167BD4F629">5.3 Orders</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7DDB33B686B3A2C6">5.3-1 PartialOrderDigraphMeetOfVertices</a>
 <a href="chap5.html#X824B9896798530F6">5.3-2 NonUpperSemimodularPair</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X8537F4088400DC48">5.4 Reachability and connectivity</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7F16B9EB8398459C">5.4-1 DigraphDiameter</a>
 <a href="chap5.html#X8104A9D37BCD8A05">5.4-2 DigraphShortestDistance</a>
 <a href="chap5.html#X81F99BC67E9D050F">5.4-3 DigraphShortestDistances</a>
 <a href="chap5.html#X8223718079D98A82">5.4-4 DigraphLongestDistanceFromVertex</a>
 <a href="chap5.html#X7CB7DDCD84621D38">5.4-5 DigraphDistanceSet</a>
 <a href="chap5.html#X79A3DA4078CF3C90">5.4-6 DigraphGirth</a>
 <a href="chap5.html#X8374B7357EC189C1">5.4-7 DigraphOddGirth</a>
 <a href="chap5.html#X84688B337BDDBB09">5.4-8 DigraphUndirectedGirth</a>
 <a href="chap5.html#X842FAD6A7B835977">5.4-9 DigraphConnectedComponents</a>
 <a href="chap5.html#X8484EC557810CD31">5.4-10 DigraphConnectedComponent</a>
 <a href="chap5.html#X833ECD6B7A84944C">5.4-11 DigraphStronglyConnectedComponents</a>
 <a href="chap5.html#X7EFCB5017D662254">5.4-12 DigraphStronglyConnectedComponent</a>
 <a href="chap5.html#X7F1B5A2782F598B1">5.4-13 DigraphBicomponents</a>
 <a href="chap5.html#X7DDE06E47E605DD7">5.4-14 ArticulationPoints</a>
 <a href="chap5.html#X803459AB86AB9BE2">5.4-15 MinimalCyclicEdgeCut</a>
 <a href="chap5.html#X84D5A125848BD800">5.4-16 Bridges</a>
 <a href="chap5.html#X865590147BD1C507">5.4-17 StrongOrientation</a>
 <a href="chap5.html#X853D0B0981A33433">5.4-18 DigraphPeriod</a>
 <a href="chap5.html#X864A31A8809F61C2">5.4-19 DigraphFloydWarshall</a>
 <a href="chap5.html#X7FBAB09E7C0BE5CF">5.4-20 IsReachable</a>
 <a href="chap5.html#X7ECD22877AEA89CC">5.4-21 IsDigraphPath</a>
 <a href="chap5.html#X7F255A2A84CB868C">5.4-22 VerticesReachableFrom</a>
 <a href="chap5.html#X8039170B82A32257">5.4-23 DigraphPath</a>
 <a href="chap5.html#X80E9D645843973A6">5.4-24 DigraphShortestPath</a>
 <a href="chap5.html#X7C45396C808308C4">5.4-25 DigraphRandomWalk</a>
 <a href="chap5.html#X787459247B2005E6">5.4-26 DigraphAbsorptionProbabilities</a>
 <a href="chap5.html#X7B0A62CF7F6F23E9">5.4-27 DigraphAbsorptionExpectedSteps</a>
 <a href="chap5.html#X7FE79CB278CE6991">5.4-28 Dominators</a>
 <a href="chap5.html#X7D66A0FB7F6100FB">5.4-29 DominatorTree</a>
 <a href="chap5.html#X7C0416FE7A69CA2C">5.4-30 IteratorOfPaths</a>
 <a href="chap5.html#X7ECD16838704FAAA">5.4-31 DigraphAllSimpleCircuits</a>
 <a href="chap5.html#X7C735C4E86BDD5F6">5.4-32 DigraphLongestSimpleCircuit</a>
 <a href="chap5.html#X7F9EDAA8854FB538">5.4-33 DigraphAllUndirectedSimpleCircuits</a>
 <a href="chap5.html#X7F0AC5617CE5E9DD">5.4-34 DigraphAllChordlessCycles</a>
 <a href="chap5.html#X805F15398735AD7D">5.4-35 FacialWalks</a>
 <a href="chap5.html#X870E04307C5F213F">5.4-36 DigraphLayers</a>
 <a href="chap5.html#X7B2E42327DA118E0">5.4-37 DigraphDegeneracy</a>
 <a href="chap5.html#X827C2BD17A4547E3">5.4-38 DigraphDegeneracyOrdering</a>
 <a href="chap5.html#X863FDFC4839A3B82">5.4-39 HamiltonianPath</a>
 <a href="chap5.html#X82F30D5681466BC6">5.4-40 NrSpanningTrees</a>
 <a href="chap5.html#X79352A8286D1D8F6">5.4-41 DigraphDijkstra</a>
 <a href="chap5.html#X794CD6037D4CF58C">5.4-42 DigraphCycleBasis</a>
 <a href="chap5.html#X835AAF9085BC9D84">5.4-43 DigraphIsKing</a>
 <a href="chap5.html#X7A17B9B67AC50561">5.4-44 DigraphKings</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X82F900777D677F55">5.5 Cayley graphs of groups</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7A000B1D7CCF7093">5.5-1 GroupOfCayleyDigraph</a>
 <a href="chap5.html#X8528455987D7D2BF">5.5-2 GeneratorsOfCayleyDigraph</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X790FD6647ECCAE3C">5.6 Associated semigroups</a>

<div class="ContSSBlock">
 <a href="chap5.html#X87D5C60D7B0C1309">5.6-1 AsSemigroup</a>
 <a href="chap5.html#X7C6D5EC27C51066B">5.6-2 AsSemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X7E2305528492DDC0">5.7 Planarity</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7DC478637E8C190D">5.7-1 KuratowskiPlanarSubdigraph</a>
 <a href="chap5.html#X78E8F09A8286501B">5.7-2 KuratowskiOuterPlanarSubdigraph</a>
 <a href="chap5.html#X84E3947E7D39BA64">5.7-3 PlanarEmbedding</a>
 <a href="chap5.html#X85DFB8C18088711F">5.7-4 OuterPlanarEmbedding</a>
 <a href="chap5.html#X806D2D6B85E0B269">5.7-5 SubdigraphHomeomorphicToK23</a>
 <a href="chap5.html#X876803517C34E1CD">5.7-6 DualPlanarGraph</a>
</div></div>
<div class="ContSect"> <a href="chap5.html#X7FF5E2D07D48647E">5.8 Hashing</a>

<div class="ContSSBlock">
 <a href="chap5.html#X7D97D990867B0149">5.8-1 DigraphHash</a>
</div></div>
</div>

<h3>5 Attributes and operations</h3>

<a id="X7E814B6478F7D015" name="X7E814B6478F7D015"></a>

<h4>5.1 Vertices and edges</h4>

<a id="X7C45F7D878D896AC" name="X7C45F7D878D896AC"></a>

<h5>5.1-1 DigraphVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers.

Returns the vertices of the digraph <var class="Arg">digraph</var>.

Note that the vertices of a digraph are always the range of positive integers from <code class="code">1</code> to the number of vertices of the graph, <code class="func">DigraphNrVertices</code> (<a href="chap5.html#X7C6F19B57CB2E882">5.1-2</a>). Arbitrary labels can be assigned to the vertices of a digraph; see <code class="func">DigraphVertexLabels</code> (<a href="chap5.html#X7E51F2FE87140B32">5.1-12</a>) for more information about this.

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "c", "a"]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphVertices(gr);
[ 1 .. 3 ]
gap> gr := Digraph([1, 2, 3, 4, 5, 7],
> [1, 2, 2, 4, 4],
> [2, 7, 5, 3, 7]);
<immutable digraph with 6 vertices, 5 edges>
gap> DigraphVertices(gr);
[ 1 .. 6 ]
gap> DigraphVertices(RandomDigraph(100));
[ 1 .. 100 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphVertices(D);
[ 1 .. 3 ]
</pre></div>

<a id="X7C6F19B57CB2E882" name="X7C6F19B57CB2E882"></a>

<h5>5.1-2 DigraphNrVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An non-negative integer.

Returns the number of vertices of the digraph <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "c", "a"]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphNrVertices(gr);
3
gap> gr := Digraph([1, 2, 3, 4, 5, 7],
> [1, 2, 2, 4, 4],
> [2, 7, 5, 3, 7]);
<immutable digraph with 6 vertices, 5 edges>
gap> DigraphNrVertices(gr);
6
gap> DigraphNrVertices(RandomDigraph(100));
100
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphNrVertices(D);
3
</pre></div>

<a id="X7D1C6A4D7ECEC317" name="X7D1C6A4D7ECEC317"></a>

<h5>5.1-3 DigraphEdges</h5>

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

Returns a list of edges of the digraph <var class="Arg">digraph</var>, where each edge is a pair of elements of <code class="func">DigraphVertices</code> (<a href="chap5.html#X7C45F7D878D896AC">5.1-1</a>) of the form <code class="code">[source,range]</code>.

The entries of <code class="code">DigraphEdges(</code><var class="Arg">digraph</var><code class="code">)</code> are in one-to-one correspondence with the edges of <var class="Arg">digraph</var>. Hence <code class="code">DigraphEdges(</code><var class="Arg">digraph</var><code class="code">)</code> is duplicate-free if and only if <var class="Arg">digraph</var> contains no multiple edges.

The entries of <code class="code">DigraphEdges</code> are guaranteed to be sorted by their first component (i.e. by the source of each edge), but they are not necessarily then sorted by the second component.

<div class="example"><pre>
gap> gr := DigraphFromDiSparse6String(".DaXbOe?EAM@G~");
<immutable multidigraph with 5 vertices, 16 edges>
gap> edges := ShallowCopy(DigraphEdges(gr));; Sort(edges);
gap> edges;
[ [ 1, 1 ], [ 1, 3 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 1 ],
 [ 2, 2 ], [ 2, 3 ], [ 2, 5 ], [ 3, 2 ], [ 3, 4 ], [ 3, 5 ],
 [ 4, 2 ], [ 4, 4 ], [ 4, 5 ], [ 5, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ]
</pre></div>

<a id="X85E1CFDD7E164AD0" name="X85E1CFDD7E164AD0"></a>

<h5>5.1-4 DigraphNrEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrEdges</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of edges of the digraph <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrEdges(gr);
15
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "a"]);
<immutable multidigraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(gr);
3
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(D);
3
</pre></div>

<a id="X7BD5D255809C859E" name="X7BD5D255809C859E"></a>

<h5>5.1-5 DigraphNrAdjacencies</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrAdjacencies</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of sets {u, v} of vertices of the digraph <var class="Arg">digraph</var>, such that either (u, v) or (v, u) is an edge. The following equality holds for any digraph <code class="code">D</code> with no multiple edges: <code class="code">DigraphNrAdjacencies(D) * 2 - DigraphNrLoops(D) = DigraphNrEdges(DigraphSymmetricClosure(D))</code>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacencies(gr);
13
gap> DigraphNrAdjacencies(gr) * 2 - DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
</pre></div>

<a id="X7E53E728795BB862" name="X7E53E728795BB862"></a>

<h5>5.1-6 DigraphNrAdjacenciesWithoutLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrAdjacenciesWithoutLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of sets {u, v} of vertices of the digraph <var class="Arg">digraph</var>, such that u ≠ v and either (u, v) or (v, u) is an edge. The following equality holds for any digraph <code class="code">D</code> with no multiple edges: <code class="code">DigraphNrAdjacenciesWithoutLoops(D) * 2 + DigraphNrLoops(D) = DigraphNrEdges(DigraphSymmetricClosure(D))</code>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacenciesWithoutLoops(gr);
10
gap> DigraphNrAdjacenciesWithoutLoops(gr) * 2 + DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
</pre></div>

<a id="X7BDABAF07917462B" name="X7BDABAF07917462B"></a>

<h5>5.1-7 DigraphNrLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

This function returns the number of loops of the digraph <var class="Arg">digraph</var>. See <code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>).

<div class="example"><pre>
gap> D := Digraph([[2, 3], [1, 4], [3, 3, 5], [], [2, 5]]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphNrLoops(D);
3
gap> D := EmptyDigraph(5);
<immutable empty digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
</pre></div>

<a id="X85D5E08280914EE4" name="X85D5E08280914EE4"></a>

<h5>5.1-8 DigraphSinks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSinks</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

This function returns a list of the sinks of the digraph <var class="Arg">digraph</var>. A sink of a digraph is a vertex with out-degree zero. See <code class="func">OutDegreeOfVertex</code> (<a href="chap5.html#X7A09EB648070276D">5.2-10</a>).

<div class="example"><pre>
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSinks(gr);
[ 3, 5 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSinks(D);
[ ]
</pre></div>

<a id="X7F5C6268839BE98C" name="X7F5C6268839BE98C"></a>

<h5>5.1-9 DigraphSources</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSources</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

This function returns an immutable list of the sources of the digraph <var class="Arg">digraph</var>. A source of a digraph is a vertex with in-degree zero. See <code class="func">InDegreeOfVertex</code> (<a href="chap5.html#X7C9CD0527CB9E6EF">5.2-12</a>).

<div class="example"><pre>
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSources(gr);
[ 1, 4 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSources(D);
[ ]
</pre></div>

<a id="X785C30378064CF47" name="X785C30378064CF47"></a>

<h5>5.1-10 DigraphTopologicalSort</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphTopologicalSort</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph whose only directed cycles are loops, then <code class="code">DigraphTopologicalSort</code> returns the vertices of <var class="Arg">digraph</var> ordered so that every edge's source appears no earlier in the list than its range. If the digraph digraph contains directed cycles of length greater than 1, then this operation returns fail.

See Section <a href="chap1.html#X84541F61810C741D">1.1-1</a> for the definition of a directed cycle, and the definition of a loop.

The method used for this attribute has complexity O(m+n) where m is the number of edges (counting multiple edges as one) and n is the number of vertices in the digraph.

<div class="example"><pre>
gap> D := Digraph([
> [2, 3], [], [4, 6], [5], [], [7, 8, 9], [], [], []]);
<immutable digraph with 9 vertices, 8 edges>
gap> DigraphTopologicalSort(D);
[ 2, 5, 4, 7, 8, 9, 6, 3, 1 ]
gap> D := Digraph(IsMutableDigraph, [[2, 3], [3], [4], []]);
<mutable digraph with 4 vertices, 4 edges>
gap> DigraphTopologicalSort(D);
[ 4, 3, 2, 1 ]
</pre></div>

<a id="X7CA91E4B7904F793" name="X7CA91E4B7904F793"></a>

<h5>5.1-11 DigraphVertexLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertexLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphVertexLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph, then the first operation returns the label of the vertex <var class="Arg">i</var>. The second operation can be used to set the label of the vertex <var class="Arg">i</var> in <var class="Arg">digraph</var> to the arbitrary GAP object <var class="Arg">obj</var>.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex <var class="Arg">i</var>, then the default value is <var class="Arg">i</var>.

If <var class="Arg">digraph</var> is a digraph created from a record with a component <code class="code">DigraphVertices</code>, then the labels of the vertices are set to the value of this component.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphVertexLabel(D, 3);
3
gap> D := Digraph(["a", "b", "c"], [], []);
<immutable empty digraph with 3 vertices>
gap> DigraphVertexLabel(D, 2);
"b"
gap> SetDigraphVertexLabel(D, 2, "d");
gap> DigraphVertexLabel(D, 2);
"d"
gap> D := InducedSubdigraph(D, [1, 2]);
<immutable empty digraph with 2 vertices>
gap> DigraphVertexLabel(D, 2);
"d"
gap> D := Digraph(IsMutableDigraph, ["e", "f", "g"], [], []);
<mutable empty digraph with 3 vertices>
gap> DigraphVertexLabel(D, 1);
"e"
gap> SetDigraphVertexLabel(D, 1, "h");
gap> DigraphVertexLabel(D, 1);
"h"
gap> InducedSubdigraph(D, [1, 2]);
<mutable empty digraph with 2 vertices>
gap> DigraphVertexLabel(D, 1);
"h"
</pre></div>

<a id="X7E51F2FE87140B32" name="X7E51F2FE87140B32"></a>

<h5>5.1-12 DigraphVertexLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertexLabels</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphVertexLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphVertexLabels</code> returns a copy of the labels of the vertices in <var class="Arg">digraph</var>. <code class="code">SetDigraphVertexLabels</code> can be used to set the labels of the vertices in <var class="Arg">digraph</var> to the list of arbitrary GAP objects <var class="Arg">list</var>, which must be of the same length as the number of vertices of <var class="Arg">digraph</var>.

If the list <var class="Arg">list</var> is immutable, then the vertex labels are set to a mutable copy of <var class="Arg">list</var>. Otherwise, the labels are set to exactly <var class="Arg">list</var>.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex <var class="Arg">i</var>, then the default value is <var class="Arg">i</var>.

If <var class="Arg">digraph</var> is a digraph created from a record with a component <code class="code">DigraphVertices</code>, then the labels of the vertices are set to the value of this component. As in the above, if the component is immutable then the digraph's vertex labels are set to a mutable copy of DigraphVertices. Otherwise, they are set to exactly DigraphVertices.

Induced subdigraphs, and other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphVertexLabels(D);
[ 1 .. 5 ]
gap> D := Digraph(["a", "b", "c"], [], []);
<immutable empty digraph with 3 vertices>
gap> DigraphVertexLabels(D);
[ "a", "b", "c" ]
gap> SetDigraphVertexLabel(D, 2, "d");
gap> DigraphVertexLabels(D);
[ "a", "d", "c" ]
gap> D := InducedSubdigraph(D, [1, 3]);
<immutable empty digraph with 2 vertices>
gap> DigraphVertexLabels(D);
[ "a", "c" ]
gap> D := Digraph(IsMutableDigraph, ["e", "f", "g"], [], []);
<mutable empty digraph with 3 vertices>
gap> SetDigraphVertexLabels(D, ["h", "i", "j"]);
gap> DigraphVertexLabels(D);
[ "h", "i", "j" ]
gap> InducedSubdigraph(D, [1, 3]);
<mutable empty digraph with 2 vertices>
gap> DigraphVertexLabels(D);
[ "h", "j" ]
</pre></div>

<a id="X79FAEACC7F438C2F" name="X79FAEACC7F438C2F"></a>

<h5>5.1-13 DigraphEdgeLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEdgeLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">j</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph without multiple edges, then the first operation returns the label of the edge from vertex <var class="Arg">i</var> to vertex <var class="Arg">j</var>. The second operation can be used to set the label of the edge between vertex <var class="Arg">i</var> and vertex <var class="Arg">j</var> to the arbitrary GAP object <var class="Arg">obj</var>.

The label of an edge can be changed an arbitrary number of times. If no label has been set for the edge, then the default value is <var class="Arg">1</var>.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their edge labels from their parents. See also <code class="func">DigraphEdgeLabels</code> (<a href="chap5.html#X7C24851087D4A8FB">5.1-14</a>).

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphEdgeLabel(D, 3, 1);
1
gap> SetDigraphEdgeLabel(D, 2, 5, [42]);
gap> DigraphEdgeLabel(D, 2, 5);
[ 42 ]
gap> D := InducedSubdigraph(D, [2, 5]);
<immutable digraph with 2 vertices, 3 edges>
gap> DigraphEdgeLabel(D, 1, 2);
[ 42 ]
gap> D := ChainDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 4 edges>
gap> DigraphEdgeLabel(D, 2, 3);
1
gap> SetDigraphEdgeLabel(D, 4, 5, [1729]);
gap> DigraphEdgeLabel(D, 4, 5);
[ 1729 ]
gap> InducedSubdigraph(D, [4, 5]);
<mutable digraph with 2 vertices, 1 edge>
gap> DigraphEdgeLabel(D, 1, 2);
[ 1729 ]
</pre></div>

<a id="X7C24851087D4A8FB" name="X7C24851087D4A8FB"></a>

<h5>5.1-14 DigraphEdgeLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEdgeLabels</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">labels</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph without multiple edges, then <code class="code">DigraphEdgeLabels</code> returns a copy of the labels of the edges in <var class="Arg">digraph</var> as a list of lists <code class="code">labels</code> such that <code class="code">labels[i][j]</code> is the label on the edge from vertex <code class="code">i</code> to vertex <code class="code">OutNeighbours(digraph)[i][j]</code>. <code class="code">SetDigraphEdgeLabels</code> can be used to set the labels of the edges in <var class="Arg">digraph</var> without multiple edges to the list <var class="Arg">labels</var> of lists of arbitrary GAP objects such that <code class="code">list[i][j]</code> is the label on the edge from vertex <code class="code">i</code> to the vertex <code class="code">OutNeighbours(digraph>[i][j]</code>. Alternatively <code class="code">SetDigraphEdgeLabels</code> can be called with binary function <var class="Arg">func</var> that as its second argument that when passed two vertices <code class="code">i</code> and <code class="code">j</code> returns the label for the edge between vertex <code class="code">i</code> and vertex <code class="code">j</code>.

The label of an edge can be changed an arbitrary number of times. If no label has been set for an edge, then the default value is <code class="code">1</code>.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ 1, 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]
gap> SetDigraphEdgeLabel(D, 2, 1, "d");
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ "d", 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]
gap> D := InducedSubdigraph(D, [1, 2, 3]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ "d", 1 ], [ 1 ] ]
gap> OutNeighbours(D);
[ [ 3 ], [ 1, 3 ], [ 1 ] ]
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> DigraphEdgeLabels(D);
[ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ]
gap> SetDigraphEdgeLabel(D, 2, 4, "a");
gap> DigraphEdgeLabels(D);
[ [ 1, 1, 1 ], [ 1, "a", 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ]
gap> InducedSubdigraph(D, [1, 2, 3, 4]);
<mutable digraph with 4 vertices, 8 edges>
gap> DigraphEdgeLabels(D);
[ [ 1, 1 ], [ 1, "a" ], [ 1, 1 ], [ 1, 1 ] ]
gap> OutNeighbors(D);
[ [ 3, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 2 ] ]
</pre></div>

<a id="X7EFAF01B7A155157" name="X7EFAF01B7A155157"></a>

<h5>5.1-15 DigraphInEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphInEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of edges.

<code class="code">DigraphInEdges</code> returns the list of all edges of <var class="Arg">digraph</var> which have <var class="Arg">vertex</var> as their range.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [3, 3], [4, 4], [1, 1]]);
<immutable multidigraph with 4 vertices, 8 edges>
gap> DigraphInEdges(D, 2);
[ [ 1, 2 ], [ 1, 2 ] ]
</pre></div>

<a id="X7BECFE6687ECD028" name="X7BECFE6687ECD028"></a>

<h5>5.1-16 DigraphOutEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOutEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of edges.

<code class="code">DigraphOutEdges</code> returns the list of all edges of <var class="Arg">digraph</var> which have <var class="Arg">vertex</var> as their source.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [3, 3], [4, 4], [1, 1]]);
<immutable multidigraph with 4 vertices, 8 edges>
gap> DigraphOutEdges(D, 2);
[ [ 2, 3 ], [ 2, 3 ] ]
</pre></div>

<a id="X7BB8ED88835F07B4" name="X7BB8ED88835F07B4"></a>

<h5>5.1-17 IsDigraphEdge</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEdge</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEdge</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

In the first form, this function returns <code class="keyw">true</code> if and only if the list <var class="Arg">list</var> specifies an edge in the digraph <var class="Arg">digraph</var>. Specifically, this operation returns <code class="keyw">true</code> if <var class="Arg">list</var> is a pair of positive integers where <var class="Arg">list</var><code class="code">[1]</code> is the source and <var class="Arg">list</var><code class="code">[2]</code> is the range of an edge in <var class="Arg">digraph</var>, and <code class="keyw">false</code> otherwise.

The second form simply returns <code class="keyw">true</code> if <code class="code">[<var class="Arg">u</var>, <var class="Arg">v</var>]</code> is an edge in <var class="Arg">digraph</var>, and <code class="keyw">false</code> otherwise.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [6], [], [3], [], [1]]);
<immutable multidigraph with 6 vertices, 5 edges>
gap> IsDigraphEdge(D, [1, 1]);
false
gap> IsDigraphEdge(D, [1, 2]);
true
gap> IsDigraphEdge(D, [1, 8]);
false
</pre></div>

<a id="X848FED0B7B4ACD1F" name="X848FED0B7B4ACD1F"></a>

<h5>5.1-18 IsMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMaximalMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMaximumMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPerfectMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">list</var> is a list of pairs of vertices of <var class="Arg">digraph</var>, then <code class="code">IsMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a matching of <var class="Arg">digraph</var>. The operation <code class="code">IsMaximalMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a maximal matching, <code class="code">IsMaximumMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a maximum matching and <code class="code">IsPerfectMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a perfect, matching of <var class="Arg">digraph</var>, respectively. Otherwise, each of these operations return <code class="keyw">false</code>.

A matching <code class="code">M</code> of a digraph <var class="Arg">digraph</var> is a subset of the edges of <var class="Arg">digraph</var>, i.e. <code class="code">DigraphEdges(<var class="Arg">digraph</var>)</code>, such that no pair of distinct edges in <code class="code">M</code> are incident to the same vertex of <var class="Arg">digraph</var>. Note that this definition allows a matching to contain loops. See <code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>). The matching <code class="code">M</code> is maximal if it is contained in no larger matching of the digraph, is maximum if it has the greatest cardinality among all matchings and is perfect if every vertex of the digraph is incident to an edge in the matching. Every maximum or perfect matching is maximal. Note, however, that not every perfect matching of digraphs with loops is maximum.

<div class="example"><pre>
gap> D := Digraph([[1, 2], [1, 2], [2, 3, 4], [3, 5], [1]]);
<immutable digraph with 5 vertices, 10 edges>
gap> IsMatching(D, [[2, 1], [3, 2]]);
false
gap> edges := [[3, 2]];;
gap> IsMatching(D, edges);
true
gap> IsMaximalMatching(D, edges);
false
gap> edges := [[2, 1], [3, 4]];;
gap> IsMaximalMatching(D, edges);
true
gap> IsPerfectMatching(D, edges);
false
gap> edges := [[1, 2], [3, 3], [4, 5]];;
gap> IsPerfectMatching(D, edges);
true
gap> IsMaximumMatching(D, edges);
false
gap> edges := [[1, 1], [2, 2], [3, 3], [4, 5]];;
gap> IsMaximumMatching(D, edges);
true
</pre></div>

<a id="X7B7A67277B1C9A02" name="X7B7A67277B1C9A02"></a>

<h5>5.1-19 DigraphMaximalMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of pairs of vertices.

This function returns a maximal matching of the digraph <var class="Arg">digraph</var>.

For the definition of a maximal matching, see <code class="func">IsMaximalMatching</code> (<a href="chap5.html#X848FED0B7B4ACD1F">5.1-18</a>).

<div class="example"><pre>
gap> D := DigraphFromDiSparse6String(".IeAoXCJU@|SHAe?d");
<immutable digraph with 10 vertices, 13 edges>
gap> M := DigraphMaximalMatching(D);; IsMaximalMatching(D, M);
true
gap> D := RandomDigraph(100);;
gap> IsMaximalMatching(D, DigraphMaximalMatching(D));
true
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> IsMaximalMatching(D, DigraphMaximalMatching(D));
true
</pre></div>

<a id="X78E9847A858788D1" name="X78E9847A858788D1"></a>

<h5>5.1-20 DigraphMaximumMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximumMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of pairs of vertices.

This function returns a maximum matching of the digraph <var class="Arg">digraph</var>.

For the definition of a maximum matching, see <code class="func">IsMaximumMatching</code> (<a href="chap5.html#X848FED0B7B4ACD1F">5.1-18</a>). If <var class="Arg">digraph</var> is bipartite (see <code class="func">IsBipartiteDigraph</code> (<a href="chap6.html#X860CFB0C8665F356">6.2-3</a>)), then the algorithm used has complexity <code class="code">O(m*sqrt(n))</code>. Otherwise for general graphs the complexity is <code class="code">O(m*n*log(n))</code>. Here <code class="code">n</code> is the number of vertices and <code class="code">m</code> is the number of edges.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&I@EA_A?AdDp[_c??OO");
<immutable digraph with 10 vertices, 23 edges>
gap> M := DigraphMaximumMatching(D);; IsMaximalMatching(D, M);
true
gap> Length(M);
5
gap> D := Digraph([[5, 6, 7, 8], [6, 7, 8], [7, 8], [8], 
> [], [], [], []]);;
gap> M := DigraphMaximumMatching(D);
[ [ 1, 5 ], [ 2, 6 ], [ 3, 7 ], [ 4, 8 ] ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> M := DigraphMaximumMatching(D);;
gap> IsMaximalMatching(D, M);
true
gap> Length(M);
9
</pre></div>

<a id="X7D7CE8328187D0DF" name="X7D7CE8328187D0DF"></a>

<h4>5.2 Neighbours and degree</h4>

<a id="X7DC2CD70830BEE60" name="X7DC2CD70830BEE60"></a>

<h5>5.2-1 AdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AdjacencyMatrix</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">‣ AdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A square matrix of non-negative integers.

This function returns the adjacency matrix <code class="code">mat</code> of the digraph <var class="Arg">digraph</var>. The value of the matrix entry <code class="code">mat[i][j]</code> is the number of edges in <var class="Arg">digraph</var> with source <code class="code">i</code> and range <code class="code">j</code>. If <var class="Arg">digraph</var> has no vertices, then the empty list is returned.

The function <code class="code">AdjacencyMatrix</code> returns an immutable list of lists, whereas the function <code class="code">AdjacencyMatrixMutableCopy</code> returns a copy of <code class="code">AdjacencyMatrix</code> that is a mutable list of mutable lists.

<div class="example"><pre>
gap> gr := Digraph([
> [2, 2, 2], [1, 3, 6, 8, 9, 10], [4, 6, 8],
> [1, 2, 3, 9], [3, 3], [3, 5, 6, 10], [1, 2, 7],
> [1, 2, 3, 10, 5, 6, 10], [1, 3, 4, 5, 8, 10],
> [2, 3, 4, 6, 7, 10]]);
<immutable multidigraph with 10 vertices, 44 edges>
gap> mat := AdjacencyMatrix(gr);;
gap> Display(mat);
[ [ 0, 3, 0, 0, 0, 0, 0, 0, 0, 0 ],
 [ 1, 0, 1, 0, 0, 1, 0, 1, 1, 1 ],
 [ 0, 0, 0, 1, 0, 1, 0, 1, 0, 0 ],
 [ 1, 1, 1, 0, 0, 0, 0, 0, 1, 0 ],
 [ 0, 0, 2, 0, 0, 0, 0, 0, 0, 0 ],
 [ 0, 0, 1, 0, 1, 1, 0, 0, 0, 1 ],
 [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 ],
 [ 1, 1, 1, 0, 1, 1, 0, 0, 0, 2 ],
 [ 1, 0, 1, 1, 1, 0, 0, 1, 0, 1 ],
 [ 0, 1, 1, 1, 0, 1, 1, 0, 0, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> Display(AdjacencyMatrix(D));
[ [ 0, 1, 0 ],
 [ 0, 0, 1 ],
 [ 1, 0, 0 ] ]
</pre></div>

<a id="X87FA0A727CDB060B" name="X87FA0A727CDB060B"></a>

<h5>5.2-2 CharacteristicPolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CharacteristicPolynomial</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A polynomial with integer coefficients.

This function returns the characteristic polynomial of the digraph <var class="Arg">digraph</var>. That is it returns the characteristic polynomial of the adjacency matrix of the digraph <var class="Arg">digraph</var>

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 2], [1, 3, 6, 8, 9, 10], [4, 6, 8],
> [1, 2, 3, 9], [3, 3], [3, 5, 6, 10], [1, 2, 7],
> [1, 2, 3, 10, 5, 6, 10], [1, 3, 4, 5, 8, 10],
> [2, 3, 4, 6, 7, 10]]);
<immutable multidigraph with 10 vertices, 44 edges>
gap> CharacteristicPolynomial(D);
x_1^10-3*x_1^9-7*x_1^8-x_1^7+14*x_1^6+x_1^5-26*x_1^4+51*x_1^3-10*x_1^2\
+18*x_1-30
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> CharacteristicPolynomial(D);
x_1^5-10*x_1^3-20*x_1^2-15*x_1-4
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> CharacteristicPolynomial(D);
x_1^3-1
</pre></div>

<a id="X8507DC4F794780C1" name="X8507DC4F794780C1"></a>

<h5>5.2-3 BooleanAdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BooleanAdjacencyMatrix</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">‣ BooleanAdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
--> --------------------

--> maximum size reached

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

quality100%

¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.27Bemerkung: (vorverarbeitet) ¤

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.