SNT – Les Graphes

Cartes de révision de vocabulaire et notions clés sur le cours SNT portant sur la théorie des graphes et leurs mesures.

Graphe

Ensemble de sommets et d'arêtes.

Sommet

Représente une personne dans un réseau social.

Arête

Représente un lien d'amitié entre deux personnes.

Voisins

Deux sommets reliés par une arête.

Degré d'un sommet

Nombre d'arêtes reliées à ce sommet, donc son nombre d'amis.

Distance

Nombre minimum d'arêtes pour aller d'un sommet à un autre.

Écartement (ou excentricité)

Distance maximale entre un sommet et les autres sommets.

Diamètre

Distance maximale entre deux sommets du graphe, c'est-à-dire le plus grand écartement.

Centre

Ensemble des sommets dont l'écartement est minimal.

Rayon

Écartement des sommets du centre, c'est-à-dire le plus petit écartement.

Matrice d'adjacence

Tableau de 1 (amis) et de 0 (pas amis) qui indique quels sommets sont reliés.

Propriétés de la matrice d'adjacence

Elle est symétrique, sa diagonale ne contient que des 0 et la somme d'une ligne donne le degré du sommet.

Propriété de la somme des degrés

$$\text{Somme des degrés} = 2 \times \text{nombre d'arêtes}$$