Forum de mathématiques - Bibm@th.net

Glozi

Invité

Un réseau routier

Bonsoir,
C'est l'histoire d'un roi un peu fou, qui règne sur une grande région. Dans cette région, il y a plein de villes (un certain nombre $N\geq 2$, que seuls les plus érudits connaissent). Le roi décide un jour de construire un réseau routier dans son royaume. Mais il a un peu la folie des grandeurs, il décide qu'entre chaque paire de villes il y aura une et exactement une route directe qui les relie (pour les curieux, combien cela fait-il de routes en fonction de $N$).

Cependant, une fois que les routes ont été construites, on se rend compte qu'en fait, elles sont toutes trop étroites et ne peuvent être empruntées que dans un sens ! Le roi doit alors dire pour chaque route dans quel sens elle sera orientée. (exemple : pour l'unique route entre Bordeaux et Strasbourg, le roi doit dire si cette route ira de Bordeaux vers Strasbourg, ou sinon de Strasbourg vers Bordeaux).

Fatigué par tout cela (et ayant certainement la flemme de réfléchir), le roi commence alors à tirer à pile ou face pour chaque route !
Les sujets, inquiets, commencent à se lamenter !

La reine les rassure :
"Ne vous en faites pas, je ne garantis pas que ce réseau routier sera parfait. Néanmoins, une fois que le roi aura fini je vous garantis que nous pourrons trouver une ville vers laquelle tous les sujets pourront se rendre en passant par au plus une ville intermédiaire, et cela quelque soit leur ville de départ. Nous n'aurons qu'à y construire notre palais !"

La reine a-t-elle raison, pourquoi ?

Bonne chance :)

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 220

Re : Un réseau routier

Bonsoir Glozi,
à te lire très vite ça me fait un peu penser à l'énigme avec les diagonales que j'avais posée il y a quelques temps..

Glozi

Invité

Re : Un réseau routier

Bonsoir,
Tu parles peut-être de ce fil https://www.bibmath.net/forums/viewtopic.php?id=14723  ou d'un autre ?
En tout cas si c'est bien ce fil dont tu évoques, j'ai l'impression que ce sont deux problèmes assez différents (tu me montreras peut-être le contraire). Dans mon problème, on ne s'intéresse pas vraiment à la disposition des routes dans l'espace (et on n'a aucune information sur leur croisements éventuels). Et même si dans le plan (sur une carte) deux de mes routes s’intersectent, cela ne veut pas dire qu'on a le droit de passer d'une route à une l'autre.

Je ne l'avais pas explicitement dit mais il faut imaginer qu'il n'y a des ronds-points que dans les villes ! on peut aussi imaginer que si deux routes se croisent, alors c'est que l'une passe au dessus de l'autre (avec un pont par exemple).

Bonne soirée

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 801

Re : Un réseau routier

Bonsoir,

Il est peut être intéressant d'écrire le problème en utilisant la matrice d'incidence du graphe (cf ici).

Dans le cas présent, cette matrice est antisymétrique... mais je n'ai pas plus creusé !

Roro.

Glozi

Invité

Re : Un réseau routier

Rebonsoir,
Roro, j'ai regardé le lien, je ne connaissais pas vraiment cette notion. Mais dans notre cas la matrice qui est définie n'est pas carrée (du moins quand $N\geq 4$, pour le graphe que j'imagine où les villes sont les sommets et les routes sont les arêtes).
En revanche si on définit la matrice $A$ de taille $N\times N$ par $A_{i,j}=1$ si la route va de $i$ vers $j$, $A_{i,j}=-1$ si la route va de $j$ vers $i$, et $A_{i,j}=0$ si $i=j$, alors cette fois $A$ est bien antisymétrique ! (cela ressemble davantage à la définition de la matrice d'adjacence).
Bonne soirée

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 801

Re : Un réseau routier

Exact Glozi, je voulais parler de cette matrice $a_{ij}=+1$ si une route va de $i$ vers $j$, et $a_{ij}=-1$ si une route va de $j$ vers $i$.

Roro.

Dernière modification par Roro (26-04-2023 07:29:18)

Wiwaxia

Membre

Lieu : Paris 75013

Inscription : 21-12-2017

Messages : 438

Re : Un réseau routier

Bonjour,

Il y a des configurations problématiques pour les graphes orientés, par exemple lorsque les arêtes sont systématiquement orientées vers le sommet de rang maximal:

A_i,j = +1 si j>i sinon si j<i alors A_i,j = -1 ;

comme on peut le constater sur le schéma de gauche, où l'on trouve
a) un sommet inaccessible (n° 1),
b) un autre dont on ne peut sortie (n° 4).

IL faut que par rapport à tout sommet donné, les arêtes concourantes ne soient pas toutes orientées dans le même sens; une exemple simple consiste à envisager pour deux sommets consécutifs, une orientation vers le sommet de rang le plus élevé modulo N - soit ici:

