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 :

Connexité et degré minimum


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    110
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2009
    Messages : 110
    Par défaut Connexité et degré minimum
    Bonjour à tous,

    j'aimerai pouvoir générer, à partir d'un ensemble de noeuds (spécifiés par leur coordonnée [x,y]), un graphe qui soit connexe et k-connecté.

    Le paramètre k serait une entrée de mon algorithme.

    Ma première idée serait d'utiliser un algorithme d'arbre recouvrant type Prime ou Kruskal afin d'avoir au moins un chemin entre chaque paire de noeud.

    Ensuite, je testerais le degrés de chacun des noeuds en venant ajouter un arc entre le noeud courant et un autre noeud choisit aléatoirement pour atteindre le degré k...

    Existe-t-il des algorithmes précis pour ce genre de problème?

    Merci d'avance.

  2. #2
    Membre expérimenté Avatar de Acrim
    Profil pro
    En recherche d'emploi
    Inscrit en
    Septembre 2010
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Septembre 2010
    Messages : 134
    Par défaut
    Citation Envoyé par dvp_zero Voir le message
    Bonjour à tous,

    j'aimerai pouvoir générer, à partir d'un ensemble de noeuds (spécifiés par leur coordonnée [x,y]), un graphe qui soit connexe et k-connecté.

    Le paramètre k serait une entrée de mon algorithme.

    Ma première idée serait d'utiliser un algorithme d'arbre recouvrant type Prime ou Kruskal afin d'avoir au moins un chemin entre chaque paire de noeud.

    Ensuite, je testerais le degrés de chacun des noeuds en venant ajouter un arc entre le noeud courant et un autre noeud choisit aléatoirement pour atteindre le degré k...

    Existe-t-il des algorithmes précis pour ce genre de problème?

    Merci d'avance.
    J'ai trouvé plusieurs définitions pour un graphe k-connecté :
    -Un graphe est dit k-connecté si pour chaque paire de nœuds il existe au moins k chemins de noeuds disjoints connectant le graphe
    -Un graphe est k-connecté si tous ses sommets sont de degré k.

    Je pense que tu prends la deuxième. Es tu sûr que toutes les combinaisons sont possibles (en fonction de la parité de k et de n) ?

    Personnellement je tentai une approche "incrémentale". Je commencerai par un graphe avec peu de nœud et un petit k. Et j'augmenterai petit à petit le nombre de nœud et la valeur de k. Ou par construction à partir de graphes triviaux. Ce ne sont que des pistes je ne garantis pas que la solution se trouve là .

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    110
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2009
    Messages : 110
    Par défaut
    Merci pour ton message.

    C'est effectivement la deuxième définition qui m'intéresse.

    Lorsque tu parles des combinaisons possibles en fonction de la parité de k et de n, que veux-tu dire par là?
    Qu'il ne serait pas toujours possible d'atteindre n'importe quelle valeur de k en fonction du nombre n de noeuds du graphe?

    Si j'ai bien compris, ça ne devrait pas trop poser de problème car le nombre de noeuds de mon graphe est grand.

    Oui ton idée est bien mais le problème c'est que le nombre de noeuds est fixé au départ, il me sera donc difficile de partir d'un graphe "général" à toute les situation.

  4. #4
    Membre expérimenté Avatar de Acrim
    Profil pro
    En recherche d'emploi
    Inscrit en
    Septembre 2010
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Septembre 2010
    Messages : 134
    Par défaut
    Citation Envoyé par dvp_zero Voir le message
    Lorsque tu parles des combinaisons possibles en fonction de la parité de k et de n, que veux-tu dire par là?
    Qu'il ne serait pas toujours possible d'atteindre n'importe quelle valeur de k en fonction du nombre n de noeuds du graphe?
    Oui je me demandais si toutes les combinaisons n-k sont possibles (autres que les cas ou k>=n).


    Citation Envoyé par dvp_zero Voir le message
    Oui ton idée est bien mais le problème c'est que le nombre de noeuds est fixé au départ, il me sera donc difficile de partir d'un graphe "général" à toute les situation.
    Je pensais partir par exemple, pour un k fixé, d'un graphe complet à (k+1) nœuds. Et d'augmenter progressivement le nombre de nœud jusqu'à avoir n nœuds. Reste à mettre au point la méthode permettant de passer d'un graphe connexe de degré k à m sommets à un graphe connexe de degré k à (m+1) sommets. Mais j'avais l'intuition que cela pouvait se faire simplement.

    Après ça reste qu'une idée, c'est toi qui voit ce qui te semble le plus prometteur.

  5. #5
    Membre habitué
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    9
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2010
    Messages : 9
    Par défaut
    Bonjour je pense que tu parle d'un graphe K-régulier c'est à dire que chaque sommet est connecté à K autres sommets .

    pour les combinaisons , elle ne sont pas toutes possibles , je sais qu'il y a deux contraintes ( et peut être y en a d'autres ) .

    1)
    k doit être inférieur à N , un graphe à N sommet peut être au max (N-1)-régulier donc chaque nœud dans ce cas est lié à tous les autres nœuds et on dit que c'est un graphe complet .

    2)
    le nombre d’arrêtés est de k*n/2 ( tu peux vérifier ) et donc il y a une contrainte de parité du produit K*n car le nombre arrêtes est entier (évidemment )
    pare exemple tu peux pas avoir un graphe d'ordre N et K-régulier ou K et N sont impairs .

    pour l'algorithme je pense que j'en ai déjà vu Un ( qui est très simple à ce que je me rappelle ) , je vais le ré-chercher , mais tu peux me dire si tu veux générer un graphe quelconque ou tous les graphes ???

  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    110
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2009
    Messages : 110
    Par défaut
    Merci pour ce complément d'informations.

    Je viens d'allé voir la définition d'un graphe k-régulier et c'est bien ce que je veux à une nuance près : tous les noeuds de mon graphe ne sont pas obligés d'avoir le même degré. Il y a simplement une contrainte sur le degré minimum.

    Pour répondre à ta question, c'est bien un graphe quelconque que je veux générer.

    Merci beaucoup

  7. #7
    Membre habitué
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    9
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2010
    Messages : 9
    Par défaut
    Citation Envoyé par Acrim Voir le message
    Oui je me demandais si toutes les combinaisons n-k sont possibles (autres que les cas ou k>=n).




    Je pensais partir par exemple, pour un k fixé, d'un graphe complet à (k+1) nœuds. Et d'augmenter progressivement le nombre de nœud jusqu'à avoir n nœuds. Reste à mettre au point la méthode permettant de passer d'un graphe connexe de degré k à m sommets à un graphe connexe de degré k à (m+1) sommets. Mais j'avais l'intuition que cela pouvait se faire simplement.

    Après ça reste qu'une idée, c'est toi qui voit ce qui te semble le plus prometteur.
    excusez moi je pensais que vous parlez des graphes réguliers

    sinon je pense que pour le passage de m à m+1 en gardant k ,
    tu peux retirer k/2 ou(k+1/2 selon la parité de k ) arcs associés à k ou (k+1) nœuds ( on ne supprime pas plus d'un arc pour un nœud) et ajouter nouveau nœud puis le lier par k ou (k+1) arcs à ces nœuds
    si j'ai bien compris

  8. #8
    Membre expérimenté Avatar de Acrim
    Profil pro
    En recherche d'emploi
    Inscrit en
    Septembre 2010
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Septembre 2010
    Messages : 134
    Par défaut
    Bonjour, désolé pour la méprise, j'avais compris la même chose que Mohammed_S. Effectivement si k est seulement le degré minimum à atteindre, la démarche que tu décris dans ton premier message devrait fonctionner.

Discussions similaires

  1. recuperer les minimum d'une séquence d'entiers?
    Par novice12 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 25/01/2005, 03h44
  2. trouver le minimum d'une liste
    Par speed034 dans le forum MS SQL Server
    Réponses: 4
    Dernier message: 08/12/2004, 12h29
  3. Taille minimum pour une JFrame ou une JInternalFrame
    Par sixkiller dans le forum Agents de placement/Fenêtres
    Réponses: 2
    Dernier message: 30/11/2004, 15h26
  4. Réponses: 6
    Dernier message: 08/11/2004, 14h18
  5. résolution de equation 2nd degré
    Par isidore dans le forum C
    Réponses: 30
    Dernier message: 29/02/2004, 10h46

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