Vu comme c'est présenté, j'imagine donc qu'une station ne peut avoir que 4 directions possibles, 2 par ligne. On suppose qu'une ligne ne déssert une station qu'une seule fois ? Si oui, alors tu ne peux pas avoir plus de 12 stations. Car 4 directions depuis n'importe quelle station, et 3 autres possibles après la 1ère station desservie. Reste à vérifier qu'on peut réaliser un tel réseau.

Je dirais intuitivement 11 stations, dont la solution est relativement simple.

Au-delà, j'ai de sérieux doutes.

Si on ne peut pas repasser 2 fois par le même point pour un trajet : 11

Sinon, autant que l'on veut.

J'ai une majoration avec 17 sommets, pardon, "arrêts" :
* Chaque sommet est de degré 2 ou 4 suivant qu'il est situé sur une ou deux lignes, donc au plus 4.
* Prenons un sommet S. S est relié à au plus 4 sommets, et chacun de ces 4 sommets, à au plus 3 autres. Quant aux autres sommets, ils seraient à une distance de S supérieure à 2. 1+4+4*3=17, cqfd.

Sinon, voici une solution avec 13 sommets :


Je n'ai pas encore beaucoup cherché et je ne vois pas a priori de raison pour laquelle ce ne serait pas possible avec 17. Je continue à réfléchir.

Et voici une solution avec 15 sommets :



Ça devient de plus en plus tendu, donc j'ai bon espoir, soit de trouver un graphe pour 16 ou 17, soit de montrer que ça ne peut exister.

Note pour plus tard : faire une version plus lisible de ce sac de noeuds

Ma ligne de métro, en forme de fleur à pétales, est constituée de n+1 stations: une station centrale O et n stations périphériques S(n). Le cheminement en boucle du métro est: O – S(1) – O – S(2) – O S(3) – O – …..– O – S(n) – O – S(1). Pour les besoins de l’énigme, je peux superposer une seconde ligne identique centrée aussi sur O. De cette manière, je peux passer de n’importe quelle station en maximum deux arrêts.
Avec ce réseau, je pourrai avoir une infinité de stations répondant à la question, mais sans doute non conforme à l’esprit de ton énigme. Faut-il rajouter dans l’énoncé qu’un cycle de stations ne doit jamais repasser deux fois par la même station ?

C'est impossible pour 16 ou 17 sommets.

Remarquons déjà que s'il existe un sommet de degré 2, les deux sommets auxquels il est relié ne peuvent eux-même être reliés qu'à 3 autres sommets chacun, aussi il y a au plus 1+2+3*2=9 sommets dans le graphe.

Tous les sommets sont donc de degré 4 (chaque station est parcourue par les deux lignes de métro).

Ensuite, je suis allé faire un tour sur cette page : https://fr.wikipedia.org/wiki/Lexique_d … es_graphes

On cherche un graphe 4-régulier (tous les sommets sont de degré 4), et de diamètre 2 (la distance maximale entre deux sommets est 2) ; le graphe doit aussi être décomposable en deux cycles disjoints, élémentaires et même hamiltoniens (les deux lignes de métro), mais ceci n'est pas nécessaire pour conclure.

Sur ce lien : http://ijact.org/volume4issue5/IJ0450003.pdf il y a une démonstration du fait qu'il n'existe pas de graphe 4-régulier de diamètre 2 à 17 ou 16 sommets. C'est un peu lourdingue comme démonstration (il y a plein de petites étapes), l'anglais n'est pas très bon et le formalisme exagéré, mais ça marche.

Enfin, si j'en crois le titre de cet article, il a été démontré qu'il n'y a qu'une solution pour 15 sommets :

H. J. Broersma, A. A. Jagers, The unique 4-regular graphs on 14 and 15 vertices
with diameter 2, Ars Combinatoria 25 (C) (1988) 55–62.

Je suppose que ça peut se démontrer avec des arguments du même type que pour 16 et 17. Il y a peut être plus élégant.

Avec deux lignes, je ne fais pas mieux que six stations,      sachant qu'avec une seule, on est déjà à cinq.

Salut !

