Les graphes

Les graphes sont des structures de données plus générales que les arbres, permettant de représenter des relations complexes entre éléments appelés sommets. Ils sont largement utilisés en informatique et en mathématiques pour modéliser divers problèmes.

Un graphe est composé de sommets (ou nœuds) reliés par des arêtes. Deux sommets reliés par une arête sont dits adjacents ou voisins. Il existe différents types de graphes :

• Graphe orienté : les arêtes ont une direction (représentées par des flèches)
• Graphe pondéré : les arêtes ont des valeurs associées

Définition: Un graphe est une structure composée de sommets et d'arêtes reliant ces sommets. Il permet de représenter des relations entre différents éléments.

Pour représenter un graphe, on peut utiliser :

1. Une matrice d'adjacence : tableau 2D où l'élément (i,j) indique s'il existe une arête entre les sommets i et j.

Exemple: Matrice d'adjacence pour un graphe à 6 sommets :

  A B C D E F
A 0 1 1 0 0 0
B 1 0 1 0 1 1
C 1 1 0 1 0 1
D 0 0 1 0 1 0
E 0 1 0 1 0 1
F 0 1 1 0 1 0

2. Des listes d'adjacence : pour chaque sommet, on liste ses voisins.

Exemple: Listes d'adjacence : A : [B, C] B : [A, C, E] C : [A, B, D, F] D : [C, F] E : [B, F] F : [B, C, D, E]

Quelques concepts importants liés aux graphes :

• Un graphe est complet si tous ses sommets sont reliés deux à deux par une arête.
• Une chaîne est une suite d'arêtes consécutives.
• La longueur d'une chaîne est le nombre d'arêtes qui la composent.
• La distance entre deux sommets est la longueur de la plus courte chaîne les reliant.
• Un cycle est une chaîne fermée qui commence et se termine par le même sommet.

Highlight: La maîtrise des graphes et de leurs représentations est essentielle en NSI Terminale pour résoudre des problèmes complexes d'optimisation et de modélisation.

Les arbres

Les arbres sont des structures de données hiérarchiques composées de nœuds reliés par des arêtes. Ils sont largement utilisés en informatique pour organiser et représenter des données de manière efficace.

Un arbre est constitué d'une racine, de nœuds internes et de feuilles. La racine est le nœud supérieur, les nœuds internes ont des fils, et les feuilles sont les nœuds sans enfants. Les relations entre les nœuds sont de type père-fils.

Vocabulaire:

• Racine : nœud supérieur de l'arbre
• Feuilles : nœuds sans enfants
• Arête : lien entre deux nœuds

Il existe différents types de parcours d'arbre pour explorer sa structure :

• Parcours préfixe : père - fils gauche - fils droit
• Parcours infixe : fils gauche - père - fils droit
• Parcours suffixe : fils gauche - fils droit - père
• Parcours en largeur : par étages

Exemple: Parcours préfixe : 1-D-B-E-K-Z Parcours infixe : B-D-1-K-E-Z

Les arbres binaires sont un type particulier d'arbre où chaque nœud a au maximum deux fils. Un cas spécial est l'arbre binaire de recherche, où les valeurs du sous-arbre gauche sont inférieures au nœud parent, et celles du sous-arbre droit sont supérieures.

Définition: Un arbre binaire de recherche est un arbre binaire où pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à celle du nœud, et toutes les valeurs du sous-arbre droit sont supérieures.

Quelques concepts importants liés aux arbres :

• Taille : nombre total de nœuds
• Hauteur : profondeur du nœud le plus profond
• Profondeur d'un nœud : nombre d'arêtes sur le chemin le plus court vers la racine

Highlight: La compréhension des arbres et de leurs parcours est fondamentale en NSI Terminale pour maîtriser les structures de données avancées.