GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

MinimumVertexCover

  

VertexCoverNumber

 

Calling Sequence

Parameters

Description

Definition

Examples

Compatibility

Calling Sequence

MinimumVertexCover(G)

MinimumVertexCover(G, opt)

VertexCoverNumber(G)

VertexCoverNumber(G, opt)

Parameters

G

-

graph

opt

-

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

Description

• 

MinimumVertexCover returns a list of vertices which comprise a minimum vertex cover.

• 

VertexCoverNumber returns the number of vertices in a minimum vertex cover of the graph G.

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:

GGraphComplementCompleteGraph3,4

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

(1)

DrawGraphG

VertexCoverNumberG

5

(2)

MinimumVertexCoverG

2,3,5,6,7

(3)

Compatibility

• 

The GraphTheory[MinimumVertexCover] and GraphTheory[VertexCoverNumber] commands were introduced in Maple 2019.

• 

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

See Also

FindVertexCover

IndependenceNumber

MaximumIndependentSet