GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/MaximumIndependentSet

GraphTheory

  

IndependenceNumber

  

MaximumIndependentSet

 

Calling Sequence

Parameters

Description

Definitions

Details

Examples

Compatibility

Calling Sequence

IndependenceNumber(G)

IndependenceNumber(G, opt)

MaximumIndependentSet(G)

MaximumIndependentSet(G, opt)

Parameters

G

-

graph

opt

-

(optional) equation of the form method = m, where m is exact or greedy

Description

• 

IndependenceNumber returns the independence number of the graph G.

• 

MaximumIndependentSet returns a list of vertices comprising a maximum independent set of G.

• 

The strategy is a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999).

Definitions

• 

An independent set of a graph G is a subset S of the vertices of G, with the condition that if any vertices v1 and v2 are both members of S, the graph G must not contain an edge between them. An independent set of G is a clique of the complement of G.

• 

A maximum independent set of G is an independent set of maximum size for the graph G.

• 

The independence number of G is the cardinality of a maximum independent set of G. This is equal to the clique number of the complement of G.

Details

• 

The problem of finding a maximum independent set for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs. For a faster algorithm that usually, but not always, returns a relatively large clique see GreedyIndependentSet. This algorithm can also be selected by using the method = greedy option. The default is method = exact.

Examples

withGraphTheory:

GCompleteGraph3,4

GGraph 1: an undirected unweighted graph with 7 vertices and 12 edge(s)

(1)

DrawGraphG

IndependenceNumberG

4

(2)

MaximumIndependentSetG

4,5,6,7

(3)

This is equivalent to the maximum clique problem on the complement of G.

CGraphComplementG:

DrawGraphC

CliqueNumberC

4

(4)

MaximumCliqueC

4,5,6,7

(5)

In this case, the greedy algorithm also finds the optimum.

IndependenceNumberG,method=greedy

4

(6)

MaximumIndependentSetG,method=greedy

4,5,6,7

(7)

Compatibility

• 

The GraphTheory[IndependenceNumber] and GraphTheory[MaximumIndependentSet] commands were updated in Maple 2019.

• 

The method option was introduced in Maple 2019.

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

CliqueNumber

GraphComplement

GreedyIndependentSet

MaximumClique