Exercice sur les graphes

[invite99628bf9]

Bonjour,

Je suis tombé sur cet exercice sur les graphes simples aux allures très sympathiques ! 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 !
-----

[invite986312212]

une suite décroissante d'entiers positifs est nécessairement finie, alors, peut-être trouver une fonction qui à une configuration associe un entier positif et qui décroîtrait à chaque changement de camp? mais je vois pas tout de suite.
(bon, ça aide pas vraiment)

[invite986312212]

ah ben, tout simplement compter +1 pour chaque arête reliant deux sommets ennemis. Quand un sommet change de camp, on perd plus d'arêtes "mixtes" qu'on n'en gagne.

[invite35452583]

ah ben, tout simplement compter +1 pour chaque arête reliant deux sommets ennemis. Quand un sommet change de camp, on perd plus d'arêtes "mixtes" qu'on n'en gagne.

Non nécessairement car les autres sommets peuvent aussi changer de camp. exemple: les sommets d'un carré dont deux côtés adjacents sont toujours ennemis, la bataille est périodique d'ordre 2 et éternelle. Mais ce n'est pas un graphe simple, hypothèse non utilisée.

Je vois plutôt ceci :
soit un sommet qui change une infinité de fois de camp, montrer qu'alors il y a deux côtés adjacents qui eux aussi changent une infinité de fois (ou s'il n'y en a aucun ou qu'un seul alors le sommet à un moment choisit définitivement son camp).
En déduire que si la bataille est éternelle il existe un cycle entre ces sommets.

[A voir en vidéo sur Futura]

[invite986312212]

j'avais compris que deux sommets ne pouvaient pas changer de camp simultanément (autrement il suffit de considérer le graphe à deux sommets ennemis, ils changent éternellement de camp). Du coup l'ordre dans lequel on examine les sommets importe. Mais dans tous les cas la bataille s'achève.

[invite35452583]

autrement il suffit de considérer le graphe à deux sommets ennemis

"Une bataille se déroule de la façon suivante : un sommet, relié à (strictement) plus d’ennemis que d’amis, passe à l’ennemi."
La guerre de deux n'aura pas lieue.

[Médiat]

La guerre de deux n'aura pas lieu.

[invite35452583]

Je vois plutôt ceci :
soit un sommet qui change une infinité de fois de camp, montrer qu'alors il y a deux côtés adjacents qui eux aussi changent une infinité de fois (ou s'il n'y en a aucun ou qu'un seul alors le sommet à un moment choisit définitivement son camp).
En déduire que si la bataille est éternelle il existe un cycle entre ces sommets.

