Graphe magique et cycle hamiltonien

[lilulana]

bonjour,

mon problème est le suivant:
je dois montrer que si un graphe G=(V,E) où E est la réunion disjointe de deux cycles hamiltoniens alors G est magique. L'exercice conseille d'étiqueter les arêtes d'un cycle avec les nombres 1,4k-1,3,4k-3,...et les autres avec 4k,2, 4k-2,4,...

je ne comprends pas cette étiquetage.je ne parviens même pas à l'essayer sur un exemple parce que je ne vois pas ce qu'ils veulent dire. je suis perdue pour l'instant.

merci d'avance

[trocho]

Bonjour.

Ne faut-il pas aussi que le graphe G soit biparti?

[lilulana]

oh si bien sûr désolée, j'ai oublié de l'écrire

[lilulana]

est-ce que le problème vous parle?

[trocho]

oui, je l'ai eu l'an dernier en contrôle, en enseignement à distance. ^^

Pour éviter de donner la réponse brute (aucun intérêt, n'est-ce pas? En plus, c'est contraire à la charte du forum), je vais essayer de te conduire vers la réponse. Il y a une date limite, pour cet exo?

Partons donc du fait que G est biparti. Que peut-on en déduire concernant la longueur d'un cycle, d'un cycle hamiltonien, et enfin concernant le graphe (n'a-t-il pas une caractéristique particulière?)

[lilulana]

oui la date limite est vendredi.on nous a donnés le devoir lundi.merci beaucoup de m'aider.

alors en fait, je ne comprends pas la numérotation proposée.c'est peut-être bête mais comment ça je numérote 1,4k-3, 3,...?pourquoi 4k?en plus, si je prends k=1, les arêtes 1,3,3,1,...
cela me pose vraiment problème.
à partir de là, je ne sais pas non plus comment exploiter le fait que le graphe est biparti.
j'espère arriver à la question "intéressante" qui suit sur les carrés magiques que je ne comprends pas non plus. par ailleurs la question précédente concerne le d-cube et Kn avec n multiple de 4.j'ai dit qu'ils ne pouvaient pas être magiques en raisonnat autour du poids qui n'allaient pas être entiers et que c'était impossible.Cela te paraît-il correct?

[lilulana]

alors je vauis faire des propositions pour avancer:


est-ce que je vais utiliser le fait qu'un graphe biparti n'a pas de cycle de longueur impaire?

[lilulana]

un graphe biparti qui est hamiltonien est d'ordre pair sinon il n'est pas hamiltonien, même plus, si G est biparti et a un cycle hamiltonien, alors les ensembles de bipartition ont même cardinal.est-ce que ça aide?

[trocho]

oui la date limite est vendredi.on nous a donnés le devoir lundi.merci beaucoup de m'aider.

alors en fait, je ne comprends pas la numérotation proposée.c'est peut-être bête mais comment ça je numérote 1,4k-3, 3,...?pourquoi 4k?en plus, si je prends k=1, les arêtes 1,3,3,1,...
cela me pose vraiment problème.
à partir de là, je ne sais pas non plus comment exploiter le fait que le graphe est biparti.
j'espère arriver à la question "intéressante" qui suit sur les carrés magiques que je ne comprends pas non plus. par ailleurs la question précédente concerne le d-cube et Kn avec n multiple de 4.j'ai dit qu'ils ne pouvaient pas être magiques en raisonnat autour du poids qui n'allaient pas être entiers et que c'était impossible.Cela te paraît-il correct?

C'est ça, j'avais fait un truc dans le genre. Ils ne changent pas leurs devoirs, apparemment...

Pour le 4k, il faut en fait que tu voies que le graphe sera forcément 4-régulier.

Par chaque point il passe deux cycles hamiltoniens disjoints, et comme tu l'as dit, ces cycles sont forcément de longueur paire.

C'est bon pour le 4k, maintenant?

Maintenant, il faut essayer de trouver une bijection convenable entre [|1,4k|]
et les arêtes telle que le poids des sommets soit constants. Pour la suite, si tu as le même énoncé que j'avais, le d) et le e) vont ensemble. Pour le e), il faut essayer à partir des carrés de trouver un étiquetage pour le graphe.

[lilulana]

alors je récapitule,juste pour voir si j'ai compris: le graphe est nécessairement 4k-régulier parce par chaque point passe deux cycles hamiltoniens disjoints?

ensuite où est-ce que j'exploite la numérotation des arêtes, il n'y a pas forcément besoin?

s'il est 4k-régulier, je dois trouver la bijection...je cherche

[trocho]

Il est nécessairement 4-régulier. Donc le nombre d'arêtes est du type 4k. Théoriquement, la répartition des étiquettes est "facile" avec l'indication de l'énoncé.

Pour mieux voir, essaie cette méthode sur la figure du d), le graphe K_4,4, qui répond aux conditions de c).

Je me reconnecterai demain. Bonne nuit.

[lilulana]

alors petite question: pourquoi la bijection est-elle de 1 à 4k?le graphe est 4k-régulier mais on ne sait pas quel est l'ordre du graphe?on sait juste que c'est de la forme 2p.je dois oublier quelque chose

[lilulana]

d'accord à demain,merci beaucoup

[lilulana]

ah oui oui, 4k régulier donc nombre d'arêtes est (n*4k)/2 donc de la forme 4k'?je me reconnecte demain matin

[lilulana]

oublie mes questions précédentes, je me suis rendue compte de l'erreur que je commettais;je cherche donc la fameuse bijection

[lilulana]

j'ai réussi à trouver la bijection dans le cas particulier du d) en étiquetant les arêtes comme ils le conseillent, en suivant le parcours du cycle hamiltonien mais je cherche maintenant à montrer que cet étiquetage convient toujours:

je dis que dans le cas que nous traitons, le poids commun est 2(4k+1).j'essaie donc de retrouver ce résultat.
on peut faire partir les deux cycles hamiltoniens du même sommet.Il part donc de ce sommet de départ l'arête (4k) pour le premier cycle, 1 pour le deuxième;il y arrive l'arête (4k-2k)=2k pour le premier et 2k+1 pour le deuxième.en sommant je retrouve 8k+2.
cela te parît-il correct?
est-ce que le raisonnement pour ce sommet suffit?parce que je ne vois pas trop comment faire pareil pour un sommet quelquonque

autre question:comment voir un graphe magique pour la question e)?

[trocho]

C'est ça, mais il faut aussi justifier pour les autres points.

Tu fais partir tes deux cycles du même point, puis tu les étiquettes. Tu calcule pour chaque point le poids d'un sommet pour l'étiquetage relatif au 1er cycle, puis pour celui relatif au second cycle. Tu verras alors qu'en additionnant ces poids, tout tombera juste. Après dans le corrigé, ils rajoutent une partie dont je ne comprends pas l'intérêt (ils disent de vérifier que les sommets en position paire (resp. impaire) sur chaque cycle sont les mêmes).

Pour la question e), tu devrais essayer de voir les chiffes du carré comme un étiquetage d'un graphe.

[lilulana]

puisqu'il y a 2k sommets, je le fais pour le 1,2,et 2k-ième?

pour le e) si j'ai compris ce que tu m'expliquais, le carré 3X3 est à associer au graphe K 3,3?donc pour l'exemple à donner je peux reprendre l'étiquetage en d)?

ils demandent de montrer que tout graphe biparti K k,k est magique, est-ce qu'il suffit de dire qu'il admet les propriétés du c)?

merci encore de toutes tes explications

[lilulana]

alors j'ai un problème(encore!)

si je prends nimporte quel sommet, je ne peux pas savoir quelle position il a dans le premier cycle et dans le deuxième: si je prends par exemple le quatrième sommet du cycle(numéroté avec les nombres pairs), l'arête entrante est 4 et celle sortante 4k-4 mais comment savoir quelle position il a dans le deuxième cycle et donc quelles arêtes entrent et sortent?

[trocho]

Soit s un sommet quelconque dont on fait "partir" les deux cycles, que l'on pourra noter C1 et C2. Alors, en étiquetant le cycle C1 à partir de s avec 1,4k-1,3,4k-3,... (d'ailleurs, jusqu'où va-t-on aller d'après toi? Il faut bien que cet étiquetage s'arrête), calcule le poids de chaque sommet du graphe. (par exemple le sommet entre l'arête étiquetée 1 et celle étiquetée 4k-1 est 4k.) de même avec C2, en partant de s, avec 4k,2,4k-2,4...

Tu devrais obtenir un résultat constant un sommet sur deux (c'est d'ailleurs là que le fait que les sommets pairs soient les mêmes pour les deux cycles prend son sens) pour tous les sommets différents de s. Le cas particulier de s se règle à part. En additionnant les deux poids relatifs aux cycles C1 et C2, tu devrais trouver un poids constant.

Pour démontrer le e), il suffit d'utiliser convenablement le fait qu'il existe un carré magique pour k plus grand que 3 et le lien qu'on peut trouver entre un carré magique et K_k,k. et en effet, pour trouver l'exemple, en utilisant le d), tu trouves très vite un carré magique d'ordre 4.