Question sur la complexité d'un algorithme en théorie des graphes

**Kenshin01** · 28/09/2021, 09h37

Bonjour je vous contacte par rapport à un exercice que je trouve dur au niveau de la compléxité

Soit l’algorithme de construction de graphe planaire suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
fonctionG = planaire(G)
      tant que G n’est pas planaire faire
                  pour tout 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

Les questions sont les suivantes : Quelle est la complexité de cet algorithme ? Finit-il toujours ?

En espérant être aidé

**tbc92** · 28/09/2021, 10h47

J'essaie de réfléchir, je n'ai pas la réponse.

Déjà, j'ai envie d'inverser les questions.
La complexité d'un algorithme, c'est en gros calculer le nombre d'opérations que le programme va effectuer.
Si dans certains cas l'algorithme ne finit pas (il tourne en boucle de façon infinie), ça veut dire que l'algorithme est de complexité infinie.

Du coup si on commence par répondre à la 1ère question en disant que l'algorithme est en n^5 ou même n^10 ... par exemple, alors ça y est, on a répondu à la 2ème question, l'algorithme se finit forcément.

Pour la complexité de l'algorithme, on peut déjà commencer par le 'coeur' du programme.

Il y a un test dans ton algorithme : si on diminue le nombre d’intersections d’arcs alors

Tu peux déjà essayer d'évaluer la complexité de ce test

Accessoirement, oublions l'exercice.
Ceci est un exercice, ou un besoin perso ?
J'étais tombé sur un jeu qui correspond exactement à cet algorithme, j'adorais ce jeu. on avait un graphe, non planaire, et il fallait déplacer des points jusqu'à obtenir un graphe planaire. Le graphe était conçu de façon à ce qu'il y ait toujours une solution.
Je ne trouve plus le lien vers ce jeu. Si tu as ça, je suis très intéressé

**Kenshin01** · 28/09/2021, 10h57

C'est un exercice que je dois faire absolument sur cette algorithme je ne comprends pas tres bien?
Cordialement

**WhiteCrow** · 28/09/2021, 11h56

Bonjour,

techniquement un algo doit terminer … mais passons ce petit abus de langage.
La complexité de ton algo va dépendre des primitives que tu emploies comme «est planaire» (l. 3) par exemple.
Mais ton algo ne se termine pas dans tous les cas de figures … que se passe-t-il si :

le graphe que tu dois dessiner n'est pas planaire ?
tous les nœuds de ton graphe sont aux mêmes coordonnées ?
…

**Kenshin01** · 28/09/2021, 12h01

Bah j'imagine que si le graphe n'est pas planaire l'algorithme s'arrêtera ?

**WhiteCrow** · 28/09/2021, 12h07

bah il aura du mal à s'arrêter avec une boucle comme tant que G n’est pas planaire faire.

**Kenshin01** · 28/09/2021, 12h27

Du coup cela donnera une boucle infini ?

**WhiteCrow** · 28/09/2021, 12h53

tu n'as pas testé sur des exemples simples ou classiques ou border line ?
tu peux dérouler l'algo à la main … cela te permettra de mieux comprendre son fonctionnement. Mais à ton avis, si tu fournis un graphe non planaire à un algorithme qui possède une boucle tant que G n’est pas planaire faire et que la seule manière de sortir de ladite boucle est d'invalider la conditionnelle , finira-t-elle ?

**Kenshin01** · 28/09/2021, 13h04

Non elle ne finira pas du coup ?

**Flodelarab** · 28/09/2021, 13h06

Bonjour

Il me semble qu'il y a confusion entre planaire (en l'état) et planaire (en déplaçant les sommets). Un graphe est planaire lorsqu'il n'y a pas d'intersections d'arêtes. On peut trouver un dessin de graphe qui a des intersections, mais qui devient évidemment planaire en déplaçant des nœuds. C'est tout le principe des jeux "Untangle".

Cet algorithme doit probablement s'arrêter pour des graphes intrinsèquement planaires, mais planter pour K5 ou K3,3, par exemple.

**Kenshin01** · 28/09/2021, 13h10

Non elle ne finira pas du coup ?

**tbc92** · 28/09/2021, 13h17

WhitCrow parlait évidemment d'un graphe qui n'est pas planaire, et qu'on ne peut pas rendre planaire.

Et évidemment, il l'a dit 2 fois, on aura une boucle infinie.

Ici l'exercice est très compliqué. Personnellement, je ne sais pas répondre, et je suis convaincu que personne ne sait répondre.

On peut déjà donner quelques notations. Au départ, on a un graphe avec S sommets, A arcs , et C croisements.
On va être cool, on va supposer que tous les graphes qui sont dans la 'base de données' sont des graphes qu'on peut rendre planaires.
Là, on peut vaguement apporter des éléments de réponse.