Quelle CHAP007.htm Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/grape/htm/CHAP007.htm

<html><head><title>[grape] 7 Vertex-Colouring and Complete Subgraphs</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP006.htm">Previous</a>] [<a href ="CHAP008.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>7 Vertex-Colouring and Complete Subgraphs</h1>

<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP007.htm#SECT001">VertexColouring</a>
<li> <A HREF="CHAP007.htm#SECT002">IsVertexColouring</a>
<li> <A HREF="CHAP007.htm#SECT003">MinimumVertexColouring</a>
<li> <A HREF="CHAP007.htm#SECT004">ChromaticNumber</a>
<li> <A HREF="CHAP007.htm#SECT005">CompleteSubgraphs</a>
<li> <A HREF="CHAP007.htm#SECT006">CompleteSubgraphsOfGivenSize</a>
<li> <A HREF="CHAP007.htm#SECT007">MaximumClique</a>
<li> <A HREF="CHAP007.htm#SECT008">CliqueNumber</a>
</ol>

The following sections describe functions for (proper) vertex-colouring
and determining complete subgraphs of a given simple graph. Included are
functions for determining the chromatic number and the clique number of
a simple graph. The methods used for proper vertex-colouring are described
in <a href="biblio.htm#Soi24a"><cite>Soi24a</cite></a>.

The function <code>CompleteSubgraphsOfGivenSize</code> can be used to determine
the complete subgraphs with given vertex-weight sum in a vertex-weighted
graph,
<a name = "I0"></a>

where the weights can be positive
integers or non-zero vectors of non-negative integers.


<h2><a name="SECT001">7.1 VertexColouring</a></h2>

<a name = "SSEC001.1"></a>
<li><code>VertexColouring( </code><var>gamma</var><code> )</code>
<li><code>VertexColouring( </code><var>gamma</var><code>, </code><var>k</var><code> )</code>
<li><code>VertexColouring( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>m</var><code> )</code>

This function returns a proper vertex-colouring <var>C</var> for the graph
<var>gamma</var>, which must be simple. A proper vertex-colouring
<a name = "I1"></a>

of <var>gamma</var> is an assignment of colours to the vertices
of <var>gamma</var>, such that, if <var>[i,j]</var> is an edge, then vertices <var>i</var> and <var>j</var>
are assigned different colours.

The returned proper vertex-colouring <var>C</var> is given as a list of positive
integers (the colours), indexed by the vertices of <var>gamma</var>, with the
property that <var><var>C</var>[i]not=<var>C</var>[j]</var> whenever <var>[i,j]</var> is an edge of <var>gamma</var>.

If the optional parameter <var>k</var> is given, then <var>k</var> must be a non-negative
integer. In this case, a proper vertex-colouring using at most <var>k</var>
colours is returned, if such a colouring exists, and <code>fail</code> otherwise.

If, in addition to <var>k</var>, the optional parameter <var>m</var> is given, then <var>m</var>
must be a a non-negative integer, such that there is no monochromatic
set of vertices of size greater than <var>m</var> in any proper vertex-colouring
of <var>gamma</var> which uses at most <var>k</var> colours. This information (which is
not checked) may help to speed up the function.

<pre>
gap> J:=JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4)
 (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true,
 names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
 [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
 representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
 ] )
gap> VertexColouring(J);
[ 1, 3, 5, 4, 2, 3, 6, 1, 5, 2 ]
gap> VertexColouring(J,5);
[ 1, 2, 3, 4, 5, 4, 2, 1, 3, 5 ]
gap> VertexColouring(J,4);
fail
</pre>


<h2><a name="SECT002">7.2 IsVertexColouring</a></h2>

<a name = "SSEC002.1"></a>
<li><code>IsVertexColouring( </code><var>gamma</var><code>, </code><var>C</var><code> )</code>
<li><code>IsVertexColouring( </code><var>gamma</var><code>, </code><var>C</var><code>, </code><var>k</var><code> )</code>

Suppose that <var>gamma</var> is a simple graph, <var>C</var> is a list of positive integers
of length <code>OrderGraph(</code><var>gamma</var><code>)</code>, and <var>k</var> is a non-negative integer
(default: <code>OrderGraph(</code><var>gamma</var><code>)</code>).