Ceci dit il faut éliminer les "fausses pistes" : une suite de sommets se terminant en un sommet lié à un nombre égal de sommets fixes d'un camp et d'un autre (à partir d'un moment). Mais c'est faisable. Donc cet ajout de l'hypothèse "simple" me laisse peu douter qu'à chaque tour ou bataille on applique simultanément la règle aux sommets.

PS : merci Médiat

[invite2c3ff3cc]

Pluto tu as redonné le même énoncé (que sur un autre forum) mais sans préciser ce sur quoi on était tombé d'accord : il faut ajouter le fait que les batailles se font les unes après les autres et pas "instantanément + simultanément". Pourquoi ?

[invite99628bf9]

Bonsoir,

Désolé ThSQ j'ai fais un double post car je voulais avoir des avis différent !
Et donc comme tu le dis si bien je pense que les batailles doivent avoir lieux les unes après les autres, sans ça, comme dans le cas du carré, il y aura une infinité de batailles ce qui ne concorde pas avec la conclusion que l'on veux faire...

Tu peux expliquer d'avantages ou tu raisonnement allait ThSQ stp ?

[Médiat]

les sommets d'un carré dont deux côtés adjacents sont toujours ennemis, la bataille est périodique d'ordre 2 et éternelle. Mais ce n'est pas un graphe simple, hypothèse non utilisée.

Je craque (je me pose la question depuis plusieurs heures, les graphes n'étant pas ma spécialité) : pourquoi ce n'est pas un graphe simple ?

[invite99628bf9]

Salut Médiat,

Moi aussi j'ai passé un petit moment sur cet exo en vain !!
Je pense aussi que c'est un graphe simple

1 - 2
|   |
2 - 1

[invite99628bf9]

J'ai pensé à une façon de résoudre avec laquelle je n'arrive pas à aboutir mais cela donnera peut être des idées à certains.

L'idée est de montrer que si une bataille a lieux en un sommet alors elle pourra impliquer au maximum un nombre fini de nouvelles batailles...(La je ne m'en sort pas dans mes calculs. il faut partir d'un nombre n de sommets, donc un sommet est relié a au plus n-1 autres sommets, donc si ce sommet tombe cela implique qu'il est relié au plus a [(n-2)/2]...etc. mais je n'aboutis pas)

Le graphe ayant un nombre de sommets fini alors le nombre de bataille est majorée et donc la guerre de durera pas indéfiniment...

[invite35452583]

Salut Médiat,

Moi aussi j'ai passé un petit moment sur cet exo en vain !!
Je pense aussi que c'est un graphe simple

1 - 2
|   |
2 - 1

Dans la définition de graphe simple que j'avais en tête et après recherche un graphe simple n'a pas de boucle.

D'autre part je pense qu'avec Ambrosio mais peut-être aussi avec d'autres, pour moi tout sommet est relié à lui-même (d'ailleurs c'est conforme à l'idée de bataille et de guerre si tout le monde est passif et ne participe pas à l'action de son propre camp pourquoi et comment peut-il y avoir une guerre). L'exemple avec deux sommets ennemis donne donc une guerre infinie pour Ambrosio si on prend en simultanée, il n'y a aucun changement de camp pour ma règle.
Ensuite il y a simultanéité ou pas.

Si la règle est bataille en un sommet à la fois, qu'importe l'ordre de bataille et la règle du changement de camp, l'idée d'Ambrosio montre de manière simple et élégante que la guerre se finit.
Si la règle est celle que j'avais en tête alors l'exemple du carré montre qu'il faut des conditions sur le graphe, par exemple simple. D'autre part l'exemple avec deux sommets montre que seule la règle où un sommet défend sa propre couleur peut imposer à une guerre de finir.
A ces deux conditions alors une guerre se finit toujours.
Un sommet qui change une infinité de fois ne peut être lié à un seul ou aucun sommet du même type. En effet, cela implique qu'il ne peut plus changer. A partir du moment où les sommets qui ne changent qu'un nombre fini de fois de camp ne changent en effet plus (ça arrive car ces sommets sont en nombre fini), alors le sommet ne plus changer qu'une fois (s'il n'y a pas d'autre sommet variable relié, c'est évident). En effet soit m le nombre de sommets fixes de l'ancien camp, n le nombre fixe du 2nd camp. Pour passer de l'un à l'autre comme le sommet qui change est de l'ancien camp on a m+1<n+1 (cas où le sommet variable est dans l'ancien camp) ou m+2<n (cas où le sommet variable est dans le nouveau camp). Pour rechanger on doit avoir m+1>n+1 ou m>n+2. On a dans un cas m<n dans l'autre m>n c'est impossible.
Tous ces sommets contiennent au moins deux arêtes on peut donc trouver une boucle. Même avec des changements simultanés la guerre se finit dans un graphe simple avec la règle un sommet est considéré relié à lui-même.

[Médiat]

Dans la définition de graphe simple que j'avais en tête et après recherche un graphe simple n'a pas de boucle

D'accord (il s'agit bien de boucle et non de cycle)

pour moi tout sommet est relié à lui-même

C'est la définition d'une boucle d'où mon :

[invite35452583]

C'est la définition d'une boucle d'où mon :

Pour la règle de la bataille et uniquement celle là, je suis d'accord qu'il y a confusion de notation. Mais, en résumant mon post précédent :
soit on adopte la règle "le sommet lui-même n'est pas compté" et on a
a) en simultané il y a des contre-exemples triviaux même avec des graphes simples
ou
b) une bataille en un sommet à la fois et alors c'est vrai pour tous les graphes même non simples
ce que je ne trouve pas très conforme soi avec les hypothèses soit avec la conclusion

soit on adopte la régle "le sommet lui-même est compté" et
a) une bataille en un sommet à la fois, c'est vrai sans hypothèse de simplicité du graphe
ce que je ne trouve toujours pas conforme aux hypothèses
ou
b) en simultané et c'est alors vrai pour les graphes simples mais non nécessairement pour les autres (contre-exemple du carré).
Seule cette dernière possibilité est conforme à mes yeux aux hypothèses et à la conclusion.

Maintenant quelque soit le vrai énoncé il y a de grandes chances que le cas sait été traité.

[invite986312212]

"Une bataille se déroule de la façon suivante : un sommet, relié à (strictement) plus d’ennemis que d’amis, passe à l’ennemi."
La guerre de deux n'aura pas lieue.

pourquoi? est-ce qu'on n'a pas 1>0 ?

[invite35452583]

pourquoi? est-ce qu'on n'a pas 1>0 ?

Je l'ai expliqué après on ne compte pas de la même façon qui est dans un camp. Sur cet exemple En un sommet je compte non seulement l'autre mais aussi le sommet en lequel la bataille a lieu (selon le principe que s'il est dans un camp il participe à la bataille dans son camp).
J'ai ensuite fait un topo sur différentes possibilités d'interpréter le résultat (règle de comptage ; simultanéité ou non).

[invite986312212]

salut,

si tu comptes un sommet parmi ses voisins, ça revient à considérer un graphe non simple et donc tu t'écartes de l'énoncé (à mon humble avis).

[christophe_de_Berlin]

Non, franchement, un sommet n´est pas relié à lui-même, ça contredit la définition de l´adjacence/voisinage.

D´ailleurs, même en admettant que la définition est ambigue, on n´a qu´a regarder la tapée d´exercices classique, où on montre que dans un graphe simple complet d´ordre n, un sommet possède (n-1) voisins. Si un sommet était relié à lui-même, il aurait alors n voisins.