Chapitre 2

Math 11 A

4.1 (Module A2)

Les graphes

ESN 2017-2018

A2: Initiation aux graphs

Dcouvre: Initiation aux graphes

Un graphe est une forme de rseau.

Le mtro de Montral est compos de 4 lignes et de 68 stations. Une couleur spcifique est associe chaque ligne: orange, bleu, vert et jaune. Au cours dun dplacement, il est possible de changer de ligne aux stations de correspondance. On prsente ci-dessous la carte du mtro de Montral.

Questions

1. Je suis la station Outremont. Quelle ligne dois-je prendre pour me rendre la station Acadie?

2. Je suis la station Universit de Montral. Dcrivez comment je peux me rendre la station Place-Saint-Henri

3. Je suis la station Assomption. Dcrivez comment je peux me rendre la station Fabre.

4. Est-ce quil y a toujours un seul moyen de voyager dune station lautre?

A2: Les caractristiques dun graphe

Notes de cours

Dfinition: Un graphe correspond un ensemble dlments et un ensemble de liens entre ces lments.

Dans la reprsentation graphique dun graphe:

Les points dun graphe sont appels des sommets;

Les lignes dun graphe sont appeles des artes ;

Les sommets dun graphe sont identifis par une lettre majuscule, une lettre minuscule, un nombre ou un mot ;

Les artes sont identifies par des lettres chaque bout de larte.

Explication laide de dessins.

Voici diffrentes caractristiques qui peuvent tre associes un graphe:

lordre dun graphe est le nombre de sommets du graphe ;

le degr dun sommet correspond au nombre de ligne (artes) qui touche le sommet ;

deux sommets relis par une mme arte sont adjacents ;

des artes qui relient les mmes sommets sont des artes parallles, nots par un nombre entre parenthses ;

une arte qui relie un sommet lui-mme est appele boucle.

Explication laide de dessins.

Un graphe est connexe si nimporte quel sommet est reli, directement ou non, nimporte quel autre sommet.

Un graphe est complet lorsque chaque sommet est reli directement tous les autres sommets.

Exercices 1

A2: Les chanes et les cycles

Notes de cours

Dans un graphe, on tablit une chane lorsquon passe dun sommet un autre en suivant des artes.

La longueur dune chane correspond au nombre de fois que lon passe dun sommet un autre.

La distance entre deux sommets A et B, note d(A, B), correspond la longueur de la chane la plus courte qui relie ces deux sommets.

Dans un graphe, un cycle est une chane qui commence et se termine au mme sommet.

Chane simple et cycle simple

Une chane est dite simple sil ny a pas de rptition dartes.

Un cycle est dit simple sil n y a pas de rptition dartes.

Exercice 2

Chaine eulrienne et cycle eulrien (Artes)

Une chane eulrienne est une chane qui emprunte toutes les artes dun graphe connexe sans rpter darte.

Un cycle eulrien est une chane eulrienne qui commence et se termine en un mme sommet.

Dans un graphe, une chane eulrienne existe :

si tous ses sommets sont de degr pair. Cette chane commence nimporte quel sommet et se termine ce mme sommet. Il sagit dun cycle eulrien.

sil y a exactement 2 sommets de degr impair. Cette chane nest pas un cycle eulrien, mais elle commence un sommet de degr impair et se termine lautre sommet de degr impair.

Chane hamiltonienne et cycle hamiltonien (Sommets)

Une chane hamiltonienne est une chane simple qui emprunte une seule fois tous les sommets dun graphe connexe.

Un cycle hamiltonien est un cycle simple qui emprunte une seule fois tous les sommets dun graphe connexe.

Exercices 3

Module A2 (30311A)Les graphes10