Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Pdf generalites graphes pdf

Généralités sur les graphes Christophe ROSSIGNOL ? Année scolaire Table des matières Notion de graphe Un peu de vocabulaire Ordre d ? un graphe degré des sommets Graphe simple graphe complet Matrice associée à un graphe Dé ?nitions Cha? nes d ? un graphe Théorème d ? Euler Graphe connexe Cha? ne eulérienne cycle eulérien Théorème d ? Euler Algorithme d ? Euler Coloriage des sommets d ? un graphe Notion de sous-graphe Nombre chromatique Algorithme de Welsh-Powell Cas d ? un graphe complet ? Ce cours est placé sous licence Creative Commons BY-SA http creativecommons org licenses by-sa fr CTABLE DES FIGURES TABLE DES FIGURES Table des ?gures Un graphe contenant une boucle Un exemple de graphe simple Un autre exemple de graphe simple Un exemple de graphe non simple Un graphe orienté simple Un graphe orienté non simple Graphe orienté contenant une boucle Le graphe complet d ? ordre Le graphe complet d ? ordre Le graphe complet d ? ordre Matrice associée à un graphe non orienté Matrice associée à un graphe orienté Un graphe connexe Un graphe non connexe Graphe contenant une cha? ne eulérienne Graphe contenant un cycle eulérien Détermination pratique d ? une cha? ne eulérienne Détermination pratique d ? une cha? ne eulérienne Un sous-graphe du graphe complet d ? ordre Pas un sous-graphe du graphe complet d ? ordre Coloriage d ? un graphe C NOTION DE GRAPHE En préliminaire Exercice A et B page Déclic Activité Vocabulaire les graphes Des schémas Notion de graphe Un peu de vocabulaire ?? Un graphe est un schéma constitué de sommets dont certains sont reliés par des arêtes ?? Un graphe orienté est un graphe dont les arêtes sont orientées échées On distingue alors le sommet origine de l ? arête et son extrémité ?? Deux sommets reliés par au moins une arête sont dits adjacents ?? Une arête partant et arrivant au même sommet est appelée boucle Ordre d ? un graphe degré des sommets Activité Vocabulaire sur les graphes Graphe non orienté Dé ?nitions ?? L ? ordre d ? un graphe est le nombre de sommets de ce graphe ?? Dans un graphe le degré de chaque sommet est le nombre d ? arêtes dont il est l ? une des extrémités Remarque Attention Il ne faut pas oublier de compter deux fois les boucles car le sommet est deux fois l ? extrémité de cette arête Exemple Dans le graphe de la ?gure le degré du sommet A est Fig ?? Un graphe contenant une boucle Propriété La somme des degrés de tous les sommets d ? un graphe est égal au double du nombre total d ? arêtes de ce graphe En particulier c ? est un nombre pair Remarque Pour une idée de la démonstration de cette propriété voir l ? activité de la feuille polycopiée Graphe simple graphe complet Dé ?nition On ne considère que des graphes non orientés Un graphe simple est un graphe sans boucle dont