Then this function returns <code>true</code> if <var>C</var> is a vertex <var>k</var>-colouring of
<var>gamma</var>, that is, a proper vertex-colouring using at most <var>k</var>-colours (for
which <var><var>C</var>[i]</var> is the colour of the <var>i</var>-th vertex), and <code>false</code> if not.

See also <a href="CHAP007.htm#SSEC001.1">VertexColouring</a>.

<pre>
gap> gamma:=JohnsonGraph(7,3);;
gap> C:=VertexColouring(gamma,6);;
gap> IsVertexColouring(gamma,C);
true
gap> IsVertexColouring(gamma,C,7);
true
gap> IsVertexColouring(gamma,C,6);
true
gap> IsVertexColouring(gamma,C,5);
false
</pre>


<h2><a name="SECT003">7.3 MinimumVertexColouring</a></h2>

<a name = "SSEC003.1"></a>
<li><code>MinimumVertexColouring( </code><var>gamma</var><code> )</code>

This function returns a minimum vertex-colouring <var>C</var> for the graph
<var>gamma</var>, which must be simple. A minimum vertex-colouring
<a name = "I2"></a>

is a proper vertex-colouring using as few colours as possible.

The returned minimum vertex-colouring <var>C</var> is given as a list of positive
integers (the colours), indexed by the vertices of <var>gamma</var>, with the
property that <var><var>C</var>[i]not=<var>C</var>[j]</var> whenever <var>[i,j]</var> is an edge of <var>gamma</var>,
and subject to this property, the number of distinct elements of <var>C</var>
is as small as possible.

See also <a href="CHAP007.htm#SSEC001.1">VertexColouring</a>.

<pre>
gap> J:=JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4)
 (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true,
 names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
 [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
 representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
 ] )
gap> MinimumVertexColouring(J);
[ 1, 2, 3, 4, 5, 4, 2, 1, 3, 5 ]
</pre>


<h2><a name="SECT004">7.4 ChromaticNumber</a></h2>

<a name = "SSEC004.1"></a>
<li><code>ChromaticNumber( </code><var>gamma</var><code> )</code>

This function returns the chromatic number of the given graph <var>gamma</var>,
which must be simple. The chromatic number
<a name = "I3"></a>

of <var>gamma</var> is the minimum number of colours needed to properly vertex-colour
<var>gamma</var>, that is, the number of colours used in a minimum vertex-colouring
of <var>gamma</var>.

See also <a href="CHAP007.htm#SSEC003.1">MinimumVertexColouring</a>.

<pre>
gap> ChromaticNumber(JohnsonGraph(5,2));
5
gap> ChromaticNumber(JohnsonGraph(6,2));
5
gap> ChromaticNumber(JohnsonGraph(7,2));
7
</pre>


<h2><a name="SECT005">7.5 CompleteSubgraphs</a></h2>

