Upload
rafael
View
64
Download
3
Embed Size (px)
DESCRIPTION
Mathématiques CST. - GRAPHES - Composantes et types. Mathématiques CST - GRAPHES : Composantes et types -. Définitions. Les graphes sont des représentations mathématiques qui servent à illustrer des situations qui ont une certaine organisation. - PowerPoint PPT Presentation
Citation preview
Mathématiques Mathématiques CSTCST
-- GRAPHES GRAPHES - - Composantes et typesComposantes et types
Mathématiques Mathématiques CSTCST- - GRAPHESGRAPHES : : Composantes et types -Composantes et types -
Définitions
Les Les graphesgraphes sont des représentations mathématiques qui sont des représentations mathématiques qui servent à servent à illustrerillustrer des situations qui ont une certaine des situations qui ont une certaine organisationorganisation..
Ex. : Organisation du système de santé.Ex. : Organisation du système de santé.
Elles permettent souvent de faire des Elles permettent souvent de faire des choix d’organisation choix d’organisation optimauxoptimaux..
Ex. : Le facteur qui distribue le courrier de manière à minimiser ses Ex. : Le facteur qui distribue le courrier de manière à minimiser ses déplacements.déplacements.
Les Les graphesgraphes sont constitués d’ensemble de points, appelés sont constitués d’ensemble de points, appelés « « sommetssommets » et de liens, appelés « » et de liens, appelés « arêtesarêtes » reliant ses sommets. » reliant ses sommets.
AA
EE
BB
DD
CC
SommetsSommets
ArêtesArêtes
BoucleBoucle
BoucleBoucle : Arête qui débute et se termine au même sommet. : Arête qui débute et se termine au même sommet.
NoteNote : La forme de l’ : La forme de l’arêtearête n’a pas d’importance (ligne droite ou courbe) n’a pas d’importance (ligne droite ou courbe)
Les Les graphesgraphes illustrent les illustrent les relationsrelations qui existent entre les sommets. qui existent entre les sommets.
AA
EE
CC
DD
BB
Ex. : Voici la représentation d’un mini-réseau Facebook de 5 personnes.Ex. : Voici la représentation d’un mini-réseau Facebook de 5 personnes.
On constate donc, entre autres, que A est « ami » avec B.On constate donc, entre autres, que A est « ami » avec B.
Cependant, A n’est pas « ami » avec C.Cependant, A n’est pas « ami » avec C.
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
DegréDegré d’un sommet : Nombre d’arêtes qui touchent au sommet. d’un sommet : Nombre d’arêtes qui touchent au sommet.
SommetsSommets DegrésDegrés
AABBCCDDEE
1122443322
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
Chaîne Chaîne : Suite d’arêtes consécutives.: Suite d’arêtes consécutives.
Ex. : Ex. : ADBEADBE
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
ChaîneChaîne : Suite d’arêtes consécutives.: Suite d’arêtes consécutives.
Ex. : Ex. : ADBEADBE
Cycle Cycle : Chaîne qui commence et se termine au même sommet.: Chaîne qui commence et se termine au même sommet.
Ex. : Ex. : BBECDECDBB
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
ChaîneChaîne simple simple : Chaîne qui ne passe pas deux fois par la même arête.: Chaîne qui ne passe pas deux fois par la même arête.
Ex. : Ex. : ADBE ADBE est une chaîne est une chaîne simplesimple..
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
ChaîneChaîne simple simple : Chaîne qui ne passe pas deux fois par la même arête.: Chaîne qui ne passe pas deux fois par la même arête.
Ex. : Ex. : ADBE ADBE est une chaîne est une chaîne simplesimple..
Ex. : Ex. : ADBECDB ADBECDB n’est pasn’est pas une chaîne une chaîne simplesimple..
Cycle Cycle simple simple : Cycle qui ne passe pas deux fois par la même arête.: Cycle qui ne passe pas deux fois par la même arête.
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
LongueurLongueur d’une chaîne : Nombre d’arêtes dans la chaîne ou le cycle. d’une chaîne : Nombre d’arêtes dans la chaîne ou le cycle.
Ex. : Ex. : La chaîne La chaîne ADBE ADBE a une a une longueurlongueur de de 33..
Voici un graphe quelconque :Voici un graphe quelconque :
AA
EE
BB
DD
CC
Longueur d’une chaîne : Nombre d’arêtes dans la chaîne ou le cycle.Longueur d’une chaîne : Nombre d’arêtes dans la chaîne ou le cycle.
Ex. : Ex. : La chaîne ADBE a une longueur de 3.La chaîne ADBE a une longueur de 3.
Distance Distance entre 2 sommets : Longueur de la chaîne entre 2 sommets : Longueur de la chaîne la plus courtela plus courte entre entre ces 2 sommets.ces 2 sommets.
Ex. : Ex. : La distance entre La distance entre EE et et CC est de est de 11..
Mathématiques Mathématiques CSTCST- - GRAPHESGRAPHES : : Composantes et types -Composantes et types -
Types de graphes
A) Graphe A) Graphe CONNEXECONNEXE
Graphe où il existe une chaîne pour aller à n’importe quel des Graphe où il existe une chaîne pour aller à n’importe quel des sommets du graphe.sommets du graphe.
AA
EE
CC
DD
BB
CONNEXECONNEXE
AA
EE
CC
DD
BB
NON-CONNEXENON-CONNEXE
B) Graphe B) Graphe ORIENTÉORIENTÉ
Graphe où chacune des arêtes est orientée (flèche).Graphe où chacune des arêtes est orientée (flèche).
AA
EE
CC
DD
BB
ORIENTÉORIENTÉ NON-ORIENTÉNON-ORIENTÉ
AA
EE
CC
DD
BB
Terminologie des graphes orientés :Terminologie des graphes orientés : ArcsArcs = Arêtes = Arêtes
CheminsChemins = Chaînes = Chaînes
CircuitsCircuits = Cycles = Cycles
C) Graphe C) Graphe VALUÉVALUÉ
Graphe où chacune des arêtes a une valeur numérique.Graphe où chacune des arêtes a une valeur numérique.
VALUÉVALUÉ NON-VALUÉNON-VALUÉ
AA
EE
CC
DD
BB
AA
EE
CC
DD
BB1212 44
6622
1010
PoidsPoids de l’arête : Valeur attribuée à l’arête de l’arête : Valeur attribuée à l’arête
PoidsPoids d’une chaîne : Somme des valeurs attribuées à chaque d’une chaîne : Somme des valeurs attribuées à chaque arête de la chaîne.arête de la chaîne.
PoidsPoids du graphe : Somme des valeurs attribuées à chaque du graphe : Somme des valeurs attribuées à chaque arête du graphe.arête du graphe.
Ex. : Ex. : Le poids du graphe Le poids du graphe ABCDEABCDE est de est de 3434. .
D) D) ARBREARBRE
Graphe, connexe et non-orienté, qui ne comporte aucun cycle Graphe, connexe et non-orienté, qui ne comporte aucun cycle simple.simple.
ARBREARBRE ARBREARBRE
AA
EE
CC
DD
BB
AA
EE
CC
DD
BB
PAS UN ARBREPAS UN ARBRE
AA
EE
CC
DD
BB
Cycle simple !Cycle simple !
Mathématiques Mathématiques CSTCST- - GRAPHESGRAPHES : : Composantes et types -Composantes et types -
Chaîne et cycle EULÉRIENS
A) Chaîne A) Chaîne EULÉRIENNEEULÉRIENNE
Chaîne qui passe Chaîne qui passe une seule fois une seule fois par toutes les par toutes les arêtesarêtes du graphe. du graphe.
ConditionsConditions pour avoir une pour avoir une chaîne chaîne eulérienneeulérienne dans un graphe :dans un graphe :
Avoir exactement Avoir exactement 22 sommets* de degré sommets* de degré impairimpair..
* Ces * Ces 2 2 sommets sont le sommets sont le débutdébut et la et la finfin de la chaîne eulérienne. de la chaîne eulérienne.
Exemple #1 :Exemple #1 :
AA
EE
CC
DD
BBImpairImpair
ImpairImpair
La chaîne La chaîne BADECBADEC est une chaîne est une chaîne eulérienneeulérienne. .
La chaîne La chaîne CEDABCEDAB est aussi une chaîne est aussi une chaîne eulérienneeulérienne. .
Exemple #2 :Exemple #2 :
Il n’y a pas de chaîne Il n’y a pas de chaîne eulérienneeulérienne, car il n’y a pas , car il n’y a pas seulement seulement 22 sommets de degré sommets de degré impairimpair. .
ImpairImpair
ImpairImpair
ImpairImpair
ImpairImpair
AA
EE
CC
DD
BB
B) Cycle B) Cycle EULÉRIENEULÉRIEN
Cycle qui passe Cycle qui passe une seule fois une seule fois par toutes les par toutes les arêtesarêtes du graphe. du graphe.
ConditionsConditions pour avoir un pour avoir un cycle cycle eulérieneulérien dans un graphe :dans un graphe :
Avoir Avoir toustous les sommets de degré les sommets de degré pairpair..
Exemple #1 :Exemple #1 :
AA
EE
CC
DD
BB
PairPair
PairPair
PairPair
PairPair
PairPair
Le cycle Le cycle BCEDABBCEDAB est un cycle est un cycle eulérieneulérien. .
Exemple #2 :Exemple #2 :
Il n’y a pas de cycle Il n’y a pas de cycle eulérieneulérien, car tous les , car tous les sommets sommets ne sont pas ne sont pas de degré de degré pairpair. .
AA
EE
CC
DD
BB
ImpairImpair
PairPair
PairPair
ImpairImpair
PairPair
Mathématiques Mathématiques CSTCST- - GRAPHESGRAPHES : : Composantes et types -Composantes et types -
Chaîne et cycle HAMILTONIENS
A) Chaîne A) Chaîne HAMILTONIENNEHAMILTONIENNE
Chaîne qui passe Chaîne qui passe une seule fois une seule fois par tous les par tous les sommets sommets du du graphe.graphe.
Pour savoir si un graphe contient ou non une Pour savoir si un graphe contient ou non une chaîne chaîne hamiltoniennehamiltonienne, , il faut procéder par il faut procéder par essai-erreuressai-erreur..
Exemple #1 :Exemple #1 :
BB
CC
EE
DD
FFAA
GG
La chaîne La chaîne ABCDEFG ABCDEFG est une chaîne est une chaîne hamiltoniennehamiltonienne. .
Exemple #2 :Exemple #2 :
Ce graphe ne contient pas de chaîne Ce graphe ne contient pas de chaîne hamiltoniennehamiltonienne. .
AA
EE
CC
DD
BB
B) Cycle B) Cycle HAMILTONIENHAMILTONIEN
Cycle qui passe Cycle qui passe une seule fois une seule fois par tous les par tous les sommets sommets du graphe.du graphe.
Pour savoir si un graphe contient ou non un Pour savoir si un graphe contient ou non un cycle cycle hamiltonienhamiltonien, il faut , il faut procéder par procéder par essai-erreuressai-erreur..
Exemple #1 :Exemple #1 :
Le cycle Le cycle EFADCBE EFADCBE est un cycle est un cycle hamiltonienhamiltonien. .
BB
CC
EE
DD
FFAA
B) Cycle B) Cycle HAMILTONIENHAMILTONIEN
Cycle qui passe Cycle qui passe une seule fois une seule fois par tous les par tous les sommets sommets du graphe.du graphe.
Pour savoir si un graphe contient ou non un Pour savoir si un graphe contient ou non un cycle cycle hamiltonienhamiltonien, il faut , il faut procéder par procéder par essai-erreuressai-erreur..
Exemple #2 :Exemple #2 :
Ce graphe ne contient aucun cycle Ce graphe ne contient aucun cycle hamiltonienhamiltonien. .
BB
CC
EE
DD
FFAA
Mathématiques Mathématiques CSTCST- - GRAPHESGRAPHES : : Composantes et types -Composantes et types -
Nombre CHROMATIQUEC’est le C’est le plus petit nombreplus petit nombre de de couleurscouleurs qu’il est possible d’utiliser qu’il est possible d’utiliser pour colorier les sommets d’un graphe pour colorier les sommets d’un graphe sans que deux sommets sans que deux sommets adjacents soient de même couleuradjacents soient de même couleur..
On utilise le nombre chromatique avec des graphes dont les On utilise le nombre chromatique avec des graphes dont les arêtesarêtes illustrent une situation illustrent une situation d’incompatibilitéd’incompatibilité ou de ou de conflitconflit..
MÉTHODEMÉTHODE : :
1.1. Placer les sommets en ordre Placer les sommets en ordre décroissantdécroissant de degré. de degré.
2.2. Attribuer une Attribuer une 11rere couleur couleur au sommet de plus grand degré.au sommet de plus grand degré.
3.3. Attribuer cette même 1 Attribuer cette même 1rere couleur au sommet suivant s’il ne lui est couleur au sommet suivant s’il ne lui est pas relié, sinon utiliser une pas relié, sinon utiliser une 22ee couleur couleur..
4.4. Répéter l’étape 3 jusqu’à ce que tous les sommets soient coloriés. Répéter l’étape 3 jusqu’à ce que tous les sommets soient coloriés.
Exemple #1 :Exemple #1 : Trouver le Trouver le nombre chromatique nombre chromatique du graphe suivant :du graphe suivant :
BB FF
DD
AA
CC EE
SommetsSommets(en ordre décroissant de degré) :(en ordre décroissant de degré) :
A A (3)(3)
E E (3)(3)
B B (2)(2)
F F (2)(2)
C C (1)(1)
D D (1)(1)
A A (3)(3)
E E (3)(3)
B B (2)(2)
F F (2)(2)
C C (1)(1)
D D (1)(1)
Le Le nombre chromatique nombre chromatique du graphe est du graphe est 33. .
Réponse :Réponse :
Exemple #2 :Exemple #2 : Sébastien veut envoyer un message à tous ses amis par Sébastien veut envoyer un message à tous ses amis par Facebook. Cependant, certains de ses amis sont en conflits Facebook. Cependant, certains de ses amis sont en conflits entre eux et se bloquent l’accès, donc ils ne peuvent voir le entre eux et se bloquent l’accès, donc ils ne peuvent voir le message envoyé à l’autre personne. Le graphe ci-dessous message envoyé à l’autre personne. Le graphe ci-dessous illustre les conflits entre les amis de Sébastien.illustre les conflits entre les amis de Sébastien.
Combien de messages différents doit-il écrire pour rejoindre Combien de messages différents doit-il écrire pour rejoindre tous ses amis ?tous ses amis ?
BB
CC
EE
DD
FFAASommetsSommets(en ordre décroissant de degré) :(en ordre décroissant de degré) :
D D (4)(4)
F F (3)(3)
A A (2)(2)
C C (2)(2)
E E (2)(2)
B B (1)(1)
D D (4)(4)
F F (3)(3)
A A (2)(2)
C C (2)(2)
E E (2)(2)
B B (1)(1)
Exemple #2 :Exemple #2 : Sébastien veux envoyer un message à tous ses amis par Sébastien veux envoyer un message à tous ses amis par Facebook. Cependant, certains de ses amis sont en conflits Facebook. Cependant, certains de ses amis sont en conflits entre eux et se bloquent l’accès, donc il ne peuvent voir le entre eux et se bloquent l’accès, donc il ne peuvent voir le message envoyé à l’autre personne. Le graphe ci-dessous message envoyé à l’autre personne. Le graphe ci-dessous illustre les conflits entre les amis de Sébastien.illustre les conflits entre les amis de Sébastien.
Combien de messages différents doit-il écrire pour rejoindre Combien de messages différents doit-il écrire pour rejoindre tous ses amis ?tous ses amis ?
BB
CC
EE
DD
FFAA
Le Le nombre chromatique nombre chromatique du graphe est du graphe est 33. .
Réponse :Réponse : 33 messages. messages.