Quelle chap8.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/chap8.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 8: Finding cliques and independent sets</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="chap8" 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="chap7.html">[Previous Chapter]</a> <a href="chap9.html">[Next Chapter]</a> </div>

<a href="chap8_mj.html">[MathJax on]</a>
<a id="X7A7E0B957932DF44" name="X7A7E0B957932DF44"></a>
<div class="ChapSects"><a href="chap8.html#X7A7E0B957932DF44">8 Finding cliques and independent sets</a>
<div class="ContSect"> <a href="chap8.html#X788474E38446039B">8.1 Finding cliques</a>

<div class="ContSSBlock">
 <a href="chap8.html#X80670E3E7C36183F">8.1-1 IsClique</a>
 <a href="chap8.html#X7A3BC9FF8169ABCD">8.1-2 CliquesFinder</a>
 <a href="chap8.html#X789854AC7B466402">8.1-3 DigraphClique</a>
 <a href="chap8.html#X84EA2F9482B8D4AF">8.1-4 DigraphMaximalCliques</a>
 <a href="chap8.html#X78427A8B81FEB457">8.1-5 CliqueNumber</a>
</div></div>
<div class="ContSect"> <a href="chap8.html#X7E31253287708348">8.2 Finding independent sets</a>

<div class="ContSSBlock">
 <a href="chap8.html#X790733B67B0BC894">8.2-1 IsIndependentSet</a>
 <a href="chap8.html#X84350678782BFAB7">8.2-2 DigraphIndependentSet</a>
 <a href="chap8.html#X7D2C78EB81A798A9">8.2-3 DigraphMaximalIndependentSets</a>
</div></div>
</div>

<h3>8 Finding cliques and independent sets</h3>

In Digraphs, a clique of a digraph is a set of mutually adjacent vertices of the digraph, and an independent set is a set of mutually non-adjacent vertices of the digraph. A maximal clique is a clique which is not properly contained in another clique, and a maximal independent set is an independent set which is not properly contained in another independent set. Using this definition in Digraphs, cliques and independent sets are both permitted, but not required, to contain vertices at which there is a loop. Another name for a clique is a complete subgraph.

Digraphs provides extensive functionality for computing cliques and independent sets of a digraph, whether maximal or not. The fundamental algorithm used in most of the methods in Digraphs to calculate cliques and independent sets is a version of the Bron-Kerbosch algorithm. Calculating the cliques and independent sets of a digraph is a well-known and hard problem, and searching for cliques or independent sets in a digraph can be very lengthy, even for a digraph with a small number of vertices. Digraphs uses several strategies to increase the performance of these calculations.

From the definition of cliques and independent sets, it follows that the presence of loops and multiple edges in a digraph is irrelevant to the existence of cliques and independent sets in the digraph. See <code class="func">DigraphHasLoops</code> (<a href="chap6.html#X7D92935C7D535187">6.2-1</a>) and <code class="func">IsMultiDigraph</code> (<a href="chap6.html#X7BB84CFC7E8B2B26">6.2-11</a>) for more information about these properties. Therefore given a digraph <var class="Arg">digraph</var>, the cliques and independent sets of <var class="Arg">digraph</var> are equal to the cliques and independent sets of the digraph:

<ul>
<li><code class="code">DigraphRemoveLoops(DigraphRemoveAllMultipleEdges(</code><var class="Arg">digraph</var><code class="code">))</code>.

</li>
</ul>
See <code class="func">DigraphRemoveLoops</code> (<a href="chap3.html#X79324AF7818C0C02">3.3-25</a>) and <code class="func">DigraphRemoveAllMultipleEdges</code> (<a href="chap3.html#X7DCCD0247897A3DE">3.3-26</a>) for more information about these attributes. Furthermore, the cliques of this digraph are equal to the cliques of the digraph formed by removing any edge <code class="code">[u,v]</code> for which the corresponding reverse edge <code class="code">[v,u]</code> is not present. Therefore, overall, the cliques of <var class="Arg">digraph</var> are equal to the cliques of the symmetric digraph:

<ul>
<li><code class="code">MaximalSymmetricSubdigraphWithoutLoops(</code><var class="Arg">digraph</var><code class="code">)</code>.

</li>
</ul>
See <code class="func">MaximalSymmetricSubdigraphWithoutLoops</code> (<a href="chap3.html#X829E3EAC7C4B3B1E">3.3-5</a>) for more information about this. The <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) of this symmetric digraph contains the automorphism group of <var class="Arg">digraph</var> as a subgroup. By performing the search for maximal cliques with the help of this larger automorphism group to reduce the search space, the computation time may be reduced. The functions and attributes which return representatives of cliques of <var class="Arg">digraph</var> will return orbit representatives of cliques under the action of the automorphism group of the maximal symmetric subdigraph without loops on sets of vertices.

