Tracer un graphe a partir d'un ordre lexicographique

[Inpu]

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 :marteau:

Bonne soirée :lol3:

[Ben314]

Salut,
En fait, ton tableau 2 donne les sommet d'arrivé pour les 7 arcs (les extt(uj)) mais pas les sommets de départ.
La fameuse phrase "On a numéroté lexicographiquement les arcs uj" signifie que les arrêtes dans le tableau sont rangées par ordre croissant du sommet de départ puis que pour un même sommet de départ, elle sont rangées dans l'ordre croissant des sommets d'arrivé (mais ça on s'en fout vu qu'on a la ligne donnant les sommets d'arrivé).
En regardant combien il y a d'arrêtes qui partent de chaque sommet (tableau 1), ça te permet de "reconstituer" la ligne qu'il te manque dans le tableau 2 c'est à dire les sommets de départ. Cette ligne est donc 1 2 2 2 4 5 5

[Inpu]

Merci beaucoup ! Donc si je comprend bien (j'essaye toujours de rephraser avec mes mots...), comme on constate qu'il n'y a qu'un arc qui part du sommet x1, on en déduit que la premier colonne du deuxieme tableau correspond à un arc dont le sommet initiale est x1 ? Et comme 3 arcs partent du sommet x2, on en déduit que les 3 colonnes suivantes correspondent a trois arcs dont l'extrémité initiale est x2 ?

[Ben314]

Oui, c'est ça.
Tes 7 "arcs" sont donc 1->5 ; 2->1 ; 2->3 ; 2->4 ; 4->3 ; 5->3 ; 5->4

Ce que l'on appelle "l'ordre lexicographique", c'est l'ordre des mots dans le dico : on compare d'abord la 1er lettre.
Si c'est pas la même on range en fonction de cette lettre et, si c'est la même, on regarde la lettre suivante.
Ici, ça veut dire qu'on range les "arcs" en regardant d'abord le N° du sommet de départ et, si c'est le même N°, on range en fonction N° du sommet d'arrivé.

[Inpu]

Merci beaucoup ! C'est bien plus clair maintenant :)

[Inpu]

Bonjour,

Je me permet de reposter à propos d'un exercice très similaire ou seul les données changent :



Comment 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

[Ben314]

Effectivement, il semble qu'il y ait une faute de frappe dans l'énoncé : dans l'ordre lexicographique, la 3 em arrête est (x2,x1) et les suivantes sont (x2,x5) et (x2,x7) : il n'y a pas d'arrête de x2 vers x4...