Bonjour, je bloque de nouveau sur un problème de graphes, il s´agit d´une situation de la modélisation d´un jeu:
Les sommets d´un graphe simple sont sujets à un guerre entre une faction A et une faction B: Dans chaque bataille, un sommet adjacent qui a plus d´ennemis que d´amis passe à l´ennemi. La guerre est considérée comme finie quand il n´y a plus de bataille possible.
Il s´agit de montrer que la guerre en question est finie à un moment ou un autre.
J´ai partionné l´ensemble des sommets de la façon suivante:
- Sa est l´ensemble des sommets dont tous les voisins sont de la faction A
- Sb est l´ensemble des sommets dont tous les voisins sont de la faction B
- S= est l´ensemble des sommets ayant exactement le même nombre de voisins de la faction A que de la faction B.
- SA>B est l´ensemble des sommets de G ayant plus de voisins de la faction A que de la faction B.
- SB>A est l´ensemble des sommets de G ayant plus de voisins de la faction B que de la faction A.
- S0 est l´ensemble des sommets isolés.
Il n´y a que S0 qui ne bouge pas. La guerre est donc finie quand les deux sous-ensembles SA>B et SB>A sont vides. Mais comment prouver qu´il arrive un moment où ils sont tous les deux vides?
-----
Envoyé par Garf 