en posant k = (j mod 4) - (i mod 4)
si |k| = 1 alors Ai,j = +1 si k = 1 sinon Ai,j = -1 ;
si |k| > 1 alors Ai,j = +1 si j > i sinon Ai,j = -1 .

cela conduit à la matrice suivante:

0 _ +1 _ +1 _ -1
-1 _ 0 _ +1 _+1
-1 _ -1 _ 0 _+1
+1 _ -1 _ -1 _ 0

Dans le cas d'une orientation aléatoire, cela se traduit par une relation sur les lignes et les colonnes.

Relations à vérifier.

Glozi

Invité

Re : Un réseau routier

Bonjour,
Wiwaxia, merci pour ta réponse et tes dessins ! Sur ton graphe de gauche, il est effectivement impossible d'atteindre le sommet 1 en partant d'une autre ville, et il est impossible de quitter le sommet 4. Cependant, le sommet 4 convient parfaitement pour être le sommet auquel fait référence la reine. Effectivement, quelque soit le sommet de départ on peut atteindre le sommet 4 en moins de deux arêtes. Si on est dans le sommet 4, on ne bouge pas c'est bon, sinon il suffit d'emprunter une arête pour atteindre le sommet 4. (au passage la reine a seulement parlé d'atteindre le sommet 4, elle n'a jamais parlé du voyage retour !)

Dans ton dessin de droite, tous les sommets conviennent pour répondre à la condition de la reine, excepté le sommet 2 : il est impossible d'aller du sommet 3 au sommet 2 en moins de 2 arêtes. (mais la reine n'avait pas parlé d'unicité, donc tant qu'on trouve au moins un sommet qui fonctionne la reine n'est pas en tort !).

Bref dans mon problème si le roi a (par chance) créé un réseau où l'une ville n'a aucune des routes qui part d'elle, alors cette ville convient car on pourra l'atteindre depuis n'importe quelle autre ville en passant par une seule route ! (bien sûr, il est très peu probable qu'on soit dans ce cas là).

Bonne journée.

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 862

Re : Un réseau routier

Bonjour à tous !

Cet énoncé me paraissait bizarre ... il faut bien lire ce que dit la reine !

Le peuple a raison de se lamenter, car comme dit ci dessus, elle promet juste qu'au moins une des villes sera atteignable au plus en 2 routes ... elle ne dit pas que ce sera vrai pour n'importe ville à ville !!!

J'avais pensé à la ville 4 de Wiwaxia, ville qui deviendra la ville du palais, et qui deviendra vite bondée !!!

Mais je suis en panne pour le moment ...

Bernard-maths

Glozi

Invité

Re : Un réseau routier

Effectivement en y réfléchissant bien, la reine ne promet pas tant que ça (mais sa formulation peut induire en erreur les sujets, satanés politiciens !) Reste tout de même à voir si ce qu'elle promet est quand même toujours vrai, où s'il y a des configurations qui mettent en défaut les dires de la reine !

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 801

Re : Un réseau routier

Bonsoir,

Je persévère un peu : je note $M$ la matrice $N\times N$ définie par
$M_{ij} = 1$ si le chemin va de la ville $i$ vers la ville $j$.
$M_{ij} = 0$ sinon.

Ainsi, le coefficient $(i,j)$ de la matrice $M^k$ donne exactement le nombre de chemins allant de la ville $i$ vers la ville $j$ en $k$ étapes.

La question est donc de savoir si une des lignes (disons la ligne $i_0$) de la matrice $\mathrm{Id}+M+M^2$ ne contient aucun $0$ : si c'est le cas alors depuis la ville $i_0$ on pourra atteindre toutes les autres villes en $0$, $1$ ou $2$ déplacements.

Je m'arrête la pour l'instant mais je continuerai peut être !

Roro.

P.S. J'ai inversé les flèches : je suis en train de répondre à la question : existe-t-il une ville à partir de laquelle on peut aller vers toutes les autres en au plus deux déplacements. Pour répondre à la question initiale (qui était "existe-t-il une ville qui est atteignable depuis n'importe laquelle des autres villes en deux déplacements", il suffit d'inverser le sens des déplacements dans mon raisonnement).

Dernière modification par Roro (26-04-2023 21:00:35)

Glozi

Invité

Re : Un réseau routier

Bonsoir,
Oui effectivement, après ton message j'avais aussi essayé de traduire matriciellement le problème. J'avais posé $N$ tel que $N_{ij}=1$ si $i=j$ ou si il y a une route de $i$ vers $j$ (et $N_{ij}=0$ sinon).
Alors si dans $N^2$ on trouve une ligne sans $0$, la reine aura raison.
En comparant avec ta matrice, on a en fait $N=M+Id$. La différence est qu'en quelque sorte je rajoute une arête de $i$ vers $i$ pour chaque $i$, ce qui nous autorise à ne pas bouger !

