Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Graphes de Coxeter



  1. #1
    fderwelt

    Graphes de Coxeter


    ------

    Bonjour,

    J'ai un ch'tit problème, technique, mais j'aimerais avoir une soluce explicite.

    Il s'agit de trouver tous les graphes qui obéissent aux règles suivantes:

    (0) le graphe est connexe (normalement ça va sans dire, mais ça va mieux en le disant).

    (1) chaque sommet est affecté d'un "poids" entier positif (entier naturel, quoi, si vous préférez).

    (2) les connexions entre sommets sont simples, doubles, ou triples, avec les règles:
    A--B : le poids de B est le même que celui de A;
    A==B : le poids de B est le double de celui de A (ou le contraire, celui de A double de celui de B);
    A==B: le poids de B est le triple de celui de A (ou le contraire, voir ci-dessus).
    Alors voilà: je cherche à énumérer tous (à isomorphisme près, évidemment) les graphes avec un nombre donné de sommets. Oh bien sûr, j'ai écrit un programme qui fait cette énumération récursivement, et qui ensuite élimine les isomorphes par une méthode que la morale réprouve, mais il ne marche (en temps raisonnable s'entend) que jusqu'à la dimension 6 (déjà 40 heures de calcul). Or il me faut cette énumération jusqu'à 32 sommets, théorie des cordes oblige. Aliors, PLEASE HELP!!!

    Si j'ai intitulé ce fil "Graphes de Coxeter", ce n'est pas par hasard. Les graphes qui m'intéressent sont ceux qui dérivent des graphes de Coxeter An, Bn, Cn, (dual de Bn) et Dn, et dans une moindre mesure, E6, E7, E8, F4 et G2. Et aussi, dans une encore moindre mesure, les hyperboliques compacts Tpqr.

    Je sais aussi que tous les graphes que je cherche se déduisent d'une des formes "canoniques" de Coxeter citées ci-avant, par des opérateurs de conjugaison que je n'écrirai pas ici parce que TeX me fait ch... Mais en gros, l'opérateur (je disais quoi sur TeX au fait?) permute les connexions (ik) et (jk), en bidouillant la connexion (ij) d'une manière très naturelle mais enquiquinante à expliquer. C'est d'ailleurs comme ça que j'ai écrit mon premier programme d'énumération.

    Toute idée géniale sera la bienvenue, et sera citée nommément dans ma biographie, quand j'aurai enfin été reconnu comme le plus grand mathélaticien de tous les temps (au passage, merci à azt, ça fait plaisir de voir qu'il y en a qui suivent...)

    -- françois

    -----
    Dernière modification par fderwelt ; 27/06/2006 à 14h17.
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  2. Publicité
  3. #2
    invite986312212
    Invité

    Re : Graphes de Coxeter

    il manque une contrainte: il faut borner les poids.

  4. #3
    homotopie

    Re : Graphes de Coxeter

    Un programme libre de téléchargement est dispo (je pense qu'il doit répondre à ta question, je te laisse vérifier) :
    http://math.univ-lyon1.fr/~ducloux/c...oxeter3_f.html

  5. #4
    fderwelt

    Re : Graphes de Coxeter

    Citation Envoyé par ambrosio
    il manque une contrainte: il faut borner les poids.
    Bonjopur et merci,

    J'aimerais bien... Il est "évident" intuitivement que les poids sont bornés (ne serait-ce que parce que les sommets sont en nombre fini, ce que je n'avais pas précisé), mais à part les bornes évidentes du style 2n ou 3n, rien de très évident ne s'impose.

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  6. #5
    fderwelt

    Re : Graphes de Coxeter

    Bonjour et merci à homotopie!

    Ce site ne m'aide pas vraiment pour le problème posé, mais me sera très très très utile pour de nombreux calculs que je m'apprêtais à me palucher sur les groupes de Coxeter. Si tout le monde publiait ses pages de calculs, ça éviterait bien des redites et des redécouvertes de la roue (qui, d'ailleurs, sont souvent bénéfiques, mais c'est un autre sujet).

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  7. A voir en vidéo sur Futura
  8. #6
    invite986312212
    Invité

    Re : Graphes de Coxeter

    Citation Envoyé par fderwelt
    Bonjopur et merci,

    J'aimerais bien... Il est "évident" intuitivement que les poids sont bornés (ne serait-ce que parce que les sommets sont en nombre fini, ce que je n'avais pas précisé), mais à part les bornes évidentes du style 2n ou 3n, rien de très évident ne s'impose.

    -- françois
    c'est moi qui dois l'être, mais je ne vois pas pourquoi tes poids seraient bornés. Même le graphe à 1 sommet, tu peux lui affecter n'importe quel poids entier positif (?) ou bien tu quotientes par la somme des poids?

  9. Publicité
  10. #7
    fderwelt

    Re : Graphes de Coxeter

    Bonjour,

    Citation Envoyé par ambrosio
    c'est moi qui dois l'être, mais je ne vois pas pourquoi tes poids seraient bornés. Même le graphe à 1 sommet, tu peux lui affecter n'importe quel poids entier positif (?) ou bien tu quotientes par la somme des poids?
    Tu as évidemment raison. Je suis trop plongé dans le truc, il y a tout un tas d'hypothèses que je prends en compte implicitement. C'est sûr que ce n'est pas terrible pour communiquer...

    En particulier, on peut supposer les poids premiers entre eux (dans leur ensemble). Mais il y a pas mal d'autres possibilités pour limiter la combinatoire. Avant de dire des bêtises, je mets ça au net, et on en reparlera quand le problème sera proprement spécifié.

    Parce que là, en l'état, c'est sûr qu'on peut faire n'importe quoi.

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

Discussions similaires

  1. Théorie des graphes
    Par -Zweig- dans le forum Lectures scientifiques
    Réponses: 4
    Dernier message: 21/12/2007, 11h05
  2. (dm) GRAPHES
    Par blueangel974 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 21/04/2007, 17h19
  3. logiciel+graphes
    Par scorpoc dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 29/01/2007, 19h18
  4. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59
  5. Graphes
    Par oli1978 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 19/12/2005, 13h24