Exercice sur les graphes simples

[pluto74]

Bonjour,

Je suis tombé sur cet exercice sur les graphes simples aux allures très sympathiques ! :we: Cependant je n'arrive pas à le résoudre !

Les sommets d’un graphe simple sont occupés par deux factions en guerre. La guerre est une succession de batailles. Une bataille se déroule de la façon suivante : un sommet, relié à (strictement) plus d’ennemis que d’amis, passe à l’ennemi. Quand il n’y a plus de bataille possible, c’est-à-dire plus de sommet susceptible de passer à l’ennemi, la guerre est finie. Montrer que la guerre ne peut pas durer éternellement.

D'avance merci ! :id:

[ThSQ]

Je ne suis pas sûr de comprendre l'énoncé car si on place 4 sommets sur un carré avec une alternance ami-ennemi : 1 - 2 - 1 - 2) il y a un va-et-vient perpétuel entre 1 - 2 - 1 - 2 et 2 - 1 - 2 - 1 :help:

[pluto74]

je pense que les batailles doivent avoir lieux les unes après les autres. Ainsi, dans le cas du carré dont tu me parlais, dès qu'un sommet change de camp l'affaire est terminée ou presque. Qu'en penses tu??

[ThSQ]

Qu'en penses tu??

Sans doute sinon ça marche pas.
Bon faut donc montrer que quel que soit l'ordre dans lequel on fait les batailles on finit par un état stable (mais pas forcément le même).

Avec ces hypothèses c'est facile :

décroit strictement à chaque bataille.

[pluto74]

décroit strictement à chaque bataille.

Je ne vois pas pourquoi le nombre d'ennemis serait strictement décroisant ? Imagine par exemple un sommet "allié" relié a 3 autres sommet "ennemis" qui ont pour unique arrête celle qui la relis à ce sommet allié (et donc ne deviendront jamais allié) contre un seul allié voisin, alors le sommet allié tombera forcement...

[HTML]
2
/
... 1 -1 - 2
\
2[/HTML]

[pluto74]

Arf excuse moi en faîte je t'avais mal lu tu parlais d'hypothèses... :briques:

Mais je n'avance toujours pas de mon coté ... :cry:

[pluto74]

Je remonte le sujet une fois au cas ou quelqu'un aurait une idée...
ThSQ je t'ai aussi rep sur FSG