IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Graphes et sous graphes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    491
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 491
    Par défaut Graphes et sous graphes
    Hello,

    Voici mon problème:

    Je dispose d'un ensemble de graphe non orientés, que je représente de deux facons: une liste de voisins connectés à chaque sommet (a chaque sommet correspond donc une liste de sommets connectés) , et la liste des arrètes (liste de couple de sommets donc).

    Ce que j'aimerai faire, c'est a partir d'un sous graphe déterminé sur un des graphes connus, pouvoir retrouver ce sous graphe dans chacun des autres graphes (en d'autre termes, récupérer les sommets/connexions qui correspondent au sous graphe désiré).

    L'application de mon problème peut se faire par exemple sur des molécules: on récupère un motif atomique donné (par exemple, 6 atomes formant un anneau), et on recherche ce type de squellette dans un ensemble d'autres molécules.

    Quelqu'un sait-il si un algorithme existe déja pour faire ce genre de chose? J'ai pour le moment réfléchi un peu mais je n'ai pas encore trouvé de solution, n'étant pas spécialiste de l'algorithmique des graphes que je sais parfois trés complexe...

    Merdi d'avance

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Ca s'appelle du "Subgraph Matching" et c'est un sujet très actif dans le petit monde de l'algorithmie.

    Je te recommande la lecture de:

    - Graph Indexing: A Frequent Structure*based Approach

    et

    - Algorithmics and Applications of Tree and Graph Searching

    A+
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    491
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 491
    Par défaut
    Je sens que ca ne va pas être de la tarte

    Merci en tout cas, je vais essayer de comprendre tout ca.
    Si quelqu'un a d'autre pistes, un début d'idée ou d'algo, n'hésitez pas.

Discussions similaires

  1. Extraction de sous graphes d'un graphe
    Par anna0510 dans le forum C++/CLI
    Réponses: 2
    Dernier message: 05/05/2012, 04h04
  2. Création de sous-graphes de poids minimaux dans un graphe planaire
    Par tomjr dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 31/03/2010, 10h51
  3. graphe 3D sous excel
    Par rabia dans le forum Excel
    Réponses: 1
    Dernier message: 02/02/2010, 09h47
  4. Couleur des graphes disponibles sous SAS
    Par stefsas dans le forum ODS et reporting
    Réponses: 3
    Dernier message: 06/08/2008, 16h47
  5. [graphe]creation de sous graphe
    Par deeal dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 22/04/2005, 19h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo