le nombre maximal de villes
Une compagnie aérienne opère en sens unique entre chaque paire de villes d'un pays composé de $N$ villes de sorte que toutes les villes soient joignables à partir de n'importe quelle ville (pas nécessairement directement).
On suppose que la planification de vol consistant à des vols de plus court chemin (y compris un nombre minimal de vols de sorte que toutes les villes soient joignables à partir d'une autre ville au moins une seule fois) se compose d'au plus 2013 vols. trouver la valeur maximale possible de $N$.
On suppose que la planification de vol consistant à des vols de plus court chemin (y compris un nombre minimal de vols de sorte que toutes les villes soient joignables à partir d'une autre ville au moins une seule fois) se compose d'au plus 2013 vols. trouver la valeur maximale possible de $N$.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Voilà, hilbert2012, je le trouve la formulation de cet énoncé bien compliquée.
Les vols directs sont autorisés, aller, mais pas retour ? Et puis quoi encore ?
Voudrais-tu essayer de le dire plus simplement STP ?
Si on enfile toutes les villes comme des perles sur un collier, on pourra toujours passer de l'une à une autre, avec moult escales.
???
Sûr que l'énoncé n'est pas d'une clarté cristalline.
Peut-être le problème du voyageur de commerce ? http://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce
Amicalement.
Je m'excuse pour la manque de clarté dans l'énoncé. Je l'ai traduit de l'anglais, je vous mets la version anglaise de l'énoncé.
An airway company operates one way flights between some pairs of cities of a country consisting of $N$ cities so that any city is reachable from any city (not necessarily directly).Suppose that in any such flight scheduling the shortest (including minimal number of flights) closed trip visiting each city (at least once) consists of at most $2013$ flights. Find the maximal possible value of $N$.
Le pire des cas n'est-il pas, justement, le collier de perles?
"between some pairs of cities of a country"
traduit par
"entre chaque paire de villes d'un pays"
Soit $n=2013$. Trouver le plus grand entier $N$ tel que pour tout graphe orienté connexe à $N$ sommets, il existe un chemin $(x_0,x_1,\ldots,x_k)$ avec $k\le n$, $x_k=x_0$ et tel que $(x_i,x_{i+1})$ est une arête pour tout $i$.
Edit : j'ai oublié de dire que tous les sommets figurent parmi l'un des $x_i$.
Soit $n = 2013$. Déterminer le plus grand entier $N$ tel qu'il existe un graphe orienté fortement connexe à $N$ sommets dans lequel le plus court circuit passant par chaque sommet au moins une fois soit de longueur $\leq n$.
Où un circuit de longueur $\ell$ est une suite de $(x_0,\ldots,x_\ell)$ telle que $(x_i,x_{i+1})$ soit une arete pour tout $i$ et $x_\ell = x_0$.
PS: La réponse me semble alors évidente. Si $G$ est un graphe orienté à $N$ sommets solution du problème et $\ell$ la longueur minimal d'un circuit passant par tous les sommets. Alors $N \leq \ell \leq n$. Pour un graphe circulaire orienté à $N=n$ sommets, on a égalité d'où le résultat $N = n = 2013$.
Au final est-ce que la réponse est $n=2013$ ? J'ai beau essayer de trouver une solution utilisant la combinatoire simple sans entrer dans les détails de la théorie des graphes, en vain.
Merci.