@nodgim: Tu es toujours sur une case (un pavé), tu ne te deplace que de case en case voisine (se touchant par un morceau de segment de longueur non nulle), et tu comptes 1 pour chaque case de ton chemin.

ça me semble chaud à trouver, cette preuve !

En revanche, on peut facilement vérifier, pour un extrait de pavage ( une quinzaine de pavés groupés ) si ça marche ou pas.
On part d'un pavé qu'on numérote 0. Les voisins immédiats sont numérotés 1. Les voisins des voisins sont numérotés 2, les suivants 3, etc...

Il y a problème lorsque un pavé de numéro n+1 est en relation avec
au moins 2 pavés de numéro n. 

La règle est donc simple. Mais trouver un groupement pour lequel ça marche pour chaque pavé numéroté 0 semble être une gageure....

On remarquera qu'on peut rechercher un "graphe planaire" et considérant que les nœuds symbolisent les paves et les arcs le voisinage de chaque pavé. Un graphe avec la propriété recherchée est dit "geodetic" . Il y a pas mal de mauvaises manières de répondre à ce problème, je n'en ai pas vu de bonne pour le moment.

Bonjour,

Voici ma réflexion pour l'instant:
Supposons que les pavés aient tous une taille bornée (sinon, c'est facile de trouver un pavage qui marche)
Considérons notre pavage comme un graphe planaire (un sommet par pavé, un arc entre eux si les pavés se touchent)

On peut déjà remarquer qu'une infinité de pavé touchent deux autres pavés au moins (sinon, on obtiendrait des cercles concentriques, et donc des pavés de taille aussi grande que souhaitée => pas borné)

De là, on peut déduire qu'étant donné deux points vérifiant cette propriété, on peut trouver un cycle passant par ces deux points.

Il est facile de montrer que l'on peut trouver un cycle de longueur paire, en effet deux cycles de longueur impaire se touchant forment un cycle de longueur paire.

Pour le construire, il suffit donc de prendre deux sommets A et B et trouver un cycle passant par eux deux. Si il est de longueur paire, c'est gagner, sinon, on prend un sommet C, et on cherche un cycle passant par B et C. S'il est de longueur impaire, le cycle somme des deux précédents cycles est de longueur paire.

on en déduit donc que l'on peut toujours trouver deux sommets tel qu'il existe deux chemins de même longueur les reliant (on les prends opposés sur le cycle de longueur paire)

Reste le problème du plus cours chemin:
On peut trouve un graphe planaire contenant un cycle paire (longueur 4) et tel qu'il n'existe qu'un seul chemin de longueur minimale: la clique d'ordre 4 (4 sommets reliés de toute les manières)

Or on peut trouver des cycles paire de taille aussi grande que l'on veut. Si l'on a un cycle pair de longueur 2n supérieure à 6, il faut que tous les sommets soient à moins de n-1 étapes

Après, je suis bloqué...

On peut montrer avec une petite étude de cas qu'un graphe géodétique planaire infini ne peut pas contenir un cycle de taille 6. Si on montre ça pour toute taille paire supérieure à 6, c'est gagné...

@nodgim : je ne comprends pas quand tu dis "2 boucles voisines sont interconnectées par 2 points voisins". Qu'est ce qui empêche que les deux points ne soient pas voisins, comme dans la figure ci-dessous, à gauche ?



Mais ça ne change pas la conclusion de l'existence d'un cycle de longueur paire. Par contre, l'existence d'un cycle de longueur paire ne suffit pas à contredire l'unicité du trajet le plus court, cf la figure de droite.

@Clydevil : à tout pavage, on peut associer un graphe unique, si on considère qu'un graphe est la donnée abstraite d'un ensemble de sommets et d'arêtes (=des paires de sommets). Mais inversement, à un graphe, je peux associer plusieurs "pavages" différents. C'est pour ça que j'ai besoin que tu définisse ce que tu appelles "pavé" pour te répondre.
* un pavé doit-il être un polygone ?
* un pavé doit-il être d'aire finie ?
* un pavé doit-il être borné ?
* doit-il y avoir un nombre fini de pavés différents ? si oui, qu'appelle-t-on "différents" ?

Ebichu a écrit:

@nodgim : je ne comprends pas quand tu dis "2 boucles voisines sont interconnectées par 2 points voisins". Qu'est ce qui empêche que les deux points ne soient pas voisins, comme dans la figure ci-dessous, à gauche ?

http://www.prise2tete.fr/upload/Ebichu-2figs.png

Mais ça ne change pas la conclusion de l'existence d'un cycle de longueur paire. Par contre, l'existence d'un cycle de longueur paire ne suffit pas à contredire l'unicité du trajet le plus court, cf la figure de droite.

@Clydevil : à tout pavage, on peut associer un graphe unique, si on considère qu'un graphe est la donnée abstraite d'un ensemble de sommets et d'arêtes (=des paires de sommets). Mais inversement, à un graphe, je peux associer plusieurs "pavages" différents. C'est pour ça que j'ai besoin que tu définisse ce que tu appelles "pavé" pour te répondre.
* un pavé doit-il être un polygone ?
* un pavé doit-il être d'aire finie ?
* un pavé doit-il être borné ?
* doit-il y avoir un nombre fini de pavés différents ? si oui, qu'appelle-t-on "différents" ?

Les configurations que tu représentes ne sont pas valables, il me semble. Mets les pavés par dessus, il me semble que ça ne marche pas.

Il y a une règle dont je n'ai pas parlé, je croyais ne pas en avoir besoin:
Une relation du graphe entre 2 sommets, avec des sommets intermédiaires, ne peut être "shuntée" par une relation extérieure qui oublierait des sommets. Si on représente un extrait du graphe, il manquera toujours les relations extérieures. Celles ci ne peuvent contourner les sommets sans aucune relation.

En matière de généralisation, j'avance que ce problème n'est pas plus compliqué avec des pavés biscornus, du genre géographie des pays. ça me rappelle beaucoup le problème des 4 couleurs.

Exact, je n'avais qu'à réaliser le découpage en pavés, ça m'aurait éviter de dire des c....

C'est bien ce que je craignais, tu es trop ambitieux

Les graphes planaires géodétiques sont décrits depuis une thèse de 1964. Je n'ai pas accès à la thèse mais l'article suivant donne le résultat principal :

http://www.sciencedirect.com/science/ar … 0068800353

N'ayant pas la démo sous la main, j'en suis réduit à croire ce monsieur sur parole, mais il a l'air de dire que c'est assez long à démontrer.

Le résultat, si je comprends bien, implique qu'un graphe planaire géodétique est une arborescence dont les noeuds non triviaux sont soit un cycle impair, soit le graphe complet K4 éventuellement complété de quelques noeuds, comme dans le message #14.



Ce type de structure ne permet pas d'obtenir de ce que tu accepterais de qualifier de "pavage"...