dwave_networkx.algorithms.cover.is_vertex_cover

is_vertex_cover(G, vertex_cover)

Determines whether the given set of vertices is a vertex cover of graph G.

A vertex cover is a set of vertices such that each edge of the graph is incident with at least one vertex in the set.

Parameters:

• G (NetworkX graph) – The graph on which to check the vertex cover.

• vertex_cover – Iterable of nodes.

Returns:

is_cover – True if the given iterable forms a vertex cover.

Return type:

bool

Examples

This example checks two covers for a graph, G, of a single Chimera unit cell. The first uses the set of the four horizontal qubits, which do constitute a cover; the second set removes one node.

>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> cover = [0, 1, 2, 3]
>>> dnx.is_vertex_cover(G,cover)
True
>>> cover = [0, 1, 2]
>>> dnx.is_vertex_cover(G,cover)
False