Grafi: insiemi dominanti
Colloca le stazioni in modo che ogni punto della mappa sia coperto e trova il numero minimo che basta: il numero di dominazione del grafo.
📖 Parti da qui: leggi i passi della «Lezione» in ordine (1, 2, 3 …) e rispondi a ogni domanda. Poi continua con «Esercizi».
- Francia: classe 12
- Russia: classe 7
- Iran: classe 12
Guida
Immagina di mettere dei bancomat ad alcuni incroci di una città. Ogni incrocio deve avere un bancomat oppure trovarsi a una strada di distanza da uno. Lo descriviamo con un grafo: gli incroci sono vertici e le strade sono lati. Un vertice dell'insieme domina se stesso e i suoi vicini. I grafi non sono nei programmi scolastici italiani: questo percorso è un ampliamento, adatto ai giochi matematici.
Un insieme di vertici è dominante se ogni vertice del grafo appartiene all'insieme oppure è vicino a un vertice dell'insieme. Il minor numero di vertici che un insieme dominante può avere è il numero di dominazione, che si scrive γ(G); un insieme dominante di quella dimensione è un insieme dominante minimo.
Minimale e minimo sono diversi. Un insieme minimale smette di dominare se togli un qualsiasi vertice; un insieme minimo ha il minor numero possibile di vertici. Ogni vertice domina al massimo Δ + 1 vertici (Δ è il grado massimo), quindi n vertici richiedono almeno il numero n diviso Δ + 1 arrotondato per eccesso.