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

? Graphe Contractible ?



  1. #1
    samy64

    Arrow ? Graphe Contractible ?


    ------

    Bonjour,

    Je suis élève ingénieur et je commence un projet de recherche opérationnelle.

    Cependant il me faut la définition d'un Graphe Contractible. Cette dernière étant très difficile à trouver sur le net.

    Quelqu'un peut-il m'aider?

    Merci!

    -----

  2. Publicité
  3. #2
    specieuse

    Re : ? Graphe Contractible ?

    En français, on écrit plutôt "graphe contractile", et en anglais, `contractible graph' (cela peut aider les recherches sur la toile, même si google est assez gentil avec l'orthographe). La notion de graphe contractile vient du fait que l'on peut associer à tout graphe G un espace topologique X (en général, un sous-truc d'un espace euclidien). Si l'espace topologique X est contractile, on peut alors dire que G l'est. Il est aussi possible de définir cette notion de manière purement combinatoire. Je ne connais pas de référence particulièrement sympathique, mais voici au moins où trouver de telles définitions.

    http://www.math.ust.hk/~mabfchen/Pap...m-Homotopy.pdf
    http://front.math.ucdavis.edu/math.CO/0605275

  4. #3
    martini_bird

    Re : ? Graphe Contractible ?

    Salut,

    pour une définition voir par exemple ici ou dans tout ouvrage de topologie algébrique.

    @ specieuse : un graphe est un espace topologique, non ?

    Cordialement.

  5. #4
    specieuse

    Re : ? Graphe Contractible ?

    Salut aussi.
    Il faut bien entendu s'entendre sur la notion de graphe (je connais au moins trois ou quatre définitions non équivalentes: il y a les graphes orientés ou pas, planaires ou pas, réflexifs ou pas, sans compter les n-graphes et autres entités terribles...), mais pour ce que j'en comprends, il s'agit dans tous les cas d'un objet purement combinatoire: je vois ce genre de bêtes comme des ensembles munis de structures, tout comme les groupes, les catégories, etc (et ici, je peux être très précis: il s'agit d'une structure algébrique au sens de Lawvere (ce qui signifie grosso modo qu'elle est définie par un nombre fini d'axiomes "gentils"), et ce n'est pas le cas de la notion d'espace topologique). Il se trouve que la réalisation topologique d'un graphe reflète une bonne part des propriétés de celui-ci, mais il ne s'agit que d'une représentation du graphe que l'on s'est donné (c'est un peu comme en faire un dessin non?). On peut en trouver d'autres tout aussi intéressantes qui dépendent du graphe lui même et non pas seulement de l'espace topologique associé (on voit ce genre de choses dans la théorie des représentations de carquois par exemple, ce qui donne naissances à des "algèbres amassées" (on dit "cluster algebras" en anglais)).
    Voilà pour ce soir. Si ce que je dis est trop abscond, je reviendrai m'expliquer à une heure moins indue.
    A très bientôt.

  6. #5
    martini_bird

    Re : ? Graphe Contractible ?

    Salut,

    merci pour les précisions : je voix bien ce que tu veux dire et tu as donné des mots-clefs qui me permettront de regarder les détails.

    Merci et bonne journée !

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

    Merci

    Bonjour Specieuse & Martini_Bird,

    Tout d'abord merci beaucoup pour ce coup de pouce.

    Cependant, lorsque je lis vos messages j'ai l'impression de lire quelquechose qui vient du futur.

    Clairement j'y comprend rien bien que j'y mette toute ma bonne volontée.

    Pensez-vous pouvoir me donner quelquechose de moins conceptuel avec des mots simples. Ou sinon connaissez-vous un site genre "Les maths pour les nuls" ou "les maths expliqué(e)s avec des mots contemporains"

    Merci d'avance

  9. Publicité
  10. #7
    invite986312212
    Invité

    Re : ? Graphe Contractible ?

    salut,

    en théorie des graphes on définit la contraction d'une arête comme suit: soient G un graphe (simple, non orienté) et ab une arête (a et b sont les sommets), la contraction de ab revient à supprimer a et b et à les remplacer par un nouveau sommet z, et à remplacer toutes les arêtes ca ou cb par une nouvelle arête cz (et si on avait un triangle abc, on ne garde qu'une seule arête cz, de façon à obtenir un graphe simple). Cette définition s'applique à tout graphe, planaire ou non, et ne fait pas intervenir de topologie.

    ensuite on définit une contraction d'un graphe comme une suite finie de contractions d'arêtes, et on remarque (et on doit pouvoir démontrer) que l'ordre des contractions n'a pas d'importance.

    maintenant un graphe contractable je ne sais pas ce que c'est, parce que clairement tout graphe peut être contracté jusqu'à un point. Par contre on utilise parfois le fait que tel graphe peut être contracté en un autre graphe (ce n'est pas toujours vrai évidemment).

    je ne sais pas si ça répond à ta question.

Sur le même thème :

Discussions similaires

  1. Tracé de graphe 2D
    Par Melquiades dans le forum Logiciel - Software - Open Source
    Réponses: 11
    Dernier message: 19/05/2007, 11h39
  2. graphe surface 3D
    Par BeBo* dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 01/11/2006, 13h18
  3. Un petit graphe ...
    Par mécano41 dans le forum Science ludique : la science en s'amusant
    Réponses: 11
    Dernier message: 16/06/2006, 20h41
  4. graphe
    Par sahdow dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 02/06/2006, 11h37
  5. Graphe de Feynman
    Par destroy dans le forum Physique
    Réponses: 15
    Dernier message: 08/03/2006, 20h11