The independent sets of a digraph are equal to the independent sets of the <code class="func">DigraphSymmetricClosure</code> (<a href="chap3.html#X874883DD7DD450C4">3.3-12</a>). Therefore, overall, the independent sets of <var class="Arg">digraph</var> are equal to the independent sets of the symmetric digraph:

<ul>
<li><code class="code">DigraphSymmetricClosure(DigraphRemoveLoops(DigraphRemoveAllMultipleEdges( </code><var class="Arg">digraph</var><code class="code">)))</code>.

</li>
</ul>
Again, the automorphism group of this symmetric digraph contains the automorphism group of <var class="Arg">digraph</var>. Since a search for independent sets is equal to a search for cliques in the <code class="func">DigraphDual</code> (<a href="chap3.html#X7F71D99D852B130F">3.3-11</a>), the methods used in Digraphs usually transform a search for independent sets into a search for cliques, as described above. The functions and attributes which return representatives of independent sets of <var class="Arg">digraph</var> will return orbit representatives of independent sets under the action of the automorphism group of the symmetric closure of the digraph formed by removing loops and multiple edges.

Please note that in Digraphs, cliques and independent sets are not required to be maximal. Some authors use the word clique to mean maximal clique, and some authors use the phrase independent set to mean maximal independent set, but please note that Digraphs does not use this definition.

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

<h4>8.1 Finding cliques</h4>

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

