81
Vertex Cover
Reminder: Graph
G = (V,E)
set of vertices
V
set of edges
E
Vertex cover
C
of
G
…
C ⊆ V
for all edges
(u,v) ∈ E
either
v ∈ C
or
u ∈ C
(or both)
⇒ All edges of the graph are "covered" by vertices in
C
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}