Les Graphes (spé)

Question 1

Les points sont

Answer 1

Les sommets du graphe

Question 2

Les lignes sont appelées

Answer 2

Arêtes (ou arc)

Question 3

Une boucle est

Answer 3

Une arête dont les extrémités sont confondues

Question 4

Deux sommets sont adjacents si ..

Answer 4

Ils sont reliés par une arête

Question 5

Un sommet pendant..

Answer 5

N’est relié qu’à un autre point. Il n’a qu’un seul voisin

Question 6

Un sommet isolé

Answer 6

N’est relié à aucun autre

Question 7

Si deux sommets sont reliés par plusieurs arêtes ..

Answer 7

Chacune est une arête multiple

Question 8

Un graphe est complet si..

Answer 8

Deux sommets quelconques sont reliés par une arête

Question 9

L’ordre d’un graphe est égal

Answer 9

Au nombre de sommets

Question 10

Le degré d’un sommet est ..

Answer 10

Le nombre d’arêtes ayant ce sommet pour extrémité

Question 11

Définition graphes et matrice

Answer 11

La matrice associée à un graphe d’ordre n dont les sommets sont numérotés de 1 à n est la matrice carrée d’ordre n où l’intersection de la i-ème ligne et de la j-ème colonne aij est égal au nombre d’arêtes reliant les sommets i et j

Question 12

La somme des degrés de tous les sommets d’un graphe ..

Answer 12

Est égale à deux fois le nombre d’arêtes

Question 13

La somme des degrés de tous les sommets d’un graphe ..

Answer 13

Est toujours un nombre pair

Question 14

Le nombre de sommets de degré impair..

Answer 14

Est un nombre pair

Question 15

Un graphe est connexe si

Answer 15

Deux sommets quelconques sont toujours reliés par une chaîne

Question 16

Un graphes complet est obligatoirement..

Answer 16

Connexe

Question 17

On appelle chaîne eulérienne d’un graphe…

Answer 17

Toute chaîne qui contient une et une seule fois toutes les arêtes du graphe

Question 18

On appelle cycle eulérien..

Answer 18

Une chaîne eulérienne fermée

Question 19

Un graphe admet une chaîne eulérienne si et seulement si

Answer 19

Le nombre de sommets de degré impair est 0 ou 2

Question 20

Une chaîne est

Answer 20

Une suite ordonnée de sommets reliés par des arêtes

Question 21

La longueur d’une chaîne est

Answer 21

Le nombre d’arêtes qui la compose

Question 22

Une chaîne est simple si

Answer 22

Elle n’utilise pas plus d’une fois une même arête

Question 23

Une chaîne est fermée si

Answer 23

L’origine et l’extrémité sont confondues.

Question 24

Une chaîne est élémentaire si

Answer 24

Elle n’utilise pas plus d’une fois le même sommet

Question 25

Une chaîne eulérienne est

Answer 25

Une chaîne contenant toute les arêtes du graphe une et une seule fois

Question 26

Un cycle est

Answer 26

Une chaîne fermée simple

Question 27

Le terme aij à l’intersection de la i-ème ligne et j-ème colonne de la matrice A^k (k entier strictement positif) est..

Answer 27

Le nombre de chaînes de longueur k reliant le sommet I au sommet j

Question 28

Un graphe est ..

Answer 28

Un ensemble de points éventuellement reliés par des lignes