<h5>8.1-1 IsClique</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsClique</code>( <var class="Arg">digraph</var>, <var class="Arg">l</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">‣ IsMaximalClique</code>( <var class="Arg">digraph</var>, <var class="Arg">l</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">l</var> is a duplicate-free list of vertices of <var class="Arg">digraph</var>, then <code class="code">IsClique(</code><var class="Arg">digraph</var><code class="code">,</code><var class="Arg">l</var><code class="code">)</code> returns <code class="keyw">true</code> if <var class="Arg">l</var> is a clique of <var class="Arg">digraph</var> and <code class="keyw">false</code> if it is not. Similarly, <code class="code">IsMaximalClique(</code><var class="Arg">digraph</var><code class="code">,</code><var class="Arg">l</var><code class="code">)</code> returns <code class="keyw">true</code> if <var class="Arg">l</var> is a maximal clique of <var class="Arg">digraph</var> and <code class="keyw">false</code> if it is not.

A clique of a digraph is a set of mutually adjacent vertices of the digraph. A maximal clique is a clique that is not properly contained in another clique. A clique is permitted, but not required, to contain vertices at which there is a loop.

<div class="example"><pre>
gap> D := CompleteDigraph(4);;
gap> IsClique(D, [1, 3, 2]);
true
gap> IsMaximalClique(D, [1, 3, 2]);
false
gap> IsMaximalClique(D, DigraphVertices(D));
true
gap> D := Digraph([[1, 2, 4, 4], [1, 3, 4], [2, 1], [1, 2]]);
<immutable multidigraph with 4 vertices, 11 edges>
gap> IsClique(D, [2, 3, 4]);
false
gap> IsMaximalClique(D, [1, 2, 4]);
true
gap> D := CompleteDigraph(IsMutableDigraph, 4);;
gap> IsClique(D, [1, 3, 2]);
true</pre></div>

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

<h5>8.1-2 CliquesFinder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CliquesFinder</code>( <var class="Arg">digraph</var>, <var class="Arg">hook</var>, <var class="Arg">user_param</var>, <var class="Arg">limit</var>, <var class="Arg">include</var>, <var class="Arg">exclude</var>, <var class="Arg">max</var>, <var class="Arg">size</var>, <var class="Arg">reps</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: The argument <var class="Arg">user_param</var>.

This function finds cliques of the digraph <var class="Arg">digraph</var> subject to the conditions imposed by the other arguments as described below. Note that a clique is represented by the immutable list of the vertices that it contains.

Let <code class="code">G</code> denote the automorphism group of the maximal symmetric subdigraph of <var class="Arg">digraph</var> without loops (see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) and <code class="func">MaximalSymmetricSubdigraphWithoutLoops</code> (<a href="chap3.html#X829E3EAC7C4B3B1E">3.3-5</a>)).

<dl>
<dt><var class="Arg">hook</var></dt>
<dd>This argument should be a function or <code class="keyw">fail</code>.

If <var class="Arg">hook</var> is a function, then it should have two arguments <var class="Arg">user_param</var> (see below) and a clique <code class="code">c</code>. The function <code class="code"><var class="Arg">hook</var>(<var class="Arg">user_param</var>, c)</code> is called every time a new clique <code class="code">c</code> is found by <code class="code">CliquesFinder</code>.

If <var class="Arg">hook</var> is <code class="keyw">fail</code>, then a default function is used that simply adds every new clique found by <code class="code">CliquesFinder</code> to <var class="Arg">user_param</var>, which must be a list in this case.

</dd>
<dt><var class="Arg">user_param</var></dt>
<dd>If <var class="Arg">hook</var> is a function, then <var class="Arg">user_param</var> can be any GAP object. The object <var class="Arg">user_param</var> is used as the first argument for the function <var class="Arg">hook</var>. For example, <var class="Arg">user_param</var> might be a list, and <code class="code"><var class="Arg">hook</var>(<var class="Arg">user_param</var>, c)</code> might add the size of the clique <code class="code">c</code> to the list <var class="Arg">user_param</var>.

If the value of <var class="Arg">hook</var> is <code class="keyw">fail</code>, then the value of <var class="Arg">user_param</var> must be a list.

</dd>
<dt><var class="Arg">limit</var></dt>
<dd>This argument should be a positive integer or <code class="keyw">infinity</code>. <code class="code">CliquesFinder</code> will return after it has found <var class="Arg">limit</var> cliques or the search is complete.

</dd>
<dt><var class="Arg">include</var> and <var class="Arg">exclude</var></dt>
<dd>These arguments should each be a (possibly empty) duplicate-free list of vertices of <var class="Arg">digraph</var> (i.e. positive integers less than the number of vertices of <var class="Arg">digraph</var>).

<code class="code">CliquesFinder</code> will only look for cliques containing all of the vertices in <var class="Arg">include</var> and containing none of the vertices in <var class="Arg">exclude</var>.

Note that the search may be much more efficient if each of these lists is invariant under the action of <code class="code">G</code> on sets of vertices.

</dd>
<dt><var class="Arg">max</var></dt>
<dd>This argument should be <code class="keyw">true</code> or <code class="keyw">false</code>. If <var class="Arg">max</var> is true then <code class="code">CliquesFinder</code> will only search for maximal cliques. If <code class="keyw">max</code> is <code class="keyw">false</code> then non-maximal cliques may be found.

</dd>
<dt><var class="Arg">size</var></dt>
<dd>This argument should be <code class="keyw">fail</code> or a positive integer. If <var class="Arg">size</var> is a positive integer then <code class="code">CliquesFinder</code> will only search for cliques that contain precisely <var class="Arg">size</var> vertices. If <var class="Arg">size</var> is <code class="keyw">fail</code> then cliques of any size may be found.

</dd>
<dt><var class="Arg">reps</var></dt>
<dd>This argument should be <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">reps</var> is <code class="keyw">true</code> then the arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> are each required to be invariant under the action of <code class="code">G</code> on sets of vertices. In this case, <code class="code">CliquesFinder</code> will find representatives of the orbits of the desired cliques under the action of <code class="code">G</code>, although representatives may be returned that are in the same orbit. If <var class="Arg">reps</var> is false then <code class="code">CliquesFinder</code> will not take this into consideration.

For a digraph such that <code class="code">G</code> is non-trivial, the search for clique representatives can be much more efficient than the search for all cliques.

</dd>
</dl>
This function uses a version of the Bron-Kerbosch algorithm.

<div class="example"><pre>
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> user_param := [];;
gap> f := function(a, b) # Calculate size of clique
> AddSet(user_param, Size(b));
> end;;
gap> CliquesFinder(D, f, user_param, infinity, [], [], false, fail,
> true);
[ 1, 2, 3, 4, 5 ]
gap> CliquesFinder(D, fail, [], 5, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ], [ 2, 4, 5 ], [ 1, 2, 4, 5 ] ]
gap> CliquesFinder(D, fail, [], 2, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ] ]
gap> CliquesFinder(D, fail, [], infinity, [], [], true, 5, false);
[ [ 1, 2, 3, 4, 5 ] ]
gap> CliquesFinder(D, fail, [], infinity, [1, 3], [], false, 3, false);
[ [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 5 ] ]
gap> CliquesFinder(D, fail, [], infinity, [1, 3], [], true, 3, false);
[ ]
gap> D := CompleteDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 20 edges>
gap> user_param := [];;
gap> f := function(a, b) # Calculate size of clique
> AddSet(user_param, Size(b));
> end;;
gap> CliquesFinder(D, f, user_param, infinity, [], [], false, fail,
> true);
[ 1, 2, 3, 4, 5 ]
gap> CliquesFinder(D, fail, [], 5, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ], [ 2, 4, 5 ], [ 1, 2, 4, 5 ] ]
gap> CliquesFinder(D, fail, [], 2, [2, 4], [3], false, fail, false);
[ [ 2, 4 ], [ 1, 2, 4 ] ]
gap> CliquesFinder(D, fail, [], infinity, [], [], true, 5, false);
[ [ 1, 2, 3, 4, 5 ] ]
gap> CliquesFinder(D, fail, [], infinity, [1, 3], [], false, 3, false);
[ [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 5 ] ]
gap> CliquesFinder(D, fail, [], infinity, [1, 3], [], true, 3, false);
[ ]</pre></div>

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

