FindVertexCover - Maple Help

GraphTheory

 FindVertexCover
 find vertex cover in graph

 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

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

Compatibility

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