Remerciez-le!

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

Généralités sur les graphes Christophe ROSSIGNOL∗ Année scolaire 2008/2009 Tabl

Généralités sur les graphes Christophe ROSSIGNOL∗ Année scolaire 2008/2009 Table des matières 1 Notion de graphe 3 1.1 Un peu de vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Ordre d’un graphe, degré des sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Graphe simple, graphe complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Matrice associée à un graphe 6 2.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Chaînes d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Théorème d’Euler 8 3.1 Graphe connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Chaîne eulérienne, cycle eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Théorème d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4 Algorithme d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Coloriage des sommets d’un graphe 11 4.1 Notion de sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Algorithme de Welsh-Powell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 Cas d’un graphe complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 ∗Ce cours est placé sous licence Creative Commons BY-SA http://creativecommons.org/licenses/by-sa/2.0/fr/ 1 TABLE DES FIGURES TABLE DES FIGURES Table des ﬁgures 1 Un graphe contenant une boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Un exemple de graphe simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Un autre exemple de graphe simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 Un exemple de graphe non simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 Un graphe orienté simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 Un graphe orienté non simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 7 Graphe orienté contenant une boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8 Le graphe complet d’ordre 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 9 Le graphe complet d’ordre 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 10 Le graphe complet d’ordre 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 11 Matrice associée à un graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 12 Matrice associée à un graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 13 Un graphe connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 14 Un graphe non connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 15 Graphe contenant une chaîne eulérienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 16 Graphe contenant un cycle eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 17 Détermination pratique d’une chaîne eulérienne (1) . . . . . . . . . . . . . . . . . . . . . . . . . . 10 18 Détermination pratique d’une chaîne eulérienne (2) . . . . . . . . . . . . . . . . . . . . . . . . . . 11 19 Un sous-graphe du graphe complet d’ordre 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 20 Pas un sous-graphe du graphe complet d’ordre 4 . . . . . . . . . . . . . . . . . . . . . . . uploads/Marketing/ pdf-generalites-graphes-pdf.pdf