<h5>8.1-3 DigraphClique</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphClique</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">size</var>]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalClique</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">size</var>]]] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: An immutable list of positive integers, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph, then these functions returns a clique of <var class="Arg">digraph</var> if one exists that satisfies the arguments, else it returns <code class="keyw">fail</code>. A clique is defined by the set of vertices that it contains; see <code class="func">IsClique</code> (<a href="chap8.html#X80670E3E7C36183F">8.1-1</a>) and <code class="func">IsMaximalClique</code> (<a href="chap8.html#X80670E3E7C36183F">8.1-1</a>).

The optional arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be a (possibly empty) duplicate-free list of vertices of <var class="Arg">digraph</var>, and the optional argument <var class="Arg">size</var> must be a positive integer. By default, <var class="Arg">include</var> and <var class="Arg">exclude</var> are empty. These functions will search for a clique of <var class="Arg">digraph</var> that includes the vertices of <var class="Arg">include</var> but does not include any vertices in <var class="Arg">exclude</var>; if the argument <var class="Arg">size</var> is supplied, then additionally the clique will be required to contain precisely <var class="Arg">size</var> vertices.

If <var class="Arg">include</var> is not a clique, then these functions return <code class="keyw">fail</code>. Otherwise, the functions behave in the following way, depending on the number of arguments:

<dl>
<dt>One or two arguments</dt>
<dd>If one or two arguments are supplied, then <code class="code">DigraphClique</code> and <code class="code">DigraphMaximalClique</code> greedily enlarge the clique <var class="Arg">include</var> until it cannot continue. The result is guaranteed to be a maximal clique. This may or may not return an answer more quickly than using <code class="func">DigraphMaximalCliques</code> (<a href="chap8.html#X84EA2F9482B8D4AF">8.1-4</a>) with a limit of 1.

</dd>
<dt>Three arguments</dt>
<dd>If three arguments are supplied, then <code class="code">DigraphClique</code> greedily enlarges the clique <var class="Arg">include</var> until it cannot continue, although this clique may not be maximal.

Given three arguments, <code class="code">DigraphMaximalClique</code> returns the maximal clique returned by <code class="code">DigraphMaximalCliques(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1)</code> if one exists, else <code class="keyw">fail</code>.

</dd>
<dt>Four arguments</dt>
<dd>If four arguments are supplied, then <code class="code">DigraphClique</code> returns the clique returned by <code class="code">DigraphCliques(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1, </code><var class="Arg">size</var><code class="code">)</code> if one exists, else <code class="keyw">fail</code>. This clique may not be maximal.

Given four arguments, <code class="code">DigraphMaximalClique</code> returns the maximal clique returned by <code class="code">DigraphMaximalCliques(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1, </code><var class="Arg">size</var><code class="code">)</code> if one exists, else <code class="keyw">fail</code>.

</dd>
</dl>

<div class="example"><pre>
gap> D := Digraph([[2, 3, 4], [1, 3], [1, 2], [1, 5], []]);
<immutable digraph with 5 vertices, 9 edges>
gap> IsSymmetricDigraph(D);
false
gap> DigraphClique(D);
[ 5 ]
gap> DigraphMaximalClique(D);
[ 5 ]
gap> DigraphClique(D, [1, 2]);
[ 1, 2, 3 ]
gap> DigraphMaximalClique(D, [1, 3]);
[ 1, 3, 2 ]
gap> DigraphClique(D, [1], [2]);
[ 1, 4 ]
gap> DigraphMaximalClique(D, [1], [3, 4]);
fail
gap> DigraphClique(D, [1, 5]);
fail
gap> DigraphClique(D, [], [], 2);
[ 1, 2 ]
gap> D := Digraph(IsMutableDigraph,
> [[2, 3, 4], [1, 3], [1, 2], [1, 5], []]);
<mutable digraph with 5 vertices, 9 edges>
gap> IsSymmetricDigraph(D);
false
gap> DigraphClique(D);
[ 5 ]</pre></div>

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

