Grafos: conjuntos dominantes
Coloca estações de modo a que todos os pontos do mapa fiquem cobertos e descobre o menor número que chega: o número de dominação do grafo.
📖 Começa aqui: lê os passos da «Lição» por ordem (1, 2, 3 …) e responde a cada pergunta. Depois continua com «Praticar».
- França: 12.º ano
- Rússia: 7.º ano
- Irão: 12.º ano
Guia
Os grafos não fazem parte do programa de Matemática do ensino básico em Portugal; este estúdio é uma extensão. Imagina que se colocam caixas multibanco em alguns cruzamentos de uma vila. Cada cruzamento tem de ter uma ou ficar a uma rua de distância de uma. Modelamos isto com um grafo: os cruzamentos são vértices e as ruas são arestas. Um vértice do conjunto domina-se a si próprio e aos seus vizinhos.
Um conjunto de vértices é dominante se todos os vértices do grafo pertencem ao conjunto ou são vizinhos de um vértice do conjunto. O menor número de vértices de um conjunto dominante é o número de dominação, escrito γ(G); um conjunto dominante desse tamanho é um conjunto dominante mínimo.
«Minimal» e «mínimo» não são o mesmo. Um conjunto minimal deixa de dominar se retirares qualquer um dos seus vértices; um conjunto mínimo tem o menor número possível de vértices. Cada vértice domina no máximo Δ + 1 vértices (Δ é o maior grau), por isso n vértices exigem pelo menos n a dividir por Δ + 1, arredondado por excesso.