<a name = "SSEC005.1"></a>
<li><code>CompleteSubgraphs( </code><var>gamma</var><code> )</code>
<li><code>CompleteSubgraphs( </code><var>gamma</var><code>, </code><var>k</var><code> )</code>
<li><code>CompleteSubgraphs( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code>
<li><code>CompleteSubgraphs( </code><var>G</var><code>, </code><var>gamma</var><code> )</code>
<li><code>CompleteSubgraphs( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code> )</code>
<li><code>CompleteSubgraphs( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code>

Let <var>gamma</var> be a simple graph and <var>k</var> an integer. This function returns
a set <var>K</var> of complete subgraphs of <var>gamma</var>, where a complete subgraph is
represented by its vertex-set. If <var>k</var> is non-negative then the elements
of <var>K</var> each have size <var>k</var>, otherwise the elements of <var>K</var> represent maximal
complete subgraphs of <var>gamma</var>. (A maximal complete subgraph of <var>gamma</var>
is a complete subgraph of <var>gamma</var> which is not properly contained in
another complete subgraph of <var>gamma</var>.) The default for <var>k</var> is <var>-1</var>,
i.e. maximal complete subgraphs. See also <code>CompleteSubgraphsOfGivenSize</code>,
which can be used to compute the maximal complete subgraphs of given
size, and can also be used to determine the (maximal or otherwise)
complete subgraphs with given vertex-weight sum in a vertex-weighted
graph.

The optional parameter <var>G</var> must be a subgroup of <code></code><var>gamma</var><code>.group</code> and
specifies the (often powerful) constraint that each returned complete
subgraph must be <var>G</var>-invariant. The default for <var>G</var> is the trivial
permutation group, which imposes no constraint.

The optional parameter <var>alls</var> controls how many complete subgraphs are
returned. The valid values for <var>alls</var> are 0, 1 (the default), and 2.

Warning: Using the default value of 1 for <var>alls</var> (see below) means
that the elements of the returned set need not be inequivalent under
<code></code><var>gamma</var><code>.group</code>. To obtain just one element from each <code></code><var>gamma</var><code>.group</code>
orbit of the required complete subgraphs, you must give the value 2 to
the parameter <var>alls</var>.

If <var>alls</var>=0 (or <code>false</code> for backward compatibility) then the returned
set <var>K</var> will contain at most one element. In this case, if <var>k</var> is
negative then <var>K</var> will contain just one <var>G</var>-invariant maximal complete
subgraph of <var>gamma</var> if and only if such a subgraph exists, and if <var>k</var>
is non-negative then <var>K</var> will contain a <var>G</var>-invariant complete subgraph
of size <var>k</var> of <var>gamma</var> if and only if such a subgraph exists.

If <var>alls</var>=1 (or <code>true</code> for backward compatibility) and <var>G</var> is trivial
then <var>K</var> will contain (perhaps properly) a set of <code></code><var>gamma</var><code>.group</code>
orbit-representatives of the maximal (if <var>k</var> is negative) or size <var>k</var>
(if <var>k</var> is non-negative) complete subgraphs of <var>gamma</var>.

If <var>alls</var>=1 (or <code>true</code> for backward compatibility) and <var>G</var> is non-trivial
then <var>K</var> will be a set of representatives for the orbits of the normalizer
of <var>G</var> in <code></code><var>gamma</var><code>.group</code>, for its action on the <var>G</var>-invariant maximal
(if <var>k</var> is negative) or <var>G</var>-invariant size <var>k</var> (if <var>k</var> is non-negative)
complete subgraphs of <var>gamma</var>.

If <var>alls</var>=2 then <var>K</var> will consist of a classification of the <var>G</var>-invariant
maximal (if <var>k</var> is negative) or the <var>G</var>-invariant size <var>k</var> (if <var>k</var> is
non-negative) complete subgraphs of <var>gamma</var>, classified up to the action
of <code></code><var>gamma</var><code>.group</code>. (This option can be more costly than when <var>alls</var>=1.)
In particular, if <var>alls</var>=2 and <var>G</var> is trivial then <var>K</var> will be a set of
<code></code><var>gamma</var><code>.group</code> orbit-representatives of the maximal (if <var>k</var> is negative)
or size <var>k</var> (if <var>k</var> is non-negative) complete subgraphs of <var>gamma</var>.

Before applying <code>CompleteSubgraphs</code>, one may want to associate the full
automorphism group of <var>gamma</var> with <var>gamma</var>, via <code></code><var>gamma</var><code> :=
NewGroupGraph( AutGroupGraph(</code><var>gamma</var><code>), </code><var>gamma</var><code> );</code>.

An alternative name for this function is <code>Cliques</code>.
<a name = "I4"></a>


See also <a href="CHAP007.htm#SSEC006.1">CompleteSubgraphsOfGivenSize</a>.

<pre>
gap> gamma := JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
 group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]),
 isGraph := true, isSimple := true,
 names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
 [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
 representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
 ] )
