Grafos: conjuntos dominantes
Coloca estaciones de modo que todos los puntos del mapa queden cubiertos y encuentra el menor número posible: el número de dominación del grafo.
📖 Empieza aquí: lee los pasos de la «Lección» por orden (1, 2, 3 …) y responde a cada pregunta. Después sigue con «Práctica».
- Francia: 12.º curso
- Rusia: 7.º curso
- Irán: 12.º curso
Guía
Los conjuntos dominantes no forman parte del currículo habitual de ESO ni de Bachillerato en España: este taller es una ampliación. Imagina que se ponen cajeros automáticos en algunos cruces de una ciudad. Cada cruce debe tener uno o estar a una calle de uno. Lo modelamos con un grafo: los cruces son vértices y las calles, aristas. Un vértice del conjunto se domina a sí mismo y a sus vecinos.
Un conjunto de vértices es dominante si todo vértice del grafo está en el conjunto o es vecino de un vértice del conjunto. El menor número de vértices que puede tener un conjunto dominante es el número de dominación, que se escribe γ(G); un conjunto dominante de ese tamaño es un conjunto dominante mínimo.
Minimal y mínimo son cosas distintas. Un conjunto minimal deja de dominar si le quitas cualquier vértice; un conjunto mínimo tiene el menor número posible de vértices. Cada vértice domina como mucho Δ + 1 vértices (Δ es el mayor grado), así que n vértices necesitan al menos n dividido entre Δ + 1, redondeado hacia arriba.