<h5>8.1-4 DigraphMaximalCliques</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalCliques</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalCliquesReps</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphCliques</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphCliquesReps</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalCliquesAttr</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">‣ DigraphMaximalCliquesRepsAttr</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of lists of positive integers.

If <var class="Arg">digraph</var> is digraph, then these functions and attributes use <code class="func">CliquesFinder</code> (<a href="chap8.html#X7A3BC9FF8169ABCD">8.1-2</a>) to return cliques of <var class="Arg">digraph</var>. A clique is defined by the set of vertices that it contains; see <code class="func">IsClique</code> (<a href="chap8.html#X80670E3E7C36183F">8.1-1</a>) and <code class="func">IsMaximalClique</code> (<a href="chap8.html#X80670E3E7C36183F">8.1-1</a>).

The optional arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be a (possibly empty) list of vertices of <var class="Arg">digraph</var>, the optional argument <var class="Arg">limit</var> must be either a positive integer or <code class="code">infinity</code>, and the optional argument <var class="Arg">size</var> must be a positive integer. If not specified, then <var class="Arg">include</var> and <var class="Arg">exclude</var> are chosen to be empty lists, and <var class="Arg">limit</var> is set to <code class="code">infinity</code>.

The functions will return as many suitable cliques as possible, up to the number <var class="Arg">limit</var>. These functions will find cliques that contain all of the vertices of <var class="Arg">include</var> but do not contain any of the vertices of <var class="Arg">exclude</var>. The argument <var class="Arg">size</var> restricts the search to those cliques that contain precisely <var class="Arg">size</var> vertices. If the function or attribute has <code class="code">Maximal</code> in its name, then only maximal cliques will be returned; otherwise non-maximal cliques may be returned.

Let <code class="code">G</code> denote the automorphism group of maximal symmetric subdigraph of <var class="Arg">digraph</var> without loops (see <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) and <code class="func">MaximalSymmetricSubdigraphWithoutLoops</code> (<a href="chap3.html#X829E3EAC7C4B3B1E">3.3-5</a>)).

<dl>
<dt>Distinct cliques</dt>
<dd><code class="code">DigraphMaximalCliques</code> and <code class="code">DigraphCliques</code> each return a duplicate-free list of at most <var class="Arg">limit</var> cliques of <var class="Arg">digraph</var> that satisfy the arguments.

The computation may be significantly faster if <var class="Arg">include</var> and <var class="Arg">exclude</var> are invariant under the action of <code class="code">G</code> on sets of vertices.

</dd>
<dt>Orbit representatives of cliques</dt>
<dd>To use <code class="code">DigraphMaximalCliquesReps</code> or <code class="code">DigraphCliquesReps</code>, the arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be invariant under the action of <code class="code">G</code> on sets of vertices.

If this is the case, then <code class="code">DigraphMaximalCliquesReps</code> and <code class="code">DigraphCliquesReps</code> each return a duplicate-free list of at most <var class="Arg">limit</var> orbits representatives (under the action of <code class="code">G</code> on sets vertices) of cliques of <var class="Arg">digraph</var> that satisfy the arguments.

The representatives are not guaranteed to be in distinct orbits. However, if fewer than <var class="Arg">lim</var> results are returned, then there will be at least one representative from each orbit of maximal cliques.

</dd>
</dl>