gap> CompleteSubgraphs(gamma);
[ [ 1, 2, 3, 4 ], [ 1, 2, 5 ] ]
gap> CompleteSubgraphs(gamma,3,2);
[ [ 1, 2, 3 ], [ 1, 2, 5 ] ]
gap> CompleteSubgraphs(gamma,-1,0);
[ [ 1, 2, 5 ] ]
gap> G:=Subgroup(gamma.group,[(2,5)(3,6)(4,7)]);;
gap> CompleteSubgraphs(G,gamma,-1);
[ [ 1, 2, 5 ], [ 2, 5, 8, 9 ], [ 8 .. 10 ] ]
gap> CompleteSubgraphs(G,gamma,-1,2);
[ [ 1, 2, 5 ], [ 2, 5, 8, 9 ] ]
gap> CompleteSubgraphs(G,gamma,4);
[ [ 2, 5, 8, 9 ] ]
</pre>


<h2><a name="SECT006">7.6 CompleteSubgraphsOfGivenSize</a></h2>

<a name = "SSEC006.1"></a>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code>, </code><var>col</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code>, </code><var>col</var><code>, </code><var>wts</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code>, </code><var>col</var><code> )</code>
<li><code>CompleteSubgraphsOfGivenSize( </code><var>G</var><code>, </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code>, </code><var>col</var><code>, </code><var>wts</var><code> )</code>

Let <var>gamma</var> be a simple graph, and <var>k</var> a non-negative integer or vector
of non-negative integers. This function returns a set <var>K</var> (possibly
empty) of complete subgraphs of size <var>k</var> of <var>gamma</var>. The vertices may
have weights, which should be non-zero integers if <var>k</var> is an integer and
non-zero <var>d</var>-vectors of non-negative integers if <var>k</var> is a <var>d</var>-vector,
and in these cases, a complete subgraph of size <var>k</var> means a complete
subgraph whose vertex-weights sum to <var>k</var>. The exact nature of the set
<var>K</var> depends on the values of the parameters supplied to this function. A
complete subgraph is represented by its vertex-set.

The optional parameter <var>G</var> must be a subgroup of <code></code><var>gamma</var><code>.group</code> and
specifies the (often powerful) constraint that each returned complete
subgraph must be <var>G</var>-invariant. The default for <var>G</var> is the trivial
permutation group, which imposes no constraint. If <var>k</var> is a vector
of dimension greater than 1, then <var>G</var> must be trivial.

The optional parameter <var>maxi</var> controls whether only maximal complete
subgraphs of size <var>k</var> are returned. (A maximal complete subgraph of
<var>gamma</var> is a complete subgraph of <var>gamma</var> which is not properly contained
in another complete subgraph of <var>gamma</var>.) The default is <code>false</code>, which
means that non-maximal as well as maximal <var>G</var>-invariant complete subgraphs
of size <var>k</var> may be returned. If <var>maxi</var>=<code>true</code> then only <var>G</var>-invariant maximal
complete subgraphs of size <var>k</var> are returned. (Previous to version 4.1
of GRAPE, <var>maxi</var>=<code>true</code> meant that it was assumed (but not checked)
that all complete subgraphs of size <var>k</var> were maximal.)

The optional parameter <var>alls</var> controls how many complete subgraphs are
returned. The valid values for <var>alls</var> are 0, 1 (the default), and 2.

Warning: Using the default value of 1 for <var>alls</var> (see below) means
that the elements of the returned set need not be inequivalent under
<code></code><var>gamma</var><code>.group</code>. To obtain just one element from each <code></code><var>gamma</var><code>.group</code>
orbit of the required complete subgraphs, you must give the value 2 to
the parameter <var>alls</var>.

If <var>alls</var>=0 (or <code>false</code> for backward compatibility) then <var>K</var> will contain
at most one element. If <var>maxi</var>=<code>false</code> then <var>K</var> will contain one element
if and only if <var>gamma</var> contains a <var>G</var>-invariant complete subgraph of
size <var>k</var>. If <var>maxi</var>=<code>true</code> then <var>K</var> will contain one element if and
only if <var>gamma</var> contains a <var>G</var>-invariant maximal complete subgraph
of size <var>k</var>, in which case <var>K</var> will contain (the vertex-set of) such
a complete subgraph.

