Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REPUBLIQUE DU SENEGAL ******* UNIVERSITE IBA DER THIAM DE THIES UFR DES SCIENCE

REPUBLIQUE DU SENEGAL ******* UNIVERSITE IBA DER THIAM DE THIES UFR DES SCIENCES ET TECHNOLOGIE (SET) DEPARTEMENT INFORMATIQUE MASTER 1 INFORMATIQUE Membres du Groupe : Khardiata SOW Mame Cheikh SYLLA Falilou Gueye Encadreur Dr KOREA Année universitaire 2020 – 2021 Devoir d’Algorithme de Graphes Exercice 1 : L’objectif de l’exercice est de trouver le nombre minimum de fréquences différentes à utiliser. Méthode de résolution : Pour résoudre ce problème nous adoptons la démarche suivante : Etape 1 : Dans cette première partie il s’agit de sortir les différents composants du graphe G en se basant sur l’arbre donnée par l’énoncé. - Chaque région est représenté comme un nœud du graphe G. - Deux nœud sont adjacents si les régions correspondantes partagent au moins un sommet dans l’arbre de départ. -Les sommet sont Ta, Tb, Tc, Td, Te, Tf et Tg Etape 2 : Représentation du Graphe G Figure 1 : Graphe G Etape 3 : Résolution Pour chercher le minimum de fréquences différentes à utiliser, il s’agira de minorer le nombre chromatique (G) en se basant sur les propriétés suivantes : o (G)  (G) o (G)  r + 1 o (G)  n + 1 - (G) (G) : représente le degré de la plus grande clique r : l’ordre du graphe n : le nombre de sommet du graph (G) : le cardinal du plus grand stable On cherche la plus grande clique {Tc, Td, Te, Tg} est la plus grande clique et son cardinal est 4 Alors (G) = 4 Donc (G)  4 (1) Le degré maximal du graphe est de 6 alors r =6 Le nombre de sommet du graphe est de 7 alors n =7 On cherche la plus grande Stable {Ta, Tc, Tf} est la plus grande clique et son cardinal est 3 Alors (G) = 3 (G)  n + 1 - (G) (G)  7 + 1 – 3 Donc (G)  5 (2) Les relations (1) et (2) entrainent que 4  (G)  5 Conclusion : Alors le nombre minimum de fréquences différentes à utiliser est de 4 fréquences. Exercice 2 : L’objectif de l’exercice est de trouver comment organiser ces épreuves de façon qu’aucun étudiant n’ait à passer deux épreuves en même temps et cela sur une durée minimale ? Méthodologie de résolution : Pour résoudre ce problème nous adoptons la démarche suivante : Etape 1 : Représentation du Graphe G Correspondant Figure 2 : Graphe G Etape 3 : Résolution Dans cet exercice il s’agit de déterminer la valeur exacte du nombre chromatique (G) du graphe G. Pour cela on se base sur les propriétés suivantes : o (G)  (G) o (G)  r + 1 o (G)  n + 1 - (G) On détermine d’abord la plus grande clique. Figure 3 : Mise en évidence du plus clique Comme le montre le graphe la plus grande clique est le graphe {1, 2, 3, 4} dont sont ordre est 4 alors (G) = 4 ce qui entraine que (G)  4 (1) En second temps on cherche le nombre exact de stable. Figure 4 : Graphe G des stables Comme le montre le graphe on a 4 ensembles de stables dont S1 = {1,5}, S2 = {2,6} S3 = {4,7} S4 = {3}. S1, S2, S3 et S4 forment une partition de l’ensemble des sommets en 4 stables alors (G)  4 (2) or d’après (1) (G)  4 donc (G) = 4 Conclusion : Il faudrait quatre périodes pour organiser les examens Exercice 3 : L’objectif de l’exercice est de montrer comment déterminer le nombre minimum d’armoires frigorifiques de grande capacité qui seront nécessaires au stockage des produits pharmaceutiques. Méthode de résolution : Pour résoudre ce problème nous adoptons la démarche suivante : Etape 1 : Dans cette première partie il s’agit de sortir les différents composants du graphe G en se basant sur le tableau donné par l’énoncé. Nous allons avant toutes choses construire le tableau des correspondances en fessant l’intersection des intervalles de températures. - Deux produits peuvent être stockés dans la même d’armoires frigorifiques si l’intersection (I) des intervalles de températures [min, Max] de ces deux produits n’est pas vide (I≠ {Ø}). - Dans le tableau ci-dessous, une tiré (-) signifie que les produits ne peuvent pas être stockés dans la même armoires frigorifiques. - Une case marque par le symbole (√) signifie que les produits peuvent être stockés dans la même d’armoires frigorifiques. Produits P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P1 √ √ √ √ √ √ - √ - - P2 √ √ √ √ √ √ - - - - P3 √ √ √ - √ - - - - - P4 √ √ - √ √ √ √ √ √ - P5 √ √ √ √ √ - √ √ √ √ P6 √ √ - √ - √ - √ - - P7 - - - √ √ - √ √ √ √ P8 √ - - √ √ √ √ √ √ √ P9 - - - √ √ - √ √ √ √ P10 - - - - √ - √ √ √ √ Tableau 1: Tableau des correspondances Etape 2 : Représentation du Graphe G - Chaque produit Pi est représenté comme un nœud du graphe G. - Deux nœud sont adjacents si les produits correspondants ne peuvent pas être stocker dans une armoire frigorifique. -Les sommets sont P1, P2, P3…P10 Figure 6 : Graphe D’incompatibilité Etape 3 : Résolution Dans cet exercice il s’agit de minorer le nombre chromatique (G) du graphe G. Pour cela on se base sur les propriétés suivantes : o (G)  (G) o (G)  r + 1 o (G)  n + 1 - (G) On détermine d’abord la plus grande clique. Figure 3 : Mise en évidence de la plus grande clique Comme le montre le graphe la plus grande clique est le graphe {P3, P6, P9} dont sont ordre est 3 alors (G) = 3 ce qui entraine que (G)  3 (1) En second temps on cherche le plus grand stable. Figure 4 : Graphe G mise en évidence des stables Le degré maximal du graphe est de 6 alors r =6 Le nombre de sommet du graphe est de 7 alors n =10 Comme le montre le graphe on a 3 ensembles de stables dont S1 = {P5, P7, P8, P9, P10}, S2 = {P1, P2, P4, P6} S3 = {P3}. S1, S2 et S3 forment une partition de l’ensemble des sommets en 3 stables. S1= {P5, P7, P8, P9, P10} est le plus grand stable et son cardinal est 5 Alors (G) = 5 (G)  n + 1 - (G) (G)  10 + 1 – 5 Donc (G)  6 (2) Les relations (1) et (2) entrainent que 3  (G)  6 Conclusion : Alors le nombre minimum de d’armoires frigorifiques de grande capacité qui seront nécessaires au stockage des produits pharmaceutiques est de 3. Exercice 4 : Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des 16 segments de la figure suivante exactement une fois ? Méthodologie de résolution : Pour résoudre ce problème nous adoptons la démarche suivante : Etape 1 : Représentation du Graphe G Correspondant Dans cette partie il s’agit de sortir les différents composants du graphe G correspondant à la figure donnée en haut. - Chaque Case de la figure est considéré comme un sommet du graphe G -Le milieu de chaque segment séparant deux cases représente un arc qui relie les sommet correspondants aux case séparées par ce segment. - On numérote les cases par des lettre alphabétiques Etape 2 : Représentation du Graphe G Correspondant Figure 5 : Graphe G correspondant Etape 3 : Résolution o Le degré de A et B est de 4 o Le degré de D et f est de 5 o Le degré de C et E est de 3 Le nombre de sommet de degré impaire est supérieur au nombre de sommet de degré paire. Alors le graphe ne peut être eulériens Conclusion : Il est impossible de tracer une courbe, sans lever le crayon, qui coupe les 16 segments car il y a plus de deux sommets de degré impair. Bibliographie : - Outil utiliser pour construire les diagrammes : https://lucid.app/ Lucide App est un logiciel qui permet de construire des diagramme en ligne gratuitement. uploads/Science et Technologie/ devoir-algo-graphes-mi1-2021.pdf