<div class="example"><pre>
gap> D := Digraph([
> [2, 3], [1, 3], [1, 2, 4], [3, 5, 6], [4, 6], [4, 5]]);
<immutable digraph with 6 vertices, 14 edges>
gap> IsSymmetricDigraph(D);
true
gap> G := AutomorphismGroup(D);
Group([ (5,6), (1,2), (1,5)(2,6)(3,4) ])
gap> AsSet(DigraphMaximalCliques(D));
[ [ 1, 2, 3 ], [ 3, 4 ], [ 4, 5, 6 ] ]
gap> DigraphMaximalCliquesReps(D);
[ [ 1, 2, 3 ], [ 3, 4 ] ]
gap> Orbit(G, [1, 2, 3], OnSets);
[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
gap> Orbit(G, [3, 4], OnSets);
[ [ 3, 4 ] ]
gap> DigraphMaximalCliquesReps(D, [3, 4], [], 1);
[ [ 3, 4 ] ]
gap> DigraphMaximalCliques(D, [1, 2], [5, 6], 1, 2);
[ ]
gap> DigraphCliques(D, [1], [5, 6], infinity, 2);
[ [ 1, 2 ], [ 1, 3 ] ]
gap> D := Digraph(IsMutableDigraph, [
> [2, 3], [1, 3], [1, 2, 4], [3, 5, 6], [4, 6], [4, 5]]);
<mutable digraph with 6 vertices, 14 edges>
gap> IsSymmetricDigraph(D);
true
gap> G := AutomorphismGroup(D);
Group([ (5,6), (1,2), (1,5)(2,6)(3,4) ])
gap> AsSet(DigraphMaximalCliques(D));
[ [ 1, 2, 3 ], [ 3, 4 ], [ 4, 5, 6 ] ]</pre></div>

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

<h5>8.1-5 CliqueNumber</h5>

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

If <var class="Arg">digraph</var> is a digraph, then <code class="code">CliqueNumber(<var class="Arg">digraph</var>)</code> returns the largest integer <code class="code">n</code> such that <var class="Arg">digraph</var> contains a clique with <code class="code">n</code> vertices as an induced subdigraph.

A clique of a digraph is a set of mutually adjacent vertices of the digraph. Loops and multiple edges are ignored for the purpose of determining the clique number of a digraph.

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

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

<h4>8.2 Finding independent sets</h4>

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

<h5>8.2-1 IsIndependentSet</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIndependentSet</code>( <var class="Arg">digraph</var>, <var class="Arg">l</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">‣ IsMaximalIndependentSet</code>( <var class="Arg">digraph</var>, <var class="Arg">l</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">l</var> is a duplicate-free list of vertices of <var class="Arg">digraph</var>, then <code class="code">IsIndependentSet(</code><var class="Arg">digraph</var><code class="code">,</code><var class="Arg">l</var><code class="code">)</code> returns <code class="keyw">true</code> if <var class="Arg">l</var> is an independent set of <var class="Arg">digraph</var> and <code class="keyw">false</code> if it is not. Similarly, <code class="code">IsMaximalIndependentSet(</code><var class="Arg">digraph</var><code class="code">,</code><var class="Arg">l</var><code class="code">)</code> returns <code class="keyw">true</code> if <var class="Arg">l</var> is a maximal independent set of <var class="Arg">digraph</var> and <code class="keyw">false</code> if it is not.

An independent set of a digraph is a set of mutually non-adjacent vertices of the digraph. A maximal independent set is an independent set that is not properly contained in another independent set. An independent set is permitted, but not required, to contain vertices at which there is a loop.

<div class="example"><pre>
gap> D := CycleDigraph(4);;
gap> IsIndependentSet(D, [1]);
true
gap> IsMaximalIndependentSet(D, [1]);
false
gap> IsIndependentSet(D, [1, 4, 3]);
false
gap> IsIndependentSet(D, [2, 4]);
true
gap> IsMaximalIndependentSet(D, [2, 4]);
true
gap> D := CycleDigraph(IsMutableDigraph, 4);;
gap> IsIndependentSet(D, [1]);
true</pre></div>

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

<h5>8.2-2 DigraphIndependentSet</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphIndependentSet</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">size</var>]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalIndependentSet</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">size</var>]]] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: An immutable list of positive integers, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph, then these functions returns an independent set of <var class="Arg">digraph</var> if one exists that satisfies the arguments, else it returns <code class="keyw">fail</code>. An independent set is defined by the set of vertices that it contains; see <code class="func">IsIndependentSet</code> (<a href="chap8.html#X790733B67B0BC894">8.2-1</a>) and <code class="func">IsMaximalIndependentSet</code> (<a href="chap8.html#X790733B67B0BC894">8.2-1</a>).

The optional arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be a (possibly empty) duplicate-free list of vertices of <var class="Arg">digraph</var>, and the optional argument <var class="Arg">size</var> must be a positive integer. By default, <var class="Arg">include</var> and <var class="Arg">exclude</var> are empty. These functions will search for an independent set of <var class="Arg">digraph</var> that includes the vertices of <var class="Arg">include</var> but does not include any vertices in <var class="Arg">exclude</var>; if the argument <var class="Arg">size</var> is supplied, then additionally the independent set will be required to contain precisely <var class="Arg">size</var> vertices.

If <var class="Arg">include</var> is not an independent set, then these functions return <code class="keyw">fail</code>. Otherwise, the functions behave in the following way, depending on the number of arguments:

<dl>
<dt>One or two arguments</dt>
<dd>If one or two arguments are supplied, then <code class="code">DigraphIndependentSet</code> and <code class="code">DigraphMaximalIndependentSet</code> greedily enlarge the independent set <var class="Arg">include</var> until it cannot continue. The result is guaranteed to be a maximal independent set. This may or may not return an answer more quickly than using <code class="func">DigraphMaximalIndependentSets</code> (<a href="chap8.html#X7D2C78EB81A798A9">8.2-3</a>) with a limit of 1.

