enigmegraphe
2022-06-13 23:23:36
Considérons le graphe d'une grille carrée, de taille n*n.
Par exemple, pour n=5 :
http://sketchtoy.com/70760924
Si on prend deux sommets quelconques, il existe bien sûr plusieurs chemins différents permettant de lier l'un à l'autre.
Voici par exemple 3 chemins différents permettant de relier les 2 points verts :
http://sketchtoy.com/70760927
Le chemin rose est très long, en revanche le chemin vert et le chemin orange sont tous deux des "plus courts chemins" : je ne peux pas relier les deux points verts en passant par moins de 4 arêtes.
Enigme :
a) Est-il possible de trouver n "plus courts chemins" qui sont tous disjoints les uns des autres (ie ils ne doivent pas passer par les même sommets) et qui couvrent tous les sommets de la grille ?
Réponse :Evidemment que oui... voici deux exemples pour la grille 5x5, qui se généralisent évidemment. Il existe bien sûr plein d'autres exemples.
http://sketchtoy.com/70760930
http://sketchtoy.com/70760929
b) Quel est le nombre minimal de "plus courts chemins" disjoints deux à deux dont on a besoin, pour recouvrir une grille de taille n x n ?
Réponse :Jsp. pour n=1, n=2 ou n=3 on prouve facilement qu'on ne peut pas faire mieux que n chemins. Pour le cas général, c'est moins clair, mais j'imagine que c'est pareil.
enigmegraphe
2022-06-13 23:28:17
Le 13 juin 2022 à 23:24:37 :
Non Kévin on fera pas ton devoir maison de théorie des graphes
Je me doute que tu n'es pas capable de le faire tkt.
C'est pas un DM, c'est une "énigme" qu'on m'a posé mais le type qui me l'a posée n'a pas non plus la solution.
Je cherche dans mon coin et je ne lirai pas le détail des différentes réponses tant que j'aurai pas abandonné, mais au cas où j'abandonne j'aimerais bien que quelqu'un ait trouvé une solution élégante.
enigmegraphe
2022-06-17 01:41:49
Je n'ai toujours pas la réponse, mais visiblement c'est vraiment un problème assez chaud.
Pour vous donner une idée, je l'ai posée à plusieurs chercheurs spécialistes de la théorie des graphes, ainsi qu'à des doctorants en informatique et post doc (tous plutôt familiers avec la théorie des graphes) et pour l'instant absolument personne n'a trouvé la réponse, ni même fait une avancée majeure. (Alors qu'ils sont plusieurs dans le lot à y avoir réfléchi plusieurs heures, et qu'on se partage nos idées dès qu'on en a).