If <var>alls</var>=1 (or <code>true</code> for backward compatibility) and <var>G</var> is trivial
then <var>K</var> will contain (perhaps properly) a set of <code></code><var>gamma</var><code>.group</code>
orbit-representatives of the size <var>k</var> (if <var>maxi</var>=<code>false</code>) or the maximal
size <var>k</var> (if <var>maxi</var>=<code>true</code>) complete subgraphs of <var>gamma</var>.

If <var>alls</var>=1 (or <code>true</code> for backward compatibility) and <var>G</var> is
non-trivial then <var>K</var> will be a set of representatives for the orbits
of the normalizer of <var>G</var> in <code></code><var>gamma</var><code>.group</code>, for its action on the
<var>G</var>-invariant size <var>k</var> (if <var>maxi</var>=<code>false</code>) or the <var>G</var>-invariant maximal
size <var>k</var> (if <var>maxi</var>=<code>true</code>) complete subgraphs of <var>gamma</var>.

If <var>alls</var>=2 then <var>K</var> will consist of a classification of the <var>G</var>-invariant
size <var>k</var> (if <var>maxi</var>=<code>false</code>) or the <var>G</var>-invariant maximal size <var>k</var> (if
<var>maxi</var>=<code>true</code>) complete subgraphs of <var>gamma</var>, classified up to the action
of <code></code><var>gamma</var><code>.group</code>. (This option can be more costly than when <var>alls</var>=1.)
In particular, if <var>alls</var>=2 and <var>G</var> is trivial then <var>K</var> will be a set of
<code></code><var>gamma</var><code>.group</code> orbit-representatives of the size <var>k</var> (if <var>maxi</var>=<code>false</code>)
or the maximal size <var>k</var> (if <var>maxi</var>=<code>true</code>) complete subgraphs of <var>gamma</var>.

The optional boolean parameter <var>col</var> is used to determine whether or not
partial proper vertex-colouring is used to cut down the search tree. The
default is <code>true</code>, which says to use this partial colouring. This is
usually the best choice. For backward compatibility, <var>col</var> a rational
number means the same as <var>col</var>=<code>true</code>.

The optional parameter <var>wts</var> should be a list of vertex-weights; the list
should be of length <code></code><var>gamma</var><code>.order</code>, with the <var>i</var>-th element being the
weight of vertex <var>i</var>. The weights must be all positive integers if <var>k</var>
is an integer, and all non-zero <var>d</var>-vectors of non-negative integers
if <var>k</var> is a <var>d</var>-vector. The default is that all weights are equal to 1.
(Recall that, for this function, a complete subgraph of size <var>k</var>
means a complete subgraph whose vertex-weights sum to <var>k</var>.)

If <var>wts</var> is a list of (positive) integers, then it is required that
for all <var>g</var> in <code></code><var>gamma</var><code>.group</code> and all <var>v</var> in <code>Vertices(</code><var>gamma</var><code>)</code>,
we have <var><var>wts</var>[vg]=<var>wts</var>[v]</var>.

If <var>wts</var> is a list of <var>d</var>-vectors then we assume that there is some group
<var>H</var> and epimorphism <var>theta</var> from <var>H</var> to <code></code><var>gamma</var><code>.group</code>, such that there
is an action <var>mu</var> of <var>H</var> on <code>[1..</code><var>d</var><code>]</code>, giving an action of <var>H</var> on the
set of integer <var>d</var>-vectors, where if <var>w</var> is an integer <var>d</var>-vector and
<var>h</var> in <var>H</var> then <var>wh</var> is defined by <var>wh[mu(i,h)]=w[i]</var> for all <var>i</var>
in <code>[1..</code><var>d</var><code>]</code>. It is then required that for all <var>h</var> in <var>H</var>, we have
<var><var>k</var>h=<var>k</var></var> and for all <var>v</var> in <code>Vertices(</code><var>gamma</var><code>)</code>, <var><var>wts</var>[vhtheta]
= <var>wts</var>[v]h</var>. These requirements are not checked by the function,
and the use of vector-weights is primarily for the DESIGN package
and advanced users of GRAPE.

An alternative name for this function is
<code>CliquesOfGivenSize</code>.
<a name = "I5"></a>


See also <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphs</a>.