(NB : la condition $N^2$ possède une ligne sans $0$ est en fait équivalent à ta condition sur $Id+M+M^2$ car $N^2=Id+2M+M^2$ et que tous les coefficients des matrices considérées sont des entiers positifs).

Dans tous les cas ce n'était pas du tout la manière dont j'envisageais le problème, mais je suis curieux de voir si une preuve d'origine algèbre linéaire peut donner un argument pour conclure ? Sinon, la prochaine fois je poserai la version matricielle ce problème en laissant les gens penser que c'est de l'algèbre linéaire mouahah !

Bonne soirée

Glozi

Invité

Re : Un réseau routier

Bonjour,
Je viens de me souvenir de ce post. Je donne une solution

▼solution

(faire un schéma sinon on ne comprend rien).
Récurrence sur $N$ le nombre de villes.

Considérons $N$ villes, par hypothèses de récurrence notons $C$ la capitale, $A_1$ les villes qui accèdent à la capitale en $1$ coup, et $A_2$ les villes qui accèdent à la capitale en 2 coups.

Si on rajoute une $N+1$ ième ville $V$, alors si on a une route de $V$ vers $C$ ou de $V$ vers une des villes de $A_1$, alors $C$ convient toujours pour être la capitale. Sinon, c'est que la route entre $C$ et $V$ va de $C$ vers $V$, de même toutes les routes entre une ville de $A_1$ et $V$ vont de la ville de $A_1$ vers $V$. Mais alors $V$ convient pour être la capitale : les villes de $A_1$ et $C$ atteignent $V$ en un coup, les villes de $A_2$ atteignent en un coup une ville de $A_1$ laquelle atteint $V$ en un coup.

Voici en bonus un petit corolaire avec l'interprétation matricielle de Roro,

Définition : Une matrice $A$ de $M_n(\mathbb{R})$ est dite "royale" si elle vérifie les propriétés suivantes :
- $A$ a des coefficients dans $\{0,1\}$.
- les coefficients diagonaux sont $1$.
- si $i\neq j$ alors $A_{i,j}=1\Leftrightarrow A_{j,i}=0$.

Théorème : quelque soit $n\geq 1$, quelque soit la matrice "royale" $A$, il existe un couple $(i,j)$ tel que $(A+E_{i,j})^5$ n'ait que des coefficients strictement positifs. (ici $E_{i,j}$ est la matrice élémentaire avec un $1$ en position $(i,j)$ et des $0$ partout ailleurs).

(Traduction : la reine dit "ne vous inquiétez pas, une fois que le roi aura fini, nous n'auront qu'à élargir une route bien choisie et la rendre à double sens, de sorte qu'on pourra se rendre de n'importe quelle ville de départ à n'importe quelle ville d'arrivée en utilisant 5 routes ou moins".)

Amusant : trouver $n$ et une matrice royale, telle que la propriété soit fausse si on remplace l'exposant $5$ par un exposant $4$.
Bonne journée

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Un réseau routier

Bonjour,

Pour ne pas s'embêter on peut raisonner par récurrence:

C'est vrai pour N = 2..

Supposons que ce soit vrai pour un rang $N \ge 2$ ( tout graphe d'ordre N etc...) et montrons que c'est vrai au rang $N+1$.

Soit donc une région R (avec le même roi un peu fou, ou un autre carrément fêlé ...) comprenant $N+1$ villes, toutes connectées par des voies à sens unique.

Soit A une de ces villes.
Si les N autres vont toutes vers A, c'est fini: A vérifie la propriété pour les $N+1$ villes.
Si au contraire de A part une voie, elle arrive à une ville B parmi $N$.
Les villes de R' = R\{A} , au nombre de N, sont reliées entre elles par des voies en sens unique.
Par l'hypothèse de récurrence il existe une ville V de R' telle que toute ville de R'  un trajet y conduise en passant au plus une fois par une ville de R'.
Par ailleurs si un prince ou un manant part de A, il se peut se rendre d'abord en B pour une conclusion similaire.

Il existe donc toujours une solution pour un graphe à N+1 villes vérifiant les contraintes.

Ainsi la propriété est vraie quelle que soit l'importance de la région.

A.

Dernière modification par bridgslam (28-08-2023 09:16:24)

Glozi

Invité

Re : Un réseau routier

Bonjour,

Par ailleurs si un prince ou un manant part de A, il se peut se rendre d'abord en B pour une conclusion similaire.

Attention, je pense que tu vas un peu vite, si par malchance pour aller de B vers V il faut forcément passer par une ville intermédiaire (disons C) dans R', alors pour aller de A vers V ton chemin sera si j'ai bien compris A--> B-->C-->V qui fait deux étapes intermédiaires et non une seule.

Bonne journée

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Un réseau routier

Bonjour,

J'avais compris dans l'énoncé "au plus une ville" par ne pas passer deux fois par la même, et non le nombre d'étapes intermédiaires.
C'est donc différent.

A.