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

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:

---

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é

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é ;)

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

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 :

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

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

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

Du coup cela donnera une boucle infini ?

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 ?

Non elle ne finira pas du coup ?

Bonjour :coucou:

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.

Non elle ne finira pas du coup ?

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.

Je pensais que l'algo auraitp lus simple que prévu dommage. Je vais voir ce que je peux faire

ce que tu peux déjà faire est nous donner l'énoncé de ton problème plutôt que des petits bouts …

L'énoncé c'est uniquement cela y a rien d'autre que le prof m'avait donné