[PDF] GRAPHE - Institut de Mathématiques de Toulouse PDF GrapheNotes.pdf

degré sortant d'un sommet s, noté d+(s)) le nombre d'arcs dont le sommet est prédécesseur (resp successeur) Pour un graphe non-orienté, on appelle degré d'

Second point à observer : les énoncés donnés sur les entiers l'ont été sur des en- et est donc un polynôme B du deuxième degré à coefficients réels Si on est distrait, des Babyloniens qui, 4000 ans plus tôt, avaient appris à compléter le carré comme nous Lorsque les Français saccagent la ville de Brescia en 1512

[PDF] echerch e Expression de la dérivée dun polynôme en - CORE

Mots clés : Polynôme, Dérivée, Distribution de Wigner-Ville Abstrac t polynomials of degree < N This representation allows to express 1(t) in term s of t , to, , tN and Lemme 2 : Soient t0 , , tQ des réels arbitraires, distincts deux à deux et tk dans la matrice du système (12) est identique à celle du second membre

[PDF] Pratique de la Régression Linéaire Multiple - Université Lumière

4 10 Codage polynomial orthogonal d'une exogène qualitative ordinale Sous H0, la statistique T suit une loi du χ2 à 2 degrés de liberté servation a participé à la construction du modèle de prédiction, dans le second, non on ajoute une variable si le carré du t de Student (qui suit une loi de Fisher) indique que le

[PDF] Entre la Terminale et les CPGE scientifiques - Lycée Victor Grignard

4 Inégalités, trinôme du second degré réel 38 Exercice 56 (F) a) Quels sont les nombres complexes dont le carré est un nombre réel ? b) Quels C'est le « problème de Bâle », ainsi nommé en hommage à la ville de Bernoulli Comment

[PDF] ALGORITHMIQUE

Equation du second degré Page 27 Variables : xA, yA, xB, yB, xC, yC, S, H : réels Début Un point M se déplace sur les côtés du carré en partant de O et en suivant le chemin O On note d la Exercice de bac n°4 Polynésie juin 2012

[PDF] Exercices de mathématiques pour la classe terminale - Toutatice

Soit un nombre réel compris entre 0 et 1 ; on note le point de S - Polynésie, exercice 4 - Énoncé originel augmenté de 50 euros par mètre carré peint Les autorités de santé d'une grande ville s'intéressent aux enfants et aux fonctions polynomiales du second degré et à la dérivation, tout en valorisant

[PDF] Fiches Xcas

Pour les nombres réels approchés, la préci- donnant le nombre de décimales désiré comme second argument de evalf, par et cacher le carré jaune en haut à droite qui donne la position de la tortue 6 Dans une ville les lignes de bus vont : de On montre qu'il existe un polynôme P unique de degré inférieur ou égal

[PDF] La suite logistique et le chaos - Département de Mathématiques d

7 3 Conjugaison des fonctions du second degré 64 o`u pn est la population de la ville `a l'année n, qn le nombre de naissances de cette même réels donne des résultats plausibles : c'est l'ordre de grandeur de la population pensant que c'est un carré pour la valeur limite de a), on a (Df3(xi))2 = 64Q3,a(0)

[PDF] Activités mathématiques dans le contexte de lhôtellerie-restauration

