[PDF] Théorie des graphes
Introduction 1 Chapitre I Premier contact avec les graphes 5 1 Graphes orientés 5 2 Graphes non orientés 8 3 Quelques exemples
[PDF] Introduction à la théorie des graphes - Apprendre-en-lignenet
Comme la théorie des graphes utilise un jargon bien particulier le début du cours comporte beaucoup de définitions C'est un peu rébarbatif
[PDF] Introduction à la théorie des graphes
L'histoire de la théorie des graphes débute peut-être avec les travaux d'Euler au XVIII e siècle et trouve son origine dans l'étude de certains problèmes
[PDF] Théorie des graphes et optimisation dans les graphes - CNRS
Théorie des graphes et optimisation dans les graphes Christine Solnon Table des matières 1 Motivations 3 2 Définitions 4 3 Représentation des graphes
[PDF] Introduction à la théorie des graphes
Ce document est le support du cours introduction `a la théorie des graphes Il présente des notions de base ou plutôt élémentaire sur la théorie des graphes
[PDF] Théorie des graphes DUT Informatique semestre 2
3 fév 2014 · L'ensemble des fiches pdf du cours de théorie des graphes (TD1 `a TD9 et TP1 `a TP9) peut être décrit par l'expression réguli`ere
[PDF] Chapitre 13 Théorie des graphes
Un graphe non orienté est dit connexe s'il y a un chemin entre n'importe quelle paire de sommets Un graphe orienté est dit connexe si en transformant ses arcs
[PDF] Théorie des Graphes - Centre Inria dUniversité Côte dAzur
2 fév 2015 · Malgré ce contenu plus avancé le livre est organisé de telle sorte qu'un cours d'introduction `a la théorie des graphes puisse se baser sur
[PDF] Théorie des graphes Introduction Programme de Terminale ES
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
[PDF] GRAPHE
I 3 Différents modes de représentation d'un graphe Cette théorie va connaitre un essor au cours du XIXème par l'intermédiaire du pro-
GRAPHEMathieu SABLIK
Table des matières
I Différentes notions de graphes
5I.1 Différents problèmes à modéliser
5I.2 Différentes notions de graphes
6I.2.1 Graphe orienté ou non
6I.2.2 Isomorphisme de graphe
8I.2.3 Degré
8 I.2.4 Construction de graphes à partir d"un autre 10 I.3 Différents modes de représentation d"un graphe 10I.3.1 Représentation sagittale
10 I.3.2 Définition par propriété caractéristique 10I.3.3 Listes d"adjacence
11I.3.4 Matrices d"adjacence
11I.3.5 Matrice d"incidence
12I.3.6 Comparaison des différentes méthodes
12I.4 Quelques classes de graphe importantes
12I.4.1 Graphes isolés
12I.4.2 Graphes cycliques
13I.4.3 Graphes complets
13I.4.4 Graphe biparti
13I.4.5 Graphes planaires
13I.4.6 Arbres
14II Problèmes de chemins dans un graphe
15II.1 Notion de chemin
15II.1.1 Définitions
15II.1.2 Longueur d"un chemin
15II.2 Connexité
16 II.3 Graphek-connexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17II.4 Chemin Eulérien et Hamiltoniens
19II.4.1 Chemin Eulérien
19II.4.2 Chemins hamiltonien
21II.5 Caractérisation des graphes bipartis
22TABLE DES MATIÈRES2
III Graphes acycliques ou sans-circuits
25III.1 Notion d"arbres
25III.1.1 Nombre d"arêtes d"un graphe acyclique
25III.1.2 Arbres et forêts
26III.1.3 Arbres orientés
27III.1.4 Notion de rang dans un graphe orienté sans circuit 28
III.2 Initiation à la théorie des jeux
28III.2.1 Jeux combinatoires
28III.2.2 Modélisation
29III.2.3 Noyau d"un graphe
29III.2.4 Exemples de jeux
30III.3 Parcours dans un graphe
32III.3.1 Notion générale
32III.3.2 Parcours en largeur
33III.3.3 Parcours en profondeur
34IV Problèmes de coloriages
37IV.1 Coloriage de sommets
37IV.1.1 Position du problème
37IV.1.2 Exemples d"applications
37IV.1.3 Nombre chromatique de graphes classiques
38IV.2 Résolution algorithmique pour le coloriage de sommets 38
IV.2.1 Algorithme glouton
39IV.2.2 Algorithme de Welsh-Powell
39IV.2.3 Existe t"il un algorithme pour trouver le nombre chromatique d"un graphe? 41
IV.3 Encadrement du nombre chromatique
41IV.4 Coloration des arêtes
43IV.5 Théorie de Ramsey
44V Graphes planaires
47V.1 Généralités
47V.2 Le théorème de Kuratowski
48V.3 Coloration
48V.4 Croisements, épaisseur et genre
50VI Un peu de théorie algébrique des graphes
53VI.1 Matrice d"adjacence et chemin dans un graphe
53VI.1.1 Matrice d"adjacence
53VI.1.2 Nombre de chemin de longueurn. . . . . . . . . . . . . . . . . . . .53 VI.1.3 Distance entre deux sommets et diamètre du graphe 53
VI.2 Théorie de Perron-Frobenius
54VI.3 Deux mots sur le Page-rank
54VIIProblèmes d"optimisation pour des graphes valués 55
VII.1Recherche d"arbre couvrant de poids maximal/minimal 55
VII.1.1 Problème
55VII.1.2 Algorithme de Prim
56VII.1.3 Algorithme de Kruskal
573T abledes Matièr es
VII.2Problème de plus court chemin
58VII.2.1 Position du problème
58VII.2.2 Principe des algorithmes étudiés
59VII.2.3 Algorithme de Bellman-Ford-Kalaba
59VII.2.4 Algorithme de Bellman
61VII.2.5 Algorithme de Dijkstra-Moore
62VII.2.6 Remarques
64VII.2.7 Ordonnancement et gestion de projet
64VII.3Flots dans les transports
65VII.3.1 Position du problème
65VII.3.2 Lemme de la coupe
66VII.3.3 Algorithme de Ford-Fulkerson
67TABLE DESMATIÈRES4
ChapitreIDifférentes notions de graphes
I.1Dif férentsproblèmes à modéliser
On peut considérer que l"article fondateur de la théorie des graphe fut publié par le mathématicien suisse Leonhard Euler en 1741. Il traitait du problème des sept ponts de d"un point donné et revenant à ce point en passant une et une seule fois par chacun des sept ponts de la ville? Cette théorie va connaitre un essor au cours duXIXèmepar l"intermédiaire du pro- blème suivant : quel est le nombre minimal de couleurs nécessaires pour colorier une carte géographique de telle sorte que deux régions limitrophe n"ont pas la même cou- leur? Le théorème des quatre couleurs affirme que seulement quatre sont nécessaires. Lerésultat fut conjecturé en 1852 par Francis Guthrie, intéressé par la coloration de la carte
des régions d"Angleterre, mais ne fût démontré qu"en 1976 par deux Américains Kenneth Appel et Wolfgang Haken. Ce fut la première fois que l"utilisation d"un ordinateur a per- mis de conclure leur démonstration en étudiant les 1478 cas particulier auxquels ils ont ramené le problème. AuXXèmesiècle, la théorie des graphes va connaître un essor croissant avec le déve- de manière non exhaustive : réseaux de transports r outier,d"eau, d"électricité : les sommets r eprésententles car - refours et les arêtes les rues; réseaux informatiques : les sommets r eprésententles or dinateurset les arêtes les connexions physiques; réseaux sociaux : les sommets r eprésententles membr esdu gr oupe,deux per - sonnes sont reliées par une arête si elles se connaissent (Facebook : graphe non graphe du web : les sommets r eprésententles pages web et chaque ar ccorr espond a un hyperliens d"une page vers une autre; réseau de transports de données (téléphonie, wifi, réseaux informatique. ..); r eprésentationd"un algorithme, du dér oulementd"un jeu ; réseaux de régulation génétique ;Chapitre I. DIFFÉRENTES NOTIONS DE GRAPHES6-or ganisationlogistique : les sommets r eprésententdes évènements, deux évène-
ments sont reliées par une arête s"ils ne peuvent pas avoir lieu en même temps; or donnancementde pr ojet: les sommets r eprésententles dif férentestâches com- posant un projet, deux tâches sont reliés par une flèche si la deuxième ne peut pas commencer avant que la première soit terminée; et beaucoup d"autr esencor e... L"étude des graphes se réalise sous deux point de vues complémentaire. L"étude de propriétés structurelles de graphes ou de familles de graphes et l"étude algorithmique de certaines propriétés. I.2Dif férentesnotions de graphes
I.2.1Graphe orienté ou non
Dans les exemples que l"on a vus, un graphe est un ensemble fini de sommets reliéspar des arêtes. Ces arêtes peuvent être orientées ou non, de plus une valeur peut être
associée à chaque arête ou aux sommets. Définition I.1.Ungraphe orienté G= (S,A)est la donnée : d"un ensemble Sdont les éléments sont des sommets; d"un ensemble ASSdont les éléments sont les arcs. Un arca= (s,s0)est aussi notés!s0,sest l"originedeaets0l"extrémité. On dit aussi ques0est lesuccesseurdesetsleprédécesseurdes0. On peut souhaiter qu"il y ait plusieurs arcs entre deux mêmes sommets. On parle alors de graphe orientémulti-arcs. Formellement,G= (S,A,i,f)c"est la donnée : d"un ensemble Sdont les éléments sont des sommets; d"un ensemble Adont les éléments sont les arcs; de deux fonctions i:A!Setf:A!Squi à chaque arcsa2Aassocie son prédécesseuri(a)et son successeurf(a).ExempleI.1.Exemple de graphe orienté :12
43G= (S,A)où
-S=f1,2,3,4g, -A=f(1,2),(2,1),(2,4),(3,4),(3,3)g.Exemple de graphe orienté multi-arcs :12
43ab dc ef gG= (S,A,i,f)où -S=f1,2,3,4g, -A=fa,b,c,d,e,f,g,hg, -i:a7!1 b7!2 c7!2 d7!2 e7!3 f7!3 g7!3etf:a7!2 b7!1 c7!4 d7!4 e7!4 f7!3 g7!3. Définition I.2.Ungraphe non orienté G= (S,A)est la donnée :
7I.2. Dif férentesnotions de graphes
d"un ensemble Sdont les éléments sont les sommets du graphe, d"un ensemble Adont les éléments, les arêtes du graphe, sont des parties à un ou deux éléments deS. seule extrémité sont des boucles. On peut de la même façon un graphe non-orientémulti-arêtes. Formellement,G= (S,A,a)est la donnée : d"un ensemble Sdont les éléments sont des sommets; d"un ensemble Adont les éléments sont les arêtes; d"une fonction adeAdans les parties à un ou deux éléments deS.ExempleI.2.Exemple de graphe non-orienté :12
43G= (S,A)où
-S=f1,2,3,4g, -A=ff1,2g,f2,4g,f3,4g,f3gg. Exemple de graphe non orienté multi-arêtes :12 43ab dc ef gG= (S,A,a)où -S=f1,2,3,4g, -A=fa,b,c,d,e,f,g,hg, -a:a7! f1,2g b7! f1,2g c7! f2,4g d7! f2,4g e7! f3,4g f7! f3g g7! f3g.
Si un arc ou une arête à ses deux extrémités constituées du même sommet, on dit que
c"est uneboucle. Un graphe estsimples"il est non-orienté, s"il a au plus une arête entre deux sommets et s"il n"a pas de boucle. L"ordred"un graphe est le nombre de sommetsjSjet latailled"un graphe est le nombre d"arêtes ou d"arcs. On appèlevaluationsur les sommets (resp. sur les arcs ou arêtes) toutes fonctions pre-nant en argument les sommets (resp. sur les arcs ou arêtes) et renvoyant un réels ou élé-
ment dans un ensemble donné. SoitG= (S,A)un graphe orienté, on associe le graphe non orientéG0= (S,A0)ayant le même ensemble de sommetsSet dont l"ensemble d"arêtesA0vérifiefx,yg 2A0() (x,y)2Aou(y,x)2A. ExempleI.3.Les trois graphes suivantssont associés au graphe non orienté suivant Chapitre I. DIFFÉRENTES NOTIONS DE GRAPHES8I.2.2Isomorphisme de graphe Deux graphes orientésG= (S,A)etG0= (S0,A0)sontisomorphess"il existe une appli- L"applicationjest alors unisomorphisme de graphes orientés. ExempleI.4.Les deux graphes suivants sont isomorphes par l"isomorphismej: 17!A,27!B,37!C,47!D,57!E.12
3 4 5AD B E C De même, deux graphes non-orientésG= (S,A)etG0= (S0,A0)sontisomorphess"il existe une application bijectivej:S!S0telle que pour touts,s02Sonfs,s0g 2A() fj(s),j(s0)g 2A. L"applicationjest alors unisomorphisme de graphes non-orientés. I.2.3Degré
Pour un graphe orienté, on appèledegré entrantd"un sommets, notéd(s)(resp.degré sortantd"un sommets, notéd+(s)) le nombre d"arcs dont le sommet est successeur (resp. prédécesseur). Pour un graphe non-orienté, on appelledegréd"un sommets, notéd(s)le nombre d"arêtes dont le sommet est une extrémité.Théorème I.1 Lemme de la poignée de mainSoitG= (S,A)un graphe orienté. On alors les égalités suivantes :
X s2Sd +(s) =X s2Sd (s) =jAj. SoitG= (S,A)un graphe non-orienté. On a alors l"égalité suivante : Xs2Sd(s) =2jAj.Démonstration:Pour un graphe orientéG= (S,A), chaque arc a un successeur et un prédé-
cesseur d"ou la première égalité.Pour obtenir la deuxième égalité, il suffit d"orienté le graphe non-orienté et remarquer
que pour chaque sommetd(s) =d+(s) +d(s).Une conséquence directe de ce théorème est que dans un graphe, le nombre de som-
mets dont le degré est impair est toujours pair. Corollaire I.2Dans un graphe non orienté, le nombre de sommets dont le degré est impair est toujours pair.9I.2. Dif férentesnotions de graphes
Démonstration:SoitG= (S,A)un graphe non orienté, on noteS1l"ensemble des sommets impairs etS2l"ensemble des sommets pairs. Par le lemme de la poignée de main, on a X s2S1d(s) +X s2S2d(s) =2jAj. Ainsi P s2S1d(s)doit être pair. Comme chaqued(s)est impair pours2S1, on en séduitquejS1jest pairSoitG= (S,A)un graphe simple non orienté défini à partir de l"ensemble de som-
metS=fv1,...,vng. On noted(vi)le degré devi. Lasuite des degrésdeGest la suitequotesdbs_dbs50.pdfusesText_50[PDF] cours thermodynamique statistique mp
[PDF] cours tourisme gratuit
[PDF] cours transaction immobilière
[PDF] cours transaction immobilière bts pi
[PDF] cours transfert thermique pdf
[PDF] cours transport routier pdf
[PDF] cours trigonométrie pdf
[PDF] cours trigonométrie première s
[PDF] cours tva maroc pdf
[PDF] cours typologie des textes narratifs s1 pdf
[PDF] cours ue4 paces pdf
[PDF] cours vanne
[PDF] cours vba excel 2013 pdf
[PDF] cours vecteurs 1ere s pdf