Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Untitled Prezi

No description
by

amani ghali

on 11 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

Algorithme de WELSH ET POWELL
Algorithme de GLOUTON
L'allocation des bandes de frequences dans un reseau cellulaire ou des cellules voisines ne doivent pas avoir la meme bande de frequences afin d'eviter les interferences.

La planification des examens dans une universite de sorte qu'un etudiant n'ait pas deux examens au meme moment.
Algorithme de DSATUR 
Projet complexite "Coloration des graphes" »
Presente par:

EL GHALI Amani
DRIDI Abir
SOUILMI Aymen
BOUMAIZA Wael
KAROUI Nour

1.Introduction

2.Domaine d'applications

3.Algorithmes proposees

4.Etude Comparative

Introduction
Domaine d'applications
Cet algorithme donne une bonne coloration du graphe mais n’assure pas que la coloration est minimale.

Entrée – Un graphe quelconque
Sortie – Une coloration propre
1 n := ;
2 Deg := Tableau (Taille : n) (Defaut : 0);
3 Sommet := Tableau (Taille : n) (Defaut : 0);
4 Pour i de 0 à n-1 faire
5 Deg.(i) <=d(i) ;
6 Sommet.(i) <= i
7 Fin Pour;
8 Tri (Tableau : Sommet);
9 Coloration séquentielle (Graphe : G) (Numérotation : Sommet)
 Si on utilise par exemple un tri par dénombrement (en O(n) , car les degrés de deux sommets ne peuvent différer de plus de n ), on obtient un algorithme de complexité O(n+m) . Si on utilise plutôt un tri par comparaison, l'algorithme est alors de complexité O( n ln(n)+m) .
Complexite
L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens ou il colorie un seul sommet à la fois et tel que:

Au départ le graphe n'est pas colore
On colorie un sommet non-deja colore
On stoppe DSATUR quand tous les sommets de G sont colores.

On definit le degre-couleur d'un sommet comme son nombre de voisins deja colores.

Le degre-couleur, qui va evoluer au cours de l'algorithme, initialise à 0 pour tout sommet .

Pour i de 0 à n-1 faire
x := 0;
# Recherche du sommet de Dsat max #
Pour y de 0 à n-1 faire
Si Couleur.(x) -1 & Dsat.(y) Dsat.(x) faire
x := y
Fin Si
Fin Pour
Fin Pour
La complexité de l'algorithme dépend de l'implémentation que l'on en fait: O(n²)

Complexite
Constitue probablement la methode de coloration la plus intuitive
Tres facile à mettre en oeuvre.
Un algorithme glouton construit une solution pas à pas :
Sans revenir sur ses décisions

En effectuant à chaque étape le choix qui semble le meilleur

En espérant obtenir un résultat optimum global

Principe :
On prend le probleme d'epreuve de gymnase : on veut qu'elle se déroule sur 24 h, le plus grand nombre possible d'epreuves.
Chaque épreuve étant caractérisée par une heure de debut et une heure de fin.
On cherche maintenant le nombre minimal de gymnases permettant le deroulement de toutes les preuves.
//initialisation
L=TriGlouton(E); //tri selon le critère Glouton
Solpartielle= ensemble (ou suite) "vide";
//calcul "glouton"
tant que Solpartielle non solution ( et L non vide )
x=premier(L); // $x$ selon critère glouton
si Solpartielle + x est une solution partielle alors S = S + x;
//dans certains problèmes, c’est toujours le cas
L=queue(L); //x ne sera plus considéré
fin tant que;



La complexité est donc souvent de l’ordre de n log n .


Complexite
Etude Comparative
Un graphe est un ensemble de sommets reliés entre eux par des arêtes symbolisant une certaine relation.
Colorer un graphe, c’est affecter une couleur à chaque sommet, de sorte que 2 sommets adjacents sont toujours de couleurs différentes tout en utilisant un nombre minimal de couleurs. Ce dernier est appelé le nombre chromatique .

 Notre objectif est de concevoir et d’implémenter un algorithme efficace et fiable pour résoudre le problème de la coloration de graphes qui est un classique de la théorie des graphes.

Objectif
Full transcript