覆盖问题和匹配问题

一、最大匹配问题

• 匹配：对于图
  
  
  
  G

  =

  (

  V

  ,

  E

  )

  G=(V,E)
  
  
  
  
  
  
  G
  
  
  
  
  =
  
  
  
  
  
  
  
  
  (
  
  
  V
  
  
  ,
  
  
  
  
  E
  
  
  )
  
  
  
  
  
  ，若边集合
  
  
  
  M

  ∈

  V

  M \in V
  
  
  
  
  
  
  M
  
  
  
  
  ∈
  
  
  
  
  
  
  
  
  V
  
  
  
  
  
  （
  
  
  
  M

  ∈

  G

  M \in G
  
  
  
  
  
  
  M
  
  
  
  
  ∈
  
  
  
  
  
  
  
  
  G
  
  
  
  
  
  ），满足所有的边
  
  
  
  e

  ∈

  M

  e \in M
  
  
  
  
  
  
  e
  
  
  
  
  ∈
  
  
  
  
  
  
  
  
  M
  
  
  
  
  
  都没有公共定点，那么，
  
  
  
  M

  M
  
  
  
  
  
  
  M
  
  
  
  
  
  为
  
  
  
  G

  G
  
  
  
  
  
  
  G
  
  
  
  
  
  的一个覆盖；

二、最小顶点覆盖问题

• 覆盖：对于图
  
  
  
  G

  =

  (

  V

  ,

  E

  )

  G=(V,E)
  
  
  
  
  
  
  G
  
  
  
  
  =
  
  
  
  
  
  
  
  
  (
  
  
  V
  
  
  ,
  
  
  
  
  E
  
  
  )
  
  
  
  
  
  ，若顶点集合
  
  
  
  M

  ∈

  V

  M \in V
  
  
  
  
  
  
  M
  
  
  
  
  ∈
  
  
  
  
  
  
  
  
  V
  
  
  
  
  
  ，满足所有的边
  
  
  
  e

  ∈

  E

  e \in E
  
  
  
  
  
  
  e
  
  
  
  
  ∈
  
  
  
  
  
  
  
  
  E
  
  
  
  
  
  都至少有一个顶点在
  
  
  
  M

  M
  
  
  
  
  
  
  M
  
  
  
  
  
  内，那么
  
  
  
  M

  M
  
  
  
  
  
  
  M
  
  
  
  
  
  就是图
  
  
  
  G

  G
  
  
  
  
  
  
  G
  
  
  
  
  
  的一个覆盖；