</dd>
<dt>Three arguments</dt>
<dd>If three arguments are supplied, then <code class="code">DigraphIndependentSet</code> greedily enlarges the independent set <var class="Arg">include</var> until it cannot continue, although this independent set may not be maximal.

Given three arguments, <code class="code">DigraphMaximalIndependentSet</code> returns the maximal independent set returned by <code class="code">DigraphMaximalIndependentSets(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1)</code> if one exists, else <code class="keyw">fail</code>.

</dd>
<dt>Four arguments</dt>
<dd>If four arguments are supplied, then <code class="code">DigraphIndependentSet</code> returns the independent set returned by <code class="code">DigraphIndependentSets(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1, </code><var class="Arg">size</var><code class="code">)</code> if one exists, else <code class="keyw">fail</code>. This independent set may not be maximal.

Given four arguments, <code class="code">DigraphMaximalIndependentSet</code> returns the maximal independent set returned by <code class="code">DigraphMaximalIndependentSets(</code><var class="Arg">digraph</var><code class="code">, </code><var class="Arg">include</var><code class="code">, </code><var class="Arg">exclude</var><code class="code">, 1, </code><var class="Arg">size</var><code class="code">)</code> if one exists, else <code class="keyw">fail</code>.

</dd>
</dl>

<div class="example"><pre>
gap> D := ChainDigraph(6);
<immutable chain digraph with 6 vertices>
gap> DigraphIndependentSet(D);
[ 6, 4, 2 ]
gap> DigraphMaximalIndependentSet(D);
[ 6, 4, 2 ]
gap> DigraphIndependentSet(D, [2, 4]);
[ 2, 4, 6 ]
gap> DigraphMaximalIndependentSet(D, [1, 3]);
[ 1, 3, 6 ]
gap> DigraphIndependentSet(D, [2, 4], [6]);
[ 2, 4 ]
gap> DigraphMaximalIndependentSet(D, [2, 4], [6]);
fail
gap> DigraphIndependentSet(D, [1], [], 2);
[ 1, 3 ]
gap> DigraphMaximalIndependentSet(D, [1], [], 2);
fail
gap> DigraphMaximalIndependentSet(D, [1], [], 3);
[ 1, 3, 5 ]
gap> D := ChainDigraph(IsMutableDigraph, 6);
<mutable digraph with 6 vertices, 5 edges>
gap> DigraphIndependentSet(D);
[ 6, 4, 2 ]
gap> DigraphMaximalIndependentSet(D);
[ 6, 4, 2 ]
gap> DigraphIndependentSet(D, [2, 4]);
[ 2, 4, 6 ]
gap> DigraphMaximalIndependentSet(D, [1, 3]);
[ 1, 3, 6 ]
gap> DigraphIndependentSet(D, [2, 4], [6]);
[ 2, 4 ]
gap> DigraphMaximalIndependentSet(D, [2, 4], [6]);
fail
gap> DigraphIndependentSet(D, [1], [], 2);
[ 1, 3 ]
gap> DigraphMaximalIndependentSet(D, [1], [], 2);
fail
gap> DigraphMaximalIndependentSet(D, [1], [], 3);
[ 1, 3, 5 ]</pre></div>

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

