? Graphe Contractible ?

[invite4cdc4bd9]

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!
-----

[invite2ac85754]

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

[invite4793db90]

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.

[invite2ac85754]

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.

[A voir en vidéo sur Futura]

[invite4793db90]

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 !

[invite4cdc4bd9]

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

[invite986312212]

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.