premier degré, reconnaître des situations de proportionnalité, utiliser dans travail mené en classe et la rencontre avec le réel ont été ici des modalités éléments, le second modèle (plus proche de la situation réelle et amenant à un problème On note la longueur du côté du carré et la hauteur de la pyramide

[PDF] GRAPHE - Institut de Mathématiques de Toulouse

degré sortant d'un sommet s, noté d+(s)) le nombre d'arcs dont le sommet est prédécesseur (resp successeur) Pour un graphe non-orienté, on appelle degré d'

[PDF] la ville carrée correction

[PDF] la ville carrée probleme solution

[PDF] La ville carrefour et lieu d'échange

[PDF] la ville dans la littérature contemporaine

[PDF] la ville dans le roman

[PDF] la ville dans le roman policier

[PDF] la ville de bonvivre possede une plaine de jeux

[PDF] la ville de demain 6e eduscol

[PDF] la ville de demain 6e evaluation

[PDF] la ville de demain la ville durable du futur

[PDF] La ville de Glanum

[PDF] la ville de londres et ses monuments les plus connus

[PDF] la ville de MIAMI

[PDF] La ville de New york

[PDF] La ville de Rome au VI e siècle avant J-C

GRAPHEMathieu SABLIK

Table des matières

I Différentes notions de graphes

I.1 Différents problèmes à modéliser

I.2 Différentes notions de graphes

I.2.1 Graphe orienté ou non

I.2.2 Isomorphisme de graphe

I.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 10

I.3.1 Représentation sagittale

10 I.3.2 Définition par propriété caractéristique 10

I.3.3 Listes d"adjacence

I.3.4 Matrices d"adjacence

I.3.5 Matrice d"incidence

I.3.6 Comparaison des différentes méthodes

I.4 Quelques classes de graphe importantes

I.4.1 Graphes isolés

I.4.2 Graphes cycliques

I.4.3 Graphes complets

I.4.4 Graphe biparti

I.4.5 Graphes planaires

I.4.6 Arbres

II Problèmes de chemins dans un graphe

II.1 Notion de chemin

II.1.1 Définitions

II.1.2 Longueur d"un chemin

II.2 Connexité

16 II.3 Graphek-connexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

II.4 Chemin Eulérien et Hamiltoniens

II.4.1 Chemin Eulérien

II.4.2 Chemins hamiltonien

II.5 Caractérisation des graphes bipartis

TABLE DES MATIÈRES2

III Graphes acycliques ou sans-circuits

III.1 Notion d"arbres

III.1.1 Nombre d"arêtes d"un graphe acyclique

III.1.2 Arbres et forêts

III.1.3 Arbres orientés

27
III.1.4 Notion de rang dans un graphe orienté sans circuit 28

III.2 Initiation à la théorie des jeux

III.2.1 Jeux combinatoires

III.2.2 Modélisation

III.2.3 Noyau d"un graphe

III.2.4 Exemples de jeux

III.3 Parcours dans un graphe

III.3.1 Notion générale

III.3.2 Parcours en largeur

III.3.3 Parcours en profondeur

IV Problèmes de coloriages

IV.1 Coloriage de sommets

IV.1.1 Position du problème

IV.1.2 Exemples d"applications

IV.1.3 Nombre chromatique de graphes classiques

38
IV.2 Résolution algorithmique pour le coloriage de sommets 38

IV.2.1 Algorithme glouton

IV.2.2 Algorithme de Welsh-Powell

39
IV.2.3 Existe t"il un algorithme pour trouver le nombre chromatique d"un graphe? 41

IV.3 Encadrement du nombre chromatique

IV.4 Coloration des arêtes

IV.5 Théorie de Ramsey

V Graphes planaires

V.1 Généralités

V.2 Le théorème de Kuratowski

V.3 Coloration

V.4 Croisements, épaisseur et genre

VI Un peu de théorie algébrique des graphes

VI.1 Matrice d"adjacence et chemin dans un graphe

VI.1.1 Matrice d"adjacence

53
VI.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

VI.3 Deux mots sur le Page-rank

54
VIIProblèmes d"optimisation pour des graphes valués 55
VII.1Recherche d"arbre couvrant de poids maximal/minimal 55

VII.1.1 Problème

VII.1.2 Algorithme de Prim

VII.1.3 Algorithme de Kruskal

3T abledes Matièr es

VII.2Problème de plus court chemin

VII.2.1 Position du problème

VII.2.2 Principe des algorithmes étudiés

VII.2.3 Algorithme de Bellman-Ford-Kalaba

VII.2.4 Algorithme de Bellman

VII.2.5 Algorithme de Dijkstra-Moore

VII.2.6 Remarques

VII.2.7 Ordonnancement et gestion de projet

VII.3Flots dans les transports

VII.3.1 Position du problème

VII.3.2 Lemme de la coupe

VII.3.3 Algorithme de Ford-Fulkerson

TABLE DESMATIÈRES4

ChapitreIDifférentes notions de graphes

I.1

Dif 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. Le

ré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.2

Dif férentesnotions de graphes

I.2.1

Graphe orienté ou non

Dans les exemples que l"on a vus, un graphe est un ensemble fini de sommets reliés

par 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

43a
b 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!4quotesdbs_dbs46.pdfusesText_46

[PDF] [PDF] GRAPHE - Institut de Mathématiques de Toulouse