GraphTheory - Maple Programming Help

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

GraphTheory

 MinimumVertexCover
 VertexCoverNumber

 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3,4\right)\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 7 vertices and 9 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{VertexCoverNumber}\left(G\right)$
 ${5}$ (2)
 > $\mathrm{MinimumVertexCover}\left(G\right)$
 $\left[{2}{,}{3}{,}{5}{,}{6}{,}{7}\right]$ (3)

Compatibility

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