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 :

Algorithme pour transformer un graphe en un graphe planaire


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2018
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2018
    Messages : 2
    Points : 2
    Points
    2
    Par défaut Algorithme pour transformer un graphe en un graphe planaire
    Bonjours à tous•tes,

    J'essaye de calculer la complexité d'un algorithme transformant un graphe quelconque en un graphe planaire, via l'utilisation des barycentres.

    Voici l'algorithme :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Fonction G = planaire(G)
    Tant que G n'est pas planaire faire 
         pour tous x sommet de G faire 
               V = liste des voisins de x 
               M = barycentre des sommets de V 
               si on diminue le nombre d'intersections d'arcs 
                          alors placer x en M 
               fin si 
         fin faire
    fin faire

    Voici mon calcul concernant l'algorithme dont je suis pas certains :

    Premièrement l'algorithme ne précise pas si l'entrée prend uniquement des graphes quelconque ou s'il peut également prendre des graphes déjà planaire. Dans ce cas :
    • Meilleur cas (= graphe planaire en entrée) = C(0) (aucune opérations de complexité n'est effectué)
    • Pire cas (= graphe non planaire en entrée) : il y a alors deux sous cas
      • le graphe peut devenir planaire : il y a donc 2 affectations (V et M) et 1 comparaison. De plus il y a 1/q * n déplacement, où q = probabilité que la condition soit remplie. La complexité dans ce cas-ci est alors, C = 3n + 1/q * n
      • le graphe ne peut pas devenir planaire : la complexité est infinie (boucle infinie)


    Dans un soucis de simplification pour calculer la complexité moyenne de l'algorithme, je décide de supprimer le cas où le graphe ne peut pas devenir planaire.
    Ainsi, Cmoyenne = Cmin + Cmax
    = 0 + 3n + 1/q * n
    = 3n + 1/q * n
    = O(n)

    Qu'en pensez-vous ?
    Merci pour votre aide

  2. #2
    Membre du Club
    Profil pro
    Inscrit en
    février 2010
    Messages
    46
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2010
    Messages : 46
    Points : 53
    Points
    53
    Par défaut Graphe planaire pour sat 3
    On dirait la résolution de sat 3 avec un graphe planaire

Discussions similaires

  1. Algorithme pour passer par tout les points d'un graphe
    Par Hamza Tadlaoui dans le forum Mathématiques
    Réponses: 2
    Dernier message: 07/08/2017, 13h35
  2. Un algorithme quasipolynomial pour l’isomorphisme de graphes
    Par dourouc05 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 12/01/2016, 16h33
  3. [Graphes] Algorithme pour transformer un graphe en graphe fortement connexe
    Par pikachu56 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 23/11/2011, 02h08
  4. Un algorithme simple pour afficher un graphe
    Par wondersonic dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 04/02/2008, 01h23
  5. problème d'algorithme pour trouver les circuit d'un graphe
    Par marc_dd dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 21/08/2006, 17h36

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