<pre>
gap> gamma:=JohnsonGraph(6,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7, 8, 9 ] ],
 group := Group([ (1,6,10,13,15,5)(2,7,11,14,4,9)(3,8,12), (2,6)(3,7)(4,8)
 (5,9) ]), isGraph := true, isSimple := true,
 names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 2, 3 ],
 [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ], [ 3, 5 ], [ 3, 6 ], [ 4, 5 ],
 [ 4, 6 ], [ 5, 6 ] ], order := 15, representatives := [ 1 ],
 schreierVector := [ -1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1 ] )
gap> CompleteSubgraphsOfGivenSize(gamma,4);
[ [ 1, 2, 3, 4 ] ]
gap> CompleteSubgraphsOfGivenSize(gamma,4,1,true);
[ ]
gap> CompleteSubgraphsOfGivenSize(gamma,5,2,true);
[ [ 1, 2, 3, 4, 5 ] ]
gap> G:=SylowSubgroup(gamma.group,3);;
gap> Size(G);
9
gap> CompleteSubgraphsOfGivenSize(G,gamma,2);
[ ]
gap> CompleteSubgraphsOfGivenSize(gamma,2);
[ [ 1, 2 ] ]
gap> CompleteSubgraphsOfGivenSize(G,gamma,3,2);
[ [ 2, 4, 11 ] ]
gap> CompleteSubgraphsOfGivenSize(gamma,3,2);
[ [ 1, 2, 3 ], [ 1, 2, 6 ] ]
gap> delta:=NewGroupGraph(Group(()),gamma);;
gap> CompleteSubgraphsOfGivenSize(delta,5,2,true);
[ [ 1, 2, 3, 4, 5 ], [ 1, 6, 7, 8, 9 ], [ 2, 6, 10, 11, 12 ],
 [ 3, 7, 10, 13, 14 ], [ 4, 8, 11, 13, 15 ], [ 5, 9, 12, 14, 15 ] ]
gap> CompleteSubgraphsOfGivenSize(delta,5,0);
[ [ 1, 2, 3, 4, 5 ] ]
gap> CompleteSubgraphsOfGivenSize(delta,5,1,false,true,
> [1,2,3,4,5,6,7,8,7,6,5,4,3,2,1]);
[ [ 1, 4 ], [ 2, 3 ], [ 3, 14 ], [ 4, 15 ], [ 5 ], [ 11 ], [ 12, 15 ],
 [ 13, 14 ] ]
</pre>


<h2><a name="SECT007">7.7 MaximumClique</a></h2>

<a name = "SSEC007.1"></a>
<li><code>MaximumClique( </code><var>gamma</var><code> )</code>

This function returns a maximum clique of the graph <var>gamma</var>, which must
be simple. A maximum clique
<a name = "I6"></a>

of <var>gamma</var> is a
set of pairwise adjacent vertices of <var>gamma</var> of the largest possible size.

An alternative name for this function is
<code>MaximumCompleteSubgraph</code>.
<a name = "I7"></a>


See also <a href="CHAP007.htm#SSEC006.1">CompleteSubgraphsOfGivenSize</a>.

<pre>
gap> J:=JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4)
 (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true,
 names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
 [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
 representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
 ] )
gap> MaximumClique(J);
[ 1, 2, 3, 4 ]
</pre>


<h2><a name="SECT008">7.8 CliqueNumber</a></h2>

<a name = "SSEC008.1"></a>
<li><code>CliqueNumber( </code><var>gamma</var><code> )</code>

This function returns the clique number of the given graph <var>gamma</var>,
which must be simple. The clique number
<a name = "I8"></a>

of <var>gamma</var> is the size of a largest clique in <var>gamma</var>, where a clique
is a set of pairwise adjacent vertices.

<pre>
gap> CliqueNumber(JohnsonGraph(5,2));
4
gap> CliqueNumber(JohnsonGraph(6,2));
5
gap> CliqueNumber(JohnsonGraph(7,2));
6
</pre>

[<a href = "chapters.htm">Up</a>] [<a href ="CHAP006.htm">Previous</a>] [<a href ="CHAP008.htm">Next</a>] [<a href = "theindex.htm">Index</a>]

<address>grape manual September 2025
</address></body></html>

quality99%

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