Forum de mathématiques - Bibm@th.net

Bonjour,

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

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

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

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).

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

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.

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

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