Chapitre 3-les Graphes (Math)

Question 1

Definition du mot: graphe

Answer 1

Représentation comprenant un ensemble de points appelés «SOMMETS» et un ensemble de liens appelés «ARÊTES» reliant, ou pas, ces sommets.

Question 2

Identifiés par une lettre majuscules, un nombre ou un mot.

Answer 2

Sommets

Question 3

Nommées à l’aide des lettres qui identifient ses extrémités dans n’importe quel ordre.

Answer 3

Arêtes

Question 4

Ordre d’un graphe

Answer 4

Nombre de sommets

Question 5

Nombre d’arêtes qui touchent

Answer 5

Degré d’un sommet

Question 6

Sommets adjacents

Answer 6

Reliés par un même arête

Question 7

Relient les même sommets

Answer 7

Arêtes parallèles

Ex: d(1) & d(2)

Question 8

Boucle

Answer 8

Compter 2 fois cette arête pour établir le degré de ce sommet

Ex: C-C

Question 9

Graphe connexe

Un seul morceau

Answer 9

N’importe quel sommet est relié, directement ou non, à n’importe quel autre sommet du graphe.

Question 10

Chaque sommet est relié directement à tous les autres sommets

Answer 10

Graphe complet

Question 11

Il ne comporte aucune arrête

Answer 11

Graphe discret

Ex: les point tous seul là là jajaja

Question 12

Graphes équivalents

Answer 12

Leurs arêtes relient les mêmes sommets dans chacun des graphes

Question 13

Lorsqu’on passe d’un sommet à un autre en suivant des arêtes

Answer 13

Chaîne

Question 14

Longueur

Answer 14

Nombre de fois que l’on passe d’un sommet à un autre (nb. D’arêtes)

Question 15

Longueur de la chaîne la plus courte aui relie ces 2 sommets

D(A,B)

Answer 15

Distance entre 2 sommets

Question 16

Une chaîne qui commence et se termine au même sommet

Answer 16

Cycle

Question 17

Chaîne simple

Answer 17

Chaîne dans laquelle chaque arête est utilisée une seule fois

(Pas de répétition d’arêtes)

Question 18

Cycle dans lequel chaque arête est utilisée une seule fois

Pas de répétition d’arêtes

Answer 18

Cycle simple

Question 19

Chaîne eulérienne

Answer 19

Chaîne qui emprunte une seule fois toutes les arêtes d’un graphe connexe

Question 20

Chaîne eulérienne qui commence et se termine en un même sommet

Answer 20

Cycle eulérien

Question 21

Chaîne simple qui emprunte une seule fois tous les sommets d’un graphe connexe

Answer 21

Chaîne hamiltonienne

Question 22

Cycle hamiltonien

Answer 22

Cycle simple qui emprunte une seule fois tous les sommets d’un graphe connexe.

Question 23

Graphe connexe qui ne comporte aucun cycle simple

Answer 23

Aucune boucle = arbre

Question 24

Arbre de valeurs minimales/maximales

Answer 24

On cherche à minimiser ou maximiser les coûts, les distances, etc.