Modèle de cours

Terminale ES GRAPHES novembre 2005 Graphes 1 Généralités sur les graphes non orientés Un graphe est constitué de sommets, dont certains sont reliés par des arêtes. Deux sommets reliés par une arête sont adjacents. Le nombre de sommets présents dans un graphe est l’ordre du graphe. Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité. Le graphe G1 est d’ordre 6 ; les sommets 1 et 2 sont adjacents, puisque reliés par une arête. Ce n’est pas le cas des sommets 5 et 2. Le degré du sommet 5 est égal à 3. Propriété : La somme des degrés d’un graphe non orienté est égale à deux fois le nombre d’arêtes du graphe. (C’est donc un nombre pair) La matrice associée à un graphe d’ordre n dont les sommets sont numérotés de 1 à n est une ème ème matrice symétrique, de dimension n × n, où le terme à l’intersection de la i ligne et de la jcolonne vaut k, nombre d’arêtes reliant i et j. La matrice 6 × 6 ci-contre est la matrice associée au graphe G1 ; elle ne contient que des 0 et des 1 puisque deux sommets quelconques de ce graphe sont au plus reliés par une arête. C’est d’ailleurs à ce type de graphe que l’on se restreindra le plus souvent. 1 / 8 Terminale ES GRAPHES novembre 2005 Un sous-graphe d’un graphe G est un graphe G’ composé de certains sommets de G, ainsi que de toutes les arêtes de G reliant ces sommets. Le sous-graphe engendré par k sommets est le sous-graphe de G défini par ces k ...