Très intéressant comme problème. J'ai trouvé 9 villes... (j'ai laissé mes 1ers essais avant d'arriver à ce résultat)

Je ne sais pas si on peut faire mieux...



Sur le 1er à 9 villes, on voit bien le principe, sur le second, on visualise mieux le circuit du 2ème métro.

Avec le réseau à 11 villes de golgot59, on ne profite pas de la possibilité de deux trajets longs. Voici ce que cela donne avec un réseau à 13 villes:
a-b / a-b-c / a-i-d / a-f-e / a-f / a-f-g / a-i-h / a-i / a-i-j / a-f-k / a-m-l / a-m
Mais est ce l’optimum ?
Avec le réseau à 15 villes de gwen27, sauf erreur de ma part, on ne n’arrive pas à passer de 1 à 7 ou de 1 à 11 au moins de 3 arrêts.
Par symétrie par rapport aux stations qui peuvent toutes être le point de départ, le réseau devra certainement être en forme de rosace régulière.

Mon réseau fonctionne.

Sous forme de matrice :
0    1    0    0    1    0    0    0    0    0    0    1    0    0    1
1    0    1    0    0    1    0    0    1    0    0    0    0    0    0
0    1    0    1    0    0    0    0    0    0    1    0    1    0    0
0    0    1    0    1    0    0    1    0    0    0    0    0    0    1
1    0    0    1    0    1    0    0    0    1    0    0    0    0    0
0    1    0    0    1    0    1    0    0    0    0    0    1    0    0
0    0    0    0    0    1    0    1    0    0    1    0    0    0    1
0    0    0    1    0    0    1    0    1    0    0    1    0    0    0
0    1    0    0    0    0    0    1    0    1    0    0    0    1    0
0    0    0    0    1    0    0    0    1    0    1    0    0    1    0
0    0    1    0    0    0    1    0    0    1    0    1    0    0    0
1    0    0    0    0    0    0    1    0    0    1    0    1    0    0
0    0    1    0    0    1    0    0    0    0    0    1    0    1    0
0    0    0    0    0    0    0    0    1    1    0    0    1    0    1
1    0    0    1    0    0    1    0    0    0    0    0    0    1    0


La matrice au carré :
4    0    1    2    0    2    1    1    1    1    1    0    1    1    0
0    4    0    1    2    0    1    1    0    1    1    1    2    1    1
1    0    4    0    1    2    1    1    1    1    0    2    0    1    1
2    1    0    4    0    1    2    0    1    1    1    1    1    1    0
0    2    1    0    4    0    1    1    1    0    1    1    1    1    2
2    0    2    1    0    4    0    1    1    1    1    1    0    1    1
1    1    1    2    1    0    4    0    1    1    0    2    1    1    0
1    1    1    0    1    1    0    4    0    1    2    0    1    1    2
1    0    1    1    1    1    1    0    4    1    1    1    1    1    1
1    1    1    1    0    1    1    1    1    4    0    1    1    1    1
1    1    0    1    1    1    0    2    1    0    4    0    2    1    1
0    1    2    1    1    1    2    0    1    1    0    4    0    1    1
1    2    0    1    1    0    1    1    1    1    2    0    4    0    1
1    1    1    1    1    1    1    1    1    1    1    1    0    4    0
0    1    1    0    2    1    0    2    1    1    1    1    1    0    4


Leur somme :


On retrouve l'ordre 4 en diagonale, logique... et 2 trajets en double pour chaque nombre.

Malheureusement, pour des raisons de symétrie, ça ne laisse que 15 liaisons de libres. Il en faudrait 16 pour rajouter un 16e point.
Il est rigolo de voir que je me suis amusé avec un parcours de cavalier pour construire la matrice noire. Je suis presque certain que celle d'ebichu présenterait la même particularité.

@gwen27 : je ne comprends pas de quel parcours de cavalier tu parles, mais je suis également certain que mon graphe présente la même propriété, car c'est le même que le tien - et pour cause, il n'en existe qu'un seul. C'est d'ailleurs un exercice pas si simple que de démontrer que nos deux graphes sont isomorphes. Je ne connais pas de programme qui fasse ça, alors je l'ai fait à la main avec Geogebra, et ça marche.