GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

FindVertexCover

  

find vertex cover in graph

 

Calling Sequence

Parameters

Description

Definition

Examples

Compatibility

Calling Sequence

FindVertexCover(G,size,opt)

Parameters

G

-

graph

size

-

(optional) integer or range; size of vertex cover to find

opt

-

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

Description

• 

FindVertexCover returns a list of vertices which comprise a vertex cover in the graph G. The optional parameter size specifies a size for the vertex cover. If size is omitted, FindVertexCover behaves identically to MinimumVertexCover and returns a minimum vertex cover.

Definition

• 

A vertex cover of a graph G is a subset S of the vertices of G such that every edge in G is incident to some member of S.

Examples

withGraphTheory:

GCompleteGraph3,4

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

(1)

DrawGraphG

FindVertexCoverG,3

1,2,3

(2)

FindVertexCoverG,4

4,5,6,7

(3)

Compatibility

• 

The GraphTheory[FindVertexCover] command was introduced in Maple 2019.

• 

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

See Also

MaximumIndependentSet

MinimumVertexCover