Mathématiques CST - GRAPHES - Composantes et types

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


AA

EE

BB

DD

CC

Chaîne Chaîne : Suite d’arêtes consécutives.: Suite d’arêtes consécutives.

Ex. : Ex. : ADBEADBE


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


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..


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.


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..


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..


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 !


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. .


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..


AA

EE

CC

DD

BB

PairPair

PairPair

PairPair

PairPair

PairPair

Le cycle Le cycle BCEDABBCEDAB est un cycle est un cycle eulérieneulérien. .


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


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..


BB

CC

EE

DD

FFAA

GG

La chaîne La chaîne ABCDEFG ABCDEFG est une chaîne est une chaîne hamiltoniennehamiltonienne. .


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..


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..


Ce graphe ne contient aucun cycle Ce graphe ne contient aucun cycle hamiltonienhamiltonien. .

BB

CC

EE

DD

FFAA


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.

Documents

Mathématiques CST - GRAPHES - Composantes et types