Démontrer qu'un graphe n'est pas magique...

[trocho]

Bonjour à tous!

Je sais que les questions sur les graphes sont un peu plus rares que le reste, sur ce forum, mais je tente quand même ma chance.

Voilà, j'ai un exercice fort prenant dans lequel on me dit qu'un graphe magique est un graphe admettant un étiquetage standard tel que le poids de chaque sommet soit constant.

En fait, j'arrive à répondre aux questions dans lesquelles on doit montrer qu'un graphe EST magique, mais je n'arrive pas à montrer que le d-cube n'est pas magique pour d>2 impair, de même que pour le graphe complet d'ordre n pour n multiple de 4.

Si quelqu'un peut m'aider...

J'espère avoir été assez clair.

Merci

[trocho]

Personne?

Si quelqu'un veut que je précise la question, pas de problème, hein...

[ffpower]

Je veux bien que tu precise la question^^.
C est quoi un ettiquetage pour commencer?

[trocho]

Si un graphe G=(V,E) est un graphe simple avec card(V)=n=nombre de sommets et card(E)=m=nombre d'arêtes, un étiquetage standard f de G est une application bijective de E sur [1,m].

En gros, à chaque arête on associe un nombre entre 1 et m, et chaque nombre est différent.

Le poids p(v) d'un sommet v est la somme des étiquettes des arêtes d'extrémité v.

:mur:

[Nathalie.Roche]

J'espère avoir compris le pb. Merci de me signaler d'éventuelles erreurs d'interprétation ou définitions.

Le d-cube a 2^d sommets et 1/2*d*2^d=d*2^(d-1) arêtes.

La somme des poids des arêtes est 1+2+...+(d*2^(d-1))=d * 2^{d-2} * (d*2^{d-1}+1)

Notons w(e) le poids de l'arête e et p(s) la somme des w(e) pour e arête incidente au sommet s.

On a Somme des p(s)=2* Somme des w(e) puisqu'en sommant sur les sommets chaque arête est comptée deux fois.

Si p(s)=P ne dépend pas de s, on doit avoir :
Nb de sommets * P= Somme des p(s)
soit
2^d * P = 2 * d * 2^{d-2} * (d*2^{d-1}+1)

d'où

P= (d/2) * (d*2^{d-1}+1)

mais d étant impair et le second facteur aussi, on aurait P non entier alors que P est une somme d'entiers.

[trocho]

Merci beaucoup!!

Je pense que c'est le raisonnement demandé. (surtout qu'à la question d'avant, ils avaient demandé de calculer un fonction du nombre d'arêtes et de sommets le poids commun des sommets...) *_* J'aurais quand même dû réfléchir un peu plus...

Grâce à ça, je pense savoir comment faire pour les graphes complets.

Merci encore!