sets of representatives (tradcucción)

Dados los vértices de una gráfica que representan un grupo de personas. Una arista entre dos personas significa que tienen algo en común. Deseamos formar un comité (un subconjunto de los vértices),con el menor número posible de miembros, de manera que todo el aquel que no esté en el comité tenga algo en común con al menos una persona en el comité. Por lo tanto, buscamos un conjunto dominantecardinalidad mínima. Tenga en cuenta que el conjunto S = {Teresa, Pete, Mike, Sandee, Steve} es un conjunto dominante minimal, mientras que el conjunto D = {Steve, Renu, Pete} es un conjunto mínimodominante (o una -conjunto) para esta gráfica. El conjunto S tiene otra propiedad de interés. Cada persona es adyacente a un miembro de S, incluidos los miembros de S sí mismos, es decir, ninguno de losmiembros de S es aislado en S. Debido a que cada miembro del comité puede sentir más cómodo conociendo al menos otro miembro del comité, un conjunto con esta propiedad podría mejorar el rendimientocomité. Un conjunto S es un conjunto dominante total si N (S) = V, o de manera equivalente, si para cada vértice v V, existe un vértice u S, u = v, tal que u es adyacente a v. El número total dominación(G) es igual a la cardinalidad de un conjunto dominante total mínimo de G. el número de dominación total de la gráfica G en la figura 1.3 es de cuatro, es decir, (G) = 4; un -conjunto{es Steve, Teresa,Renu, Pete}.

A continuación, los vértices de una gráfica ser de dos tipos:

(i) los que representan a los miembros de una sociedad de la exploración,

(ii) aquellos que representan lAhabilidades (ver figura 14).

(iii) En esta gráfica, una arista entre una persona y una habilidad significa que esa persona tiene experiencia en esa área de habilidad. Queremos enviar una expedición paraestablecer un campamento y explorar algún lugar remoto del mundo. Con el fin de ahorrar costos, queremos enviar el menor número posible de personas, pero tenemos que estar seguros de que cada...