Graphes Valués

[invite587a1462]

Bonjour à tous,

Je suis en MPSI, option informatique. La question que j'aimerais vous poser est soulevée dans un DM d'info que j'ai à faire, mais c'est entièrement une question de maths.

Le sujet est le deuxième problème du concours mines-ponts 2008, accessible via le lien suivant: http://minesponts.scei-concours.org/.../info-2008.pdf. La question qui me tracasse est la question 25: c'est la deuxième question de la 4ème partie (pour y répondre, la lecture des parties 1, 2 et 3 n'est absolument pas nécessaire, il suffit de connaître les notations introduites en tout début de problème).

Je ne parviens absolument pas à établir l'inégalité demandée. Quelqu'un pourrait me mettre sur la voie??

Merci,


Cartapuces.
-----

[acx01b]

salut

tu prends les arrêtes de ton tour T, et tu les minores par les arrêtes qui sont dans ton Eval

un sommet u_a de ton tour T qui est dans U, dont les 2 sommets voisins sont u_b et u_c, tu peux minorer : (u_b,u_a) + (u_a,u_c) par eval2(....,u_a)
reste à trouver un bon minorant pour les sommets de ton tour qui ne sont pas dans U, et ça devrait fonctionner

[invite587a1462]

Bonjour,

Je ne vois pas très bien ce que tu veux dire. j'ai effectivement essayé de minorer le poids des arrêtes du tour T par celui des arrêtes de mon eval, mais je ne vois pas comment faire apparaître le facteur 1/2.
En fait, l'inégalité demandée revient à montrer que:

la somme des arrêtes dont les sommets sont dans U est supérieure ou égale à partie entière ( 1/2 * eval1(...)+eval1(...) + eval2(...) ).

Comme tu me l'as dit, j'ai sommé le poids des arrêtes des sommets dans U et les ai majoré par une somme des eval2(..., u_a), un sommet sur deux. Mais je n'arrive pas à conclure...

[acx01b]

prends un graphe à 4 sommets : a,b,c,d
ton tour c'est (a,b,c,d)
ta chaine c'est (a,b)
U = (c,d)
U' = U union {a,b} = (a,b,c,d)

poids(tour) = (a,b) + (b,c) + (c,d) + (d,a)
eval(chaine) = (a,b) + 1/2 (min(b,U) + min(c,U') + min2(c,U') + min(d,U') + min2(d,U') + min (a,U))

(b,c) + (c,d) est minoré par min(c,U') + min2(c,U')
(c,d) + (d,a) est minoré par min(d,U') + min2(d,U')
(b,c) est minoré par min(b,U)
(d,a) est minoré par min (a,U)

donc 2 ((b,c) + (c,d) + (d,a))
est minoré par :
min(b,U) + min(c,U') + min2(c,U') + min(d,U') + min2(d,U') + min (a,U)

[A voir en vidéo sur Futura]