Graphes et logique relationnelle
Problèmes de placement, relations d'ordre : modéliser avec un graphe.
Méthode de modélisation
1. Poser les contraintes
Lister toutes les informations : "A est à gauche de B", "C n'est pas à côté de D"...
2. Construire un tableau
Lignes = personnes/objets, Colonnes = positions Remplir par déduction : ✓ (possible), ✗ (impossible), ● (sûr)
3. Éliminer
Pour chaque case impossible, propager la contrainte sur les autres lignes/colonnes.
4. Conclure
Quand toutes les cases sont résolues, lire la solution.
Astuce
Les contraintes négatives ("X n'est pas à côté de Y") sont souvent sous-estimées : elles éliminent énormément de possibilités.