<h5>8.2-3 DigraphMaximalIndependentSets</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalIndependentSets</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalIndependentSetsReps</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphIndependentSets</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphIndependentSetsReps</code>( <var class="Arg">digraph</var>[, <var class="Arg">include</var>[, <var class="Arg">exclude</var>[, <var class="Arg">limit</var>[, <var class="Arg">size</var>]]]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalIndependentSetsAttr</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">‣ DigraphMaximalIndependentSetsRepsAttr</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An immutable list of lists of positive integers.

If <var class="Arg">digraph</var> is digraph, then these functions and attributes use <code class="func">CliquesFinder</code> (<a href="chap8.html#X7A3BC9FF8169ABCD">8.1-2</a>) to return independent sets of <var class="Arg">digraph</var>. An independent set is defined by the set of vertices that it contains; see <code class="func">IsMaximalIndependentSet</code> (<a href="chap8.html#X790733B67B0BC894">8.2-1</a>) and <code class="func">IsIndependentSet</code> (<a href="chap8.html#X790733B67B0BC894">8.2-1</a>).

The optional arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be a (possibly empty) list of vertices of <var class="Arg">digraph</var>, the optional argument <var class="Arg">limit</var> must be either a positive integer or <code class="code">infinity</code>, and the optional argument <var class="Arg">size</var> must be a positive integer. If not specified, then <var class="Arg">include</var> and <var class="Arg">exclude</var> are chosen to be empty lists, and <var class="Arg">limit</var> is set to <code class="code">infinity</code>.

The functions will return as many suitable independent sets as possible, up to the number <var class="Arg">limit</var>. These functions will find independent sets that contain all of the vertices of <var class="Arg">include</var> but do not contain any of the vertices of <var class="Arg">exclude</var> The argument <var class="Arg">size</var> restricts the search to those cliques that contain precisely <var class="Arg">size</var> vertices. If the function or attribute has <code class="code">Maximal</code> in its name, then only maximal independent sets will be returned; otherwise non-maximal independent sets may be returned.

Let <code class="code">G</code> denote the <code class="func">AutomorphismGroup</code> (<a href="chap7.html#X858C32127A190175">7.2-2</a>) of the <code class="func">DigraphSymmetricClosure</code> (<a href="chap3.html#X874883DD7DD450C4">3.3-12</a>) of the digraph formed from <var class="Arg">digraph</var> by removing loops and ignoring the multiplicity of edges.

<dl>
<dt>Distinct independent sets</dt>
<dd><code class="code">DigraphMaximalIndependentSets</code> and <code class="code">DigraphIndependentSets</code> each return a duplicate-free list of at most <var class="Arg">limit</var> independent sets of <var class="Arg">digraph</var> that satisfy the arguments.

The computation may be significantly faster if <var class="Arg">include</var> and <var class="Arg">exclude</var> are invariant under the action of <code class="code">G</code> on sets of vertices.

</dd>
<dt>Representatives of distinct orbits of independent sets</dt>
<dd>To use <code class="code">DigraphMaximalIndependentSetsReps</code> or <code class="code">DigraphIndependentSetsReps</code>, the arguments <var class="Arg">include</var> and <var class="Arg">exclude</var> must each be invariant under the action of <code class="code">G</code> on sets of vertices.

If this is the case, then <code class="code">DigraphMaximalIndependentSetsReps</code> and <code class="code">DigraphIndependentSetsReps</code> each return a list of at most <var class="Arg">limit</var> orbits representatives (under the action of <code class="code">G</code> on sets of vertices) of independent sets of <var class="Arg">digraph</var> that satisfy the arguments.

The representatives are not guaranteed to be in distinct orbits. However, if <var class="Arg">lim</var> is not specified, or fewer than <var class="Arg">lim</var> results are returned, then there will be at least one representative from each orbit of maximal independent sets.

</dd>
</dl>

<div class="example"><pre>
gap> D := CycleDigraph(5);
<immutable cycle digraph with 5 vertices>
gap> DigraphMaximalIndependentSetsReps(D);
[ [ 1, 3 ] ]
gap> DigraphIndependentSetsReps(D);
[ [ 1 ], [ 1, 3 ] ]
gap> Set(DigraphMaximalIndependentSets(D));
[ [ 1, 3 ], [ 1, 4 ], [ 2, 4 ], [ 2, 5 ], [ 3, 5 ] ]
gap> DigraphMaximalIndependentSets(D, [1]);
[ [ 1, 3 ], [ 1, 4 ] ]
gap> DigraphIndependentSets(D, [], [4, 5]);
[ [ 1 ], [ 2 ], [ 3 ], [ 1, 3 ] ]
gap> DigraphIndependentSets(D, [], [4, 5], 1, 2);
[ [ 1, 3 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 5 edges>
gap> DigraphMaximalIndependentSetsReps(D);
[ [ 1, 3 ] ]
gap> DigraphIndependentSetsReps(D);
[ [ 1 ], [ 1, 3 ] ]
gap> Set(DigraphMaximalIndependentSets(D));
[ [ 1, 3 ], [ 1, 4 ], [ 2, 4 ], [ 2, 5 ], [ 3, 5 ] ]
gap> DigraphMaximalIndependentSets(D, [1]);
[ [ 1, 3 ], [ 1, 4 ] ]
gap> DigraphIndependentSets(D, [], [4, 5]);
[ [ 1 ], [ 2 ], [ 3 ], [ 1, 3 ] ]
gap> DigraphIndependentSets(D, [], [4, 5], 1, 2);
[ [ 1, 3 ] ]</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap7.html">[Previous Chapter]</a> <a href="chap9.html">[Next Chapter]</a> </div>

<div class="chlinkbot">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>

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

quality100%

¤ Dauer der Verarbeitung: 0.24 Sekunden (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.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.