Algorithme de graphe bipartite

Question

Considérons la question suivante relative à la théorie des graphes:

Soit G un graphe bipartite. Pour rendre le problème plus concret suppose G est l'union disjointe de deux ensembles, dis-je et S. Suppose

• I représente les personnes avec le nom 1, 2, 3, 4, 5, 6, 7, 8, 9 , S
• S représente des compétences avec le nom a, b, c, d, e, f, g, h.

Ainsi, chaque individu a certains compétences, par exemple,

• individuelle 1 a des compétences b, d, g et h,
• individuel 2 a des compétences a, f, et h ,
• etc.

[dans l'exemple, sont données au hasard données].

Notre but est de construire une équipe composée du nombre minimum de personnes de je de telle sorte que toutes les compétences dans S sera représentée dans l'équipe, qui est pour chaque compétence s dans S, il existe un membre de l'équipe ayant la compétence s.

Ce problème a-t-il un nom? Est-ce qu'un algorithme efficace pour le résoudre est connu?

Answer 1

Sons comme un set cover problem
Groupes d'articles de l créer un sous-ensemble de de

Answer 2

Votre problème est un problème de couverture de jeu minimum:

Achetez X de M sur N lots où M est le nombre minimum de lots dont vous avez besoin pour obtenir tous les éléments X. Dans votre exemple, les compétences sont des items et les étudiants sont beaucoup.

http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml

Le problème est NP-dur. Le moyen efficace de le résoudre est d'utiliser l'algorithme d'approximation de la couverture d'ensemble glouton.