Résolution de problèmes conduisant à la modélisation d'une situation par un graphe orienté ou non, éventuellement étiqueté ou pondéré et dont la solution est associée : au coloriage d'un graphe,
à la recherche du nombre chromatique,
à l'existence d'une chaîne ou d'un cycle eulérien,
à la recherche d'une plus courte chaîne d'un graphe pondéré ou non,
à la caractérisation des mots reconnus par un graphe étiqueté et, réciproquement, à la construction d'un graphe étiqueté reconnaissant une famille de mots.
à la recherche d'un état stable d'un graphe probabiliste à 2 ou 3 sommets.
Vocabulaire élémentaire des graphes : sommets, sommets adjacents, arêtes, degré d'un sommet, ordre d'un graphe, chaîne, longueur d'une chaîne, graphe complet, distance entre deux sommets, diamètre, sous-graphe stable, graphe connexe, nombre chromatique, chaîne eulérienne, matrice associée à un graphe, matrice de transition pour un graphe pondéré par des probabilités.
Résultats élémentaires sur les graphes :
lien entre la somme des degrés des sommets et le nombre d'arêtes d'un graphe ;
conditions d'existence de chaînes et cycles eulériens ;
exemples de convergence pour des graphes probabilistes à deux sommets, pondérés par des probabilités.