Discussion:Hypercube (graphe)

BA ?

A mon avis c'est encore un peu tôt. Il faudrait développer les preuves (et il faudrait aussi que je me tapes le paragraphe sur la structure exacte du groupe d'automorphisme de l'hypercube, groupe qui est entièrement connu). Koko90 (d) 27 mars 2009 à 13:23 (CET)

J'ai finalement rédigé le paragraphe avec la structure exacte du groupe d'automorphisme de l'hypercube. Koko90 (d) 17 août 2009 à 11:41 (CEST)

L'article est vraiment solide. Il est appuyé sur d'autres articles comme le produit cartésien, le remarquable théorie des graphes ou encore le Lexique de la théorie des graphes. Personnellement j'aurai dit que la théorie des graphes est assez mure (malgré des paragraphes manquant) et celui là un peu moins. A l'introduction près, je vote déjà pour. Mais je partage en partie l'opinion de Koko90, il reste du potentiel d'amélioration pour l'AdQ. Jean-Luc W (d) 31 mars 2009 à 15:18 (CEST)

hypercube et urnes d'Ehrenfest

Il y a un lien étroit entre le Modèle des urnes d'Ehrenfest (voir aussi Chaîne de Markov#Probabilités de transition) et la marche aléatoire sur les arètes de l'hypercube, ce qui a conduit Mark Kac [1] à un très joli calcul exact [2] de valeurs propres de la matrice de transition de la chaîne de Markov sous jacente. Comme il s'agit d'une chaine image (on associe à chaque sommet la somme de ses coordonnées) le lien avec les valeurs propres de la matrice d'adjacence de l'hypercube est peut-être assez distendu. J'ai aussi vu passer sous mes yeux un calcul du trou spectral de la matrice d'adjacence, par Diaconis ou par Benny Sudakov, peut-être. Ce pourrait être un enrichissement de la page.--Chassaing 26 mars 2009 à 21:38 (CET)

Commentaires

Le travail est déjà remarquable, cependant à mon avis il reste encore du travail pour un label. Même si ma lecture fût à la fois rapide et partiel.

• Une introduction est indispensable, elle suit des règles précises (cf Résumé introductif).

Philippe Giabbanelli (d) 12 août 2009 à 01:51 (CEST)

• Les concepts ou symboles ne sont pas toujours introduit. Dans le paragraphe Construction, on voit l'usage du symbole K₂, mais il n'est pas simple de deviner à quoi il fait référence (Q₂ peut-être ?). Il est un peu dommage de ne pas avoir mis les étiquettes sur les différents exemples de graphes.

K₂ est le graphe complet à deux sommets (ok, ça fait juste une arête et deux sommets), il faudrait un lien vers une page sur les graphes complets. Koko90 (d) 27 mars 2009 à 13:22 (CET)

PS - J'ai fait le lien, donc pour cette remarque c'est réglé. Koko90 (d) 30 mars 2009 à 12:39 (CEST)

• Le style est parfois encore un peu léger. Dans le paragraphe Propriétés fondamentales on lit tout sommet a donc degré n. J'ai plutôt l'habitude de lire des phrases comme le degré de chaque sommet est égal à n. On lit encore on voit que pour passer de Q_n−1 à Q_n, il faut faire une copie du graphe, autrement dit on double le nombre de sommets. J'aurais préféré un style comme Les sommets du graphe Q_n sont ceux de deux copies du graphe Q_n−1, on en déduit qu'augmenter le degré de 1 revient à doubler le nombre de sommets.
• Il me semble que pour un bon article, un préambule indiquant la motivation qui pousse à établir les différents résultats de l'article est indispensable. Quelques mots sur l'histoire du concept, qui s'y ait intéressé et pourquoi est aussi le bienvenu. Tu n'as développé qu'une application, si je ne m'abuse, mais n'en existe-t-il pas d'autres ? Jean-Luc W (d) 27 mars 2009 à 10:52 (CET)

J'ai complété le préambule pour qu'on ait en tête l'utilisation pratique qui a motivé son développement et le cadre dans lequel il est aujourd'hui étudié. Il y a probablement d'autres applications, mais je pense qu'elles sont moins directes (génération de code, utilisation pour prouver d'autres théorèmes...) et je ne suis pas au courant de celles-ci. Ca rentrerait dans le cadre d'un AdQ je pense. Philippe Giabbanelli (d) 12 août 2009 à 01:51 (CEST)

Une nouvelle salve de commentaires

• J'ai peur que le début de l'introduction soit rebutante pour une classe de lecteurs peu habitués à du formalisme mais qui pourraient quand même tirer quelques bribes de l'article (par exemple des gens en début d'études scientifiques motivés par les applications au calcul parallèle). On aiderait peut-être la lecture en mettant la phrase sur l'interprétation géométrique devant celle qui parle d'étiquettes, en mettant à cet endroit une image contenant les seuls cas n=2 et n=3 (on voit mal comment mettre autre chose que n=4 dans l'infobox, mais le résultat est que ça met en haut de page un dessin qui peut paraître mystérieux - je n'ai pas de suggestion de remède à ce qui me semble un problème, sinon supprimer toutes les infobxes de Wikipédia :-)). Appeler "0" et "1" des "lettres" ("chiffres" est utilisé plus bas) n'est pas gênant pour qui sait des maths, mais peut troubler le profane non ?

• Là, c'est "ma faute". À "l'origine", il y avait "lettre", mais je trouvais ça perturbant de parler de "chiffre" juste après avoir introduit "l'alphabet" {0;1}. "Symbole" conviendrait mieux peut-être ? Léna (d) 16 août 2009 à 12:45 (CEST)

• Symbole est une bonne idée et logique dans le cas d'un alphabet. J'ai effectué les remplacements. Philippe Giabbanelli (d) 17 août 2009 à 08:21 (CEST)

• Un peu plus bas l'apparition de l'« espace vectoriel {Z2}n » ne m'a bien sûr pas gêné, mais peut rebuter le non-mathématicien. Des liens internes seraient utiles (mais je suppose qu'on n'a pas d'article sur "{Z2}n" alors que ça se justifierait tout à fait, ah le biais en faveur des objets qui ont des noms).

• Lien interne rajouté sur espace vectoriel. Philippe Giabbanelli (d) 17 août 2009 à 08:21 (CEST)

Mmmouais sur ce point, je ne suis pas sûr que ça suffise au Candide de passage (mais comment se mettre à sa place ?). Comprendra-t-il quel est le corps de base de cet espace vectoriel. D'une façon générale, une critique déjà faite par JLW plus haut est peut-être encore un peu d'actualité, meême si je n'ai été moi-même gêné nulle part : n'y a-t-il pas de ci de là des notations qui peuvent laisser perplexe quelqu'un qui n'est pas entraîné (le Z_2 ici) ? J'ai par exemple aussi remarqué dans "Cubes de Fibonacci" le $V_{0}=\lambda$ que je crois avoir compris (V_0 commence une partition des sommets, lambda est une chaîne vide), mais qui peut être opaque. Si vous avez du temps, regarder toutes les formules en essayant e se mettre dans la peau d'un candide (de préférence chacun regardant celles tapées par l'autre) pourrait être utile à la clarté de l'article, me semble-t-il. Touriste (d) 17 août 2009 à 20:57 (CEST)

J'avoue être en panne d'idées Pour l'espace vectoriel, il y a un lien interne si la structure intéresse vraiment quelqu'un, mais tout ce qui importe vraiment pour la construction est dans le c'est-à-dire où on donne la forme de l'étiquette. Pour les cubes de Fibonacci, j'ai remplacé lambda par epsilon parce que c'est plus commun pour le mot vide (j'aurai dû le faire au lieu de suivre la notation de l'article) et j'ai ajouté un lien interne vers grammaire formelle pour qu'on puisse lire ça au cas où. Philippe Giabbanelli (d) 18 août 2009 à 02:57 (CEST)

• Je n'ai carrément pas compris le raisonnement prouvant la parité de la longueur des cycles : n'est-il pas entaché d'un lapsus ? En tous cas il n'est pas bien clair, alors qu'il paraît évident au lecteur que je suis que ça découle immédiatement du changement de parité du nombre de 0 de l'étiquette à chaque pas, pourquoi invoquer une récurrence sur n ? De même il paraît curieux d'invoquer des résultats théoriques pour prouver la bipartition ou calculer le nombre chromatique, la bipartition par parité du nombre de zéros sautant aux yeux (ne pourrait-on quand même la signaler, si une source la signale comme il est plausible Note ajoutée le lendemain : c'est signalé dans Harary et al. vers la fin de la page 278) ? Touriste (d) 15 août 2009 à 20:57 (CEST)

  Rajout de la bipartition par parité de l'étiquette, comme suggéré par Harary. J'ai relu et je n'ai pas trouvé de lapsus, peut-être que je n'arrive pas à le trouver dans mon style ? Où est-ce que ça pose problème exactement ? Comme la parité de la construction des cycles est expliquée par construction (d'un hypercube de dimension n à dimension n+1), la preuve se veut par récurrence. La bipartition est une façon alternative de le voir, et maintenant elle est mentionnée dans le paragraphe (bonne suggestion). Philippe Giabbanelli (d) 17 août 2009 à 08:21 (CEST)

  Ah alors si ce n'est pas un lapsus, c'est un problème de clarté des termes utilisés je suppose (que sont "le graphe d'origine" et "sa copie" ?). Je le voyais comme une référence à la section "Constructions". Posons plus précisément le problème qui m'a gêné et de la façon dont j'ai pigé les mots utilisés. Soit xy0 les sommets du "graphe d'origine" dans Q_3 et xy1 les sommets de sa copie ($x,y\in \{0,1\}$). Soit le cycle 000 010 110 100 101 001 000. Il contient p=3 arêtes dans le "graphe d'origine" mais non pas "nécessairement p" dans la copie mais seulement p'=1. J'ai en toute bonne foi inteprêté ton texte comme légitimant cet exemple, et ça marche toujours quand je le tape ; donc il y a un problème de clarté. Touriste (d) 17 août 2009 à 20:57 (CEST)

  J'ai fait un dessin pour le cas que tu as dit et je l'ai rajouté dans l'article en scindant en deux la partie cycle et celle sur le nombre chromatique. Les preuves n'étant pas données, ça peut faire plus de peur que de bien de dire "continuez par récurrence et vous verrez bien" donc j'ai réécrit le mécanisme. Qu'en penses-tu ? Pour ton exemple, tu verras sur la figure qu'il y a p = 2 arêtes dans le graphe d'origine (celui où les sommets démarrent par 0) et p = 2 arêtes dans le graphe copie (celui où les sommets démarrent par 1). Philippe Giabbanelli (d) 18 août 2009 à 02:57 (CEST)

• Tiens encore une suggestion : je m'aperçois que la référence D2 (Harary, Hayes et Wu) est d'une nature assez différente des autres puisque c'est un « comprehensive survey of the theory of hypercube graphs. ». Pourquoi pas créer une section "Bibliographie" peut-être limitée à cet article (à moins que d'autres articles analogues, ou chapitres de traités, n'aient été écrits depuis 1988) ? Je pense que ce serait profitable pour les lecteurs que de les aiguiller sur cet article qui est un approfondissement de celui que nous leur fournissons, en le mettant davantage en relief et en signalant son caractère généraliste. Touriste (d) 16 août 2009 à 11:04 (CEST)

  C'est le seul article 'général' sur l'hypercube des références, les autres étant sur des domaines particuliers ou pas uniquement sur l'hypercube.

• Le wikilien petit monde ne va manifestement pas là où il devrait aller. Touriste (d) 16 août 2009 à 11:12 (CEST)

  Oui et non. Étude du petit monde est le bon article. Cet article a juste un mauvais contenu. Cette notion a été formalisée et étudiée par les physiciens, avec des modèles fournis par les gens de théorie des graphes. Le problème actuel de l'article est qu'il fait uniquement la première partie de vulgarisation et se concentre sur la sociologie. Il me déplaît fortement mais comme c'était mon sujet de thèse, je préfère éviter de le reprendre en main parce que j'en arriverai à dupliquer ce que j'ai déjà écrit ailleurs et sous copyright. Philippe Giabbanelli (d) 17 août 2009 à 08:21 (CEST)

  Ah ! Et ben on oublie ma remarque alors. Tout est dans tout, c'est trop bien la Science :-) Touriste (d) 17 août 2009 à 20:57 (CEST)

Produit en couronne

L'article dit ceci :
"Le produit en couronne de A et B étant défini comme le produit semi-direct $A\wr B=A^{B}\rtimes B$ où $A^{B}$ est l'ensemble des fonctions de A dans B et où A agit sur $A^{B}$ par décalage d'indice :

$(g.\lambda )(s)=\lambda (g^{-1}s)$ pour $g\in A$ et $\lambda \in A^{B}$."

À mon avis, il faut écrire :
"Le produit en couronne de A par B étant défini comme le produit semi-direct $A\wr B=A^{B}\rtimes B$ où $A^{B}$ est l'ensemble des fonctions de B dans A et où B agit sur $A^{B}$ par décalage d'indice :

$(g.\lambda )(s)=\lambda (g^{-1}s)$ pour $g,s\in \mathbf {B}$ et $\lambda \in A^{B}$."

Voici deux anomalies évidentes de la formulation actuelle :
1° A^B ne désigne pas l'ensemble des fonctions de A dans B, mais l'ensemble des fonctions de B dans A;
2° un produit semi-direct $\ A^{B}\rtimes B$ correspond à une action de B et non à une action de A.

Je préfère ne pas intervenir directement dans l'article, parce que je ne connais pas le sujet de l'article (hypercube) Marvoir (discuter) 18 mai 2014 à 16:33 (CEST)

bien vu. Koko90 (discuter) 24 juin 2014 à 18:55 (CEST)