Les graphes (cours de Maths - Terminale ES)

Résumé du document

Un graphe est un ensemble de points et de lignes reliant certains de ces points.
Un sommet est un point du graphe. Le nombre de sommets est l'ordre du graphe.
Une arête du graphe est une ligne reliant deux sommets du graphe du graphe. Une boucle est une arête reliant un sommet à lui-même. Deux sommets reliés par une arête sont adjacents (...)

Extraits

[...] La distance entre deux sommets d'un graphe est la longueur de la chaîne qui les relie ayant le moins d'arêtes. Le diamètre d'un graphe connexe est la plus grande distance constatée entrre deux sommets de ce graphe parmi toutes les paires de sommets. Exemples : Graphe Exemples de chaîne : ABCB / ABCFDE . Chaînes de longueur 3 : ABCF / ABCB . Cycle : ABCA Distance entre les différents sommets : Graphe Chaînes de longueur 2 : ABD /ADC . [...]

[...] Une arête du graphe est une ligne reliant deux sommets du graphe du graphe. Une boucle est une arête reliant un sommet à lui-même. Deux sommets reliés par une arête sont adjacents. Le degré d'un sommet est égal au nombre d'extrémités d'arêtes partant ou arrivant à ce sommet. Un sommet est isolé lorsqu'aucune arête ne le relie aux autres sommets. Un graphe simple est un graphe sans boucle tel que, entre deux sommets, il y ait au plus une arête. [...]

[...] Exemples : Dans le graphe la chaîne EDFEBFCBAC est une chaîne eulérienne. Graphe : ADBEDCBA est un cycle eulérien. Théorème d'Euler Un graphe connexe admet une chaîne eulérienne si et seulement si tous ses sommets sont de degré pair sauf au plus deux. Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair. Matrice associée à un graphe On considère un graphe G d'ordre n dont les sommets sont numérotés de 1 à n. [...]

[...] Exemples : Un sous graphe du graphe Définition Le nombre chromatique est le plus petit nombre de couleurs permettant de colorier tous les sommets d'un graphe sans que deux sommets adjacents du graphe soient de la même couleur. Théorème Si un graphe contient un sous graphe complet d'ordre n alors son nombre chromatique est supérieur ou égal à n. Le nombre chromatique d'un graphe est inférieur ou égal à γ + 1 où γ est le plus grand degré des sommets. [...]

[...] Graphe orienté Ce graphe ne contient qu'une seule boucle, de E à E. Théorème La somme des degrés de tous les sommets d'un graphe est égale au double du nombre d'arête. Le graphe comporte 5 arêtes, les degrés des sommets de ce graphe sont : La somme des degrés des sommets est 10. Définitions Un graphe complet est un graphe simple dont tous les sommets sont adjacents les uns avec les autres. Dans ce graphe complet d'ordre le degré de chacun des sommets est n-1. [...]