Inscription / Connexion Nouveau Sujet
Tracer un graphe a partir d'un ordre lexicographique
Bonsoir,
Je bloque complètement sur l'exercice suivant :
Je comprend qu'il y a 5 sommets de X1 à X5, qu'il n'y a qu'un arc qui part du sommet x1, 3 arc qui partent du sommet x2, etc...
J'imagine que k(uj) correspond à la capacité des arcs car c'est un réseau de transport.
Par contre, là ou je suis vraiment perdu, c'est à la phrase "On a numéroté lexicographiquement les arcs uj : ainsi u1 est l'arc (x1, x5) puis u2 est l'arc (x2, x1), etc..."
Comment on détermine que u1 correspond à l'arc x1, x5 ? De l'aide serait la bienvenue, j'ai tracé pas mal de graphe mais ça ne correspond pas aux tableaux.
Bonne soirée !
Je ne connaissais pas ce mode de définition d'un graphe, mais pourquoi pas...
Je pense que l'ordre lexicographique est simplement l'équivalent de l'ordre alphabétique.
Selon cet ordre : u1 < u2 < u3 < u4 < u5 < u6 < u7
Tu as le nombre de départs par sommets :
1 2 3 4 5
1 3 0 1 2 Donc les arcs seront comme ceci :
1 .
2 .
2 .
2 .
4 .
5 .
5 .
Il reste à compléter par le tableau des extrémités :
1 5 (3)
2 1 (5)
2 3 (2)
2 4 (4)
4 3 (4)
5 3 (4)
5 4 (1)
Pour faire apparaître un graphe de transport il faut faire apparaître une source (S) et un puits (P) :
Cool.
Si tu veux en tirer profit, tu lis ça juste une fois, puis tu refais l'exercice intégralement par toi même.
Bon courage 
!
C'est déjà fait ne t'en fais pas ! Le flot initiale en sortie était de 8, et j'ai pu l'optimiser jusqu'à 9 avec une chaine améliorante.
Bonjour,
Je me permet de reposter à propos d'un exercice très similaire ou seul les données changent :
Comme ce fait-il que dans l'énoncé ils disent que "u3 est (x2, x4)" ? D'après l'ordre lexicographique, u3 ne correspondait pas plutôt à (x2, x1) ?
Encore merci
...
!
Annuler
connectez vous
autre en Bts