← Logică și algoritmi
Legătura cu informatica
Harta este un graf: intersecțiile sunt vârfurile, iar străzile sunt muchiile.
- intersecțiile cu stații formează o mulțime dominantă: orice vârf este în mulțime sau are un vecin în ea;
- pentru grafurile mari, nu se cunoaște un algoritm rapid care să găsească cea mai mică mulțime dominantă;
- problema se rezolvă încercând sistematic alegerile, cu metoda backtracking;
- problema apare la amplasarea spitalelor, a antenelor de telefonie și a stațiilor de încărcare.