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
    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
    Graphe planaire pour sat 3
    On dirait la résolution de sat 3 avec un graphe planaire

###raw>template_hook.ano_emploi###