Discussion:Produit zig-zag de graphes

Un exemple

Si quelqu'un trouve un exemple, ce serait bien ! -- ManiacParisien (d) 20 juin 2013 à 15:06 (CEST)

J'ai pas encore pris le temps de me plonger dans le truc (il faut dire que ça fait un peu peur), mais le premier résultat google pour "produit zig zag comment sortir d'un labyrinthe" est un pdf de l'ens, avec un exemple en page 21... Si ça peut aider...--Roll-Morton (d) 22 juin 2013 à 20:02 (CEST)

Bon exemple, en effet. J'ose pas copier-coller, et j'ai la flemme de le ré-latexer. C'est un rapport de fin de cours ? -- ManiacParisien (d) 22 juin 2013 à 22:05 (CEST)

Je sais pas j'ai juste cherché un document en français parlant de ce machin là.--Roll-Morton (d) 23 juin 2013 à 01:43 (CEST)

Peut-être avec un dessin... (plus simple que celui page 21 du PDF que tu mentionnes). Si j'ai le temps je le fais sous inkscape. Bravo en tout cas pour l'article ! --MathsPoetry (d) 25 juin 2013 à 21:47 (CEST)

Merci d'avance -- ManiacParisien (d) 26 juin 2013 à 20:52 (CEST)

Attends, j'ai encore rien promis ! --MathsPoetry (d) 26 juin 2013 à 21:21 (CEST)

En parlant de dessins, celui de http://www.math.mcgill.ca/goren/667.2010/Neil.pdf me semble faux : un des traits bleus du schéma de la page 2, celui de droite, me semble faire zig, mais pas zag . Vous confirmez ?

J'ai regardé pas mal de schémas sur Google, ils sont tous trop compliqués et illisibles. Je continue à chercher un exemple qui ne serait pas trivial mais lisible.

Déjà, je ne vais pas prendre un graphe cubique pour G, car alors H peut difficilement être autre chose que de degré 2, ce qui donne trop d'arêtes. Je crois que je vais prendre G de degré 4 et H de degré 1. G sera probablement le graphe octaédrique, car il n'a que 6 sommets. --MathsPoetry (d) 3 juillet 2013 à 12:37 (CEST)

C'est bien ! Et tous les autres ajouts excellents ! -- ManiacParisien (d) 3 juillet 2013 à 18:42 (CEST)

Fait. J'ai aussi fait le degré 4 fois le degré 2, pour avoir un exemple moint "trivial".

Content que ça te plaise . Bon, c'est très "chevelu" comme résultat, mais c'est un peu la nature du produit zig-zag qui le veut (c'est d'ailleurs le signe que c'est fortement expanseur…). --MathsPoetry (d) 3 juillet 2013 à 18:51 (CEST)

Bravo pour les autres exemples. J'ai testé le remplacement de gallery par Gallery dans le premier exemple : la marge est plus fine, donc les images plus grandes; je ne suis pas entièrement convaincu.

En revanche, la dernière figure est excellente (principe dans le cas généra) ! Personnellement, j'aime bien les légendes longues; je rappellerais les formules dans la légende, ou est-ce trop long ?-- ManiacParisien (d) 5 juillet 2013 à 16:29 (CEST)

Je ne savais pas, pour gallery et Gallery.

Je ne suis pas à 100 % convaincu pour mes illustrations d'exemples de produit zig-zag. Je trouve le graphe résultant illisible, malgré l'appel à l'aide de couleurs. J'en suis un peu arrivé à la conclusion que c'est inhérent à l'opération. À moins qu'on n'arrive à mieux en disposant mieux les arêtes et les sommets ?

J'aime bien les légendes courtes , mais ici une légende plus longue peut tout à fait se justifier. Vas-y. --MathsPoetry (d)

Peut-on supprimer le cadre intérieur, inutile, dans les galeries ? --MathsPoetry (d) 6 juillet 2013 à 11:34 (CEST)

Peut-être, mais je ne sais pas faire. -- ManiacParisien (d) 6 juillet 2013 à 19:01 (CEST)

Et maintenant, je sais .-- ManiacParisien (d) 15 juillet 2013 à 06:40 (CEST)

Nombre de couleurs nécessaires pour colorer les arêtes d'un graphe régulier ?

« Les graphes D-réguliers (réguliers de degré D) sont supposés posséder une coloration des arêtes avec D couleurs telle que deux arêtes adjacentes sont colorées différemment. »

Ce n'est pas vrai en général. Considérez par exemple le graphe 2-régulier à 3 sommets (ou n'importe quel autre graphe cycle à nombre de sommets impair, en fait). Vous ne pourrez pas colorer les arêtes avec 2 couleurs de façon à ce que des arêtes adjacentes aient toujours de couleurs différentes. Il vous en faut 3.

J'ai supposé que "sont supposés" voulait dire que l'on choisissait un graphe où D couleurs suffisent, parce que ça nous arrange bien. --MathsPoetry (d) 3 juillet 2013 à 12:57 (CEST)

Merci d'avoir arrangé cette formulation douteuse. C'est bien comme ça ! (Et l'exemple excellent aussi !) -- ManiacParisien (d) 3 juillet 2013 à 18:43 (CEST)

OK, j'étais pas sûr de ce que "sont supposés" voulait dire. Content de ne pas m'être planté... --MathsPoetry (d) 3 juillet 2013 à 18:52 (CEST)

Réécriture de la définition simplifiée

Je me suis permis de réécrire la définition simplifiée en supprimant tout formalisme. J'espère que tu ne m'en veux pas.

J'espère aussi que je n'ai pas introduit d'erreur par rapport à la définition originale des auteurs. Je veux bien une relecture critique. En particulier cela m'intéresse de savoir si le mot arbitraire (concernant la coloration des sommets de H) est correct. --MathsPoetry (d) 4 juillet 2013 à 12:19 (CEST)

Bien ! Le moins de notations, le mieux. Le mot arbitraire me convient, je ne vois pas de piège.-- ManiacParisien (d) 5 juillet 2013 à 16:24 (CEST)

Le piège serait le Travail Inédit (TI). Je n'ai en effet pas lu (contrairement à toi, je crois), l'article de recherche original. Pour moi, le produit de G et H n'est défini de façon univoque que pour une D-coloration des arêtes de G donnée et une D-coloration des sommets de H donnée. Dit autrement, étant donnés deux graphes G et H avec $deg(G)=|H|$, on a encore le choix (arbitraire) de la coloration des arêtes de G et des sommets de H. En particulier, si on colore tout ça autrement, on obtient un autre produit. J'ai raison ou tort ? --MathsPoetry (d) 5 juillet 2013 à 19:18 (CEST)

Oui, j'ai regardé l'article original qui est bien plus clair que les pages de la wikipédia anglaise. Je crois que tu as parfaitement raison, et qu'il n'y pas de piège. -- ManiacParisien (d) 6 juillet 2013 à 06:27 (CEST)

Les anglophones sont plus concis que nous, ils privilégient l'énumération des résultats à leur explication. C'est un choix valide, mais je préfère vulgariser. Par exemple, ils sautent complètement la définition simplifiée, qui n'est effectivement pas nécessaire, puisque l'on dispose d'une définition générale... --MathsPoetry (d) 6 juillet 2013 à 11:19 (CEST)

Connectivité ou connexité ?

Quelle est la bonne terminologie ? Il s'agit de l'existence d'un chemin ou d'une chaîne reliant deux sommets donnés. Je penche pour la version « connexité » plutôt que « connectivité » qui sent l'anglicisme. Cela a des répercussions sur d'autres pages, comme L (complexité), où j'ai mis « connectivité », mais là aussi, « connexité » serait peut-être mieux ? -- ManiacParisien (d) 6 juillet 2013 à 06:27 (CEST)

Je dirais en effet "connexité" comme dans l'article Algorithmes de connexité basés sur des pointeurs.

Côté vocabulaire, c'est "coloration de graphe" et "coloriage de carte", on "colore un graphe" et on "colorie une carte" (traître, parfois, le français).

Enfin, c'est "espace" et pas "place" pour "space". On parle ici de l'espace mémoire nécessaire à l'algorithme, je crois. Je corrige. --MathsPoetry (d) 6 juillet 2013 à 11:17 (CEST)

D'accord. -- ManiacParisien (d) 6 juillet 2013 à 19:01 (CEST)

Autre phrase qui me fait tiquer

« Si une coloration existe, alors RotG(v,i)=(w,j) implique i=j. »

Euh, ça me semble être un gros raccourci. Coloration ou pas, la numérotation des arêtes issues de chaque sommet est a priori arbitraire. Alors effectivement, si D couleurs suffisent, on peut s'arranger pour que i et j soient égaux, mais ce n'est pas pareil que de dire que ça implique que i = j. Je corrige en ce sens. Merci de signaler un éventuel désaccord. --MathsPoetry (d) 4 juillet 2013 à 12:54 (CEST)

Là, j'étais pris au piège de l'article, je crois. J'ai encore changé ta phrase, (et c'est là que je me suis aperçu que la notation v(i) avait disparue); est-ce que c'est plus clair ? Sinon, on revient en arrière. -- ManiacParisien (d) 5 juillet 2013 à 16:14 (CEST)

C'est plus clair mais pas forcément nécessaire : "on peut s'arranger" me semble suffire, pas besoin d'expliquer comment. J'ai réverté au nom de la concision, si tu penses que c'était mieux en détaillant on peut en discuter. --MathsPoetry (d) 5 juillet 2013 à 19:23 (CEST)

Valeurs propres

J'ai remis "en valeur absolue" pour le majorant de la valeur propre, en effet celle-ci peut être négative. Merci de valider. --MathsPoetry (d) 6 juillet 2013 à 11:32 (CEST)

Tout à fait. C'est comme ça aussi dans la page anglaise. -- ManiacParisien (d) 6 juillet 2013 à 19:01 (CEST)

Une source possible

Je suis tombe sur ce billet de blog, par un spécialiste. Si ça peut aider... --Roll-Morton (discuter) 20 avril 2016 à 11:33 (CEST)