Remerciez-le!

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

Devoir algo graphes mi1 2021

REPUBLIQUE DU SENEGAL UNIVERSITE IBA DER THIAM DE THIES UFR DES SCIENCES ET TECHNOLOGIE SET DEPARTEMENT INFORMATIQUE MASTER INFORMATIQUE Devoir d ? Algorithme de Graphes Membres du Groupe Khardiata SOW Mame Cheikh SYLLA Falilou Gueye Encadreur Dr KOREA Année universitaire ?? CExercice L ? objectif de l ? exercice est de trouver le nombre minimum de fréquences di ?érentes à utiliser Méthode de résolution Pour résoudre ce problème nous adoptons la démarche suivante Etape Dans cette première partie il s ? agit de sortir les di ?é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 Représentation du Graphe G Figure Graphe G Etape Résolution Pour chercher le minimum de fréquences di ?é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 o ? G ? n - ?? G C ? 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 Alors ? G Donc ? G ? Le degré maximal du graphe est de alors r Le nombre de sommet du graphe est de alors n On cherche la plus grande Stable Ta Tc Tf est la plus grande clique et son cardinal est Alors ?? G ? G ? n - ?? G ? G ? ?? Donc ? G ? Les relations et entrainent que ? ? G ? Conclusion Alors le nombre minimum de fréquences di ?érentes à utiliser est de fréquences ? Exercice 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 Représentation du Graphe G Correspondant CFigure Graphe G Etape 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 o ? G ? n - ?? G On détermine d ? abord la plus grande clique Figure Mise en évidence du plus clique Comme le montre le graphe la plus grande clique est le graphe C dont sont ordre est alors ? G ce qui entraine que ? G ? En second temps on cherche le nombre exact de