Cours de Théorie des Graphes








télécharger 0.56 Mb.
titreCours de Théorie des Graphes
page1/10
date de publication21.05.2017
taille0.56 Mb.
typeCours
b.21-bal.com > documents > Cours
  1   2   3   4   5   6   7   8   9   10
Collection Faire le Bonheur® vous propose

version exclusive et limité !!!





Cours de Théorie des Graphes
v 1. 0




* Graphes orientés.
* Graphes non orientés.


- Une organisation bien conçus pour la simplicité et la lucidité .

- Des exemples illustrés pour se débarrasser de la forme sèche du cours.

- Et pour la pratique un peut d'exos corrigés pour fluidité.


«  J’aprend bien mes cours …et si je trouve une amalgame je dit laisse tomber....quant a l’organisation et aux exemples …je pense que c’est facile mais ….. si faire le bonheur alors je sens et je crois que c’est seulement faire avaler !!!  » . Notre objectif -l’éditeur- .
D'après le web
Soutenus et réalisé par : Seif ‚ charaf ©

Graphes non orientés

Un graphe fini G = (V, E) est défini par l'ensemble fini V = {v1, v2, ..., vn} (|V| = n) dont les éléments sont appelés sommets, et par l'ensemble fini E = {e1, e2, ..., em} (|E| = m) dont les éléments sont appelés arêtes.
Une arête e de l'ensemble E est définie par une paire non-ordonnée de sommets, appelés les extrémités de e. Si l'arête e relie les sommets a et b, on dira que ces sommets sont adjacents, ou incidents avec e, ou encore que l'arête e est incidente avec les sommets a et b.
On appelle ordre d'un graphe le nombre de sommets (n) de ce graphe.

Représentation graphique

Les graphes tiennent leur nom du fait qu'on peut les représenter par des dessins. À chaque sommet de G, on fait correspondre un point distinct du plan et on relie par une courbe simple les points correspondant aux extrémités de chaque arête.

Exemple

Il existe une infinité de manières de représenter graphiquement un graphe. Vous voyez ci-contre deux représentations graphiques du même graphe G=(V,E) décrit ci-dessous par l'ensemble de ses sommets et l'ensemble de ses arêtes.

Ensemble des sommets:

V = {1, 2, 3, 4, 5}

Ensemble des arêtes:

E = {(1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5), (4, 5)}


Une représentation non planaire de G


Une représentation planaire de G

Quelques types de graphes

Si on arrive à dessiner le graphe sans qu'aucune arête n'en coupe une autre (les arêtes ne sont pas forcément rectilignes), on dit que le graphe est planaire.

Les graphes ci-dessus sont simples, mais on peut imaginer des graphes avec une arête qui relie un sommet à lui-même (une boucle), ou plusieurs arêtes reliant les deux mêmes sommets (voir ci-dessous, à gauche). Dans ce cas, on parle de multigraphe.

Un graphe est connexe s'il est possible, à partir de n'importe quel sommet, de rejoindre tous les autres en suivant les arêtes. Un graphe non connexe se décompose en composantes connexes. Sur le graphe ci-dessous, au milieu, les composantes connexes sont {1, 2, 3, 4} et {5, 6}.


Graphe non simple (multigraphe)

V = {1, 2, 3, 4}
E = {(1,1), (1,3), (1,4), (2,3), (2,3), (3,4)}





Graphe non connexe

V = {1, 2, 3, 4, 5, 6}
E = {(1,3), (1,4), (2,3), (3,4), (5,6)}





Graphe complet K5

V = {1, 2, 3, 4, 5}
E = {(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}





Graphe biparti

V = {1, 2, 3, 4, 5}
E = {(1,2), (1,4), (2,3), (2,5), (3,4), (4,5)}

Un graphe est complet si chaque sommet du graphe est relié directement à tous les autres sommets (voir ci-dessus).

Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y (dans l'exemple ci-dessus, à droite, on a X={1, 3, 5} et Y={2, 4}, ou vice versa).



Exercices

Exercice 1

On a 6 wagons à trier. Dans la gare de triage, les wagons entrent dans l'ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l'ordre croissant. Deux wagons i et j peuvent être mis sur la même voie si et seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir.
Dessinez un graphe illustrant la situation, en indiquant ce que représentent les sommets et les arêtes de votre graphe.
Quel sera le nombre minimal de voies nécessaires au tri?

Exercice 2

Trois professeurs P1, P2, P3 doivent donner ce lundi un certain nombre d'heures de cours à trois classes C1, C2, C3:
- P1 doit donner deux heures de cours à C1 et une heure à C2.
- P2 doit donner une heure de cours à C1, une heure à C2 et une heure à C3;
- P3 doit donner une heure de cours à C1, une heure à C2 et deux heures à C3.
Comment représenter cette situation par un graphe?
Quel type de graphe obtenez-vous?
Combien faudra-t-il de plages horaires au minimum?
Aidez-vous du graphe pour proposer un horaire du lundi pour ces professeurs.

Exercice 3

Un tournoi d'échecs oppose 6 personnes. Chaque joueur doit affronter tous les autres.
Construisez un graphe représentant toutes les parties possibles.
Quel type de graphe obtenez-vous?
Si chaque joueur ne joue qu'un match par jour, combien de jours faudra-t-il pour terminer le tournoi?
Aidez-vous du graphe pour proposer un calendrier des matches.

Exercice 4






Sur un échiquier 3x3, les deux cavaliers noirs sont placés sur les cases a1 et c1, les deux cavaliers blancs occupant les cases a3 et c3.
Aidez-vous d'un graphe pour déterminer les mouvements qui permettront aux cavaliers blancs de prendre les places des cavaliers noirs, et vice versa.

Exercice 5

  Un jour, Sherlock Holmes reçoit la visite de son ami Watson que l'on avait chargé d'enquêter sur un assassinat mystérieux datant de plus de trois ans.

  À l'époque, le Duc de Densmore avait été tué par l'explosion d'une bombe, qui avait entièrement détruit le château de Densmore où il s'était retiré. Les journaux d'alors relataient que le testament, détruit lui aussi dans l'explosion, avait tout pour déplaire à l'une de ses sept ex-épouses. Or, avant de mourir, le Duc les avait toutes invitées à passer quelques jours dans sa retraite écossaise.
  - Holmes: Je me souviens de cette affaire; ce qui est étrange, c'est que la bombe avait été fabriquée spécialement pour être cachée dans l'armure de la chambre à coucher, ce qui suppose que l'assassin a nécessairement effectué plusieurs visites au château!
  - Watson: Certes, et pour cette raison, j'ai interrogé chacune des femmes: Ann, Betty, Charlotte, Edith, Félicia, Georgia et Helen. Elles ont toutes juré qu'elles n'avaient été au château de Densmore qu'une seule fois dans leur vie.
  - Holmes: Hum! Leur avez-vous demandé à quelle période elles ont eu leur séjour respectif?
  - Watson: Hélas! Aucune ne se rappelait les dates exactes, après plus de trois ans! Néanmoins, je leur ai demandé qui elles avaient rencontré:

  • Ann a rencontré Betty, Charlotte, Félicia et Georgia.

  • Betty a rencontré Ann, Charlotte, Edith, Félicia et Helen.

  • Charlotte a rencontré Ann, Betty et Edith.

  • Edith a rencontré Betty, Charlotte et Félicia.

  • Félicia a rencontré Ann, Betty, Edith et Helen.

  • Georgia a rencontré Ann et Helen.

  • Helen a rencontré Betty, Félicia et Georgia.

  Vous voyez, mon cher Holmes, les réponses sont concordantes!

  C'est alors que Holmes prit un crayon et dessina un étrange petit dessin, avec des points marqué A, B, C, E, F, G, H et des lignes reliant certains de ces points. Puis, en moins de trente secondes, Holmes déclara:
  - Tiens, tiens! Ce que vous venez de me dire détermine d'une façon unique l'assassin.

Qui est l'assassin?
  1   2   3   4   5   6   7   8   9   10

similaire:

Cours de Théorie des Graphes icon«Un bon dessin vaut mieux qu’un long discours». Le langage des graphes...

Cours de Théorie des Graphes iconFiche ue10-cours 2 structure normale et pathologique de la peau de la theorie a la pratique

Cours de Théorie des Graphes iconCours sur la raison et la croyance
«forts» se laissent dominer, c’est qu’ils sont devenus faibles. C’est pourquoi Socrate va amener Calliclès à reformuler sa théorie...

Cours de Théorie des Graphes iconLa théorie du chaos est pour les mathématiciens une théorie comme une autre, née au XX e
«détermine» le lieu précis où le ballon va tomber, I e., par expérience, IL analyse deux instants passé et présent du ballon et IL...

Cours de Théorie des Graphes iconApproche anthropologique de la douleur : en échos à Bernard Feltz...

Cours de Théorie des Graphes iconКурс лекций по теме: «L’Argumentation dans la langue: théorie et pratique»
«Des trois genres de la rhétorique: le délibératif, le judiciaire, le démonstratif»

Cours de Théorie des Graphes iconRésumé : Entre 1930 et 1959 R. Ruyer a su proposer une théorie de...
«“Percevoir l'étendue ”, c'est une façon d'être étendu»(Ruyer, 1932,c, p. 527), mais l'étendue est la véritable chose en soi qui...

Cours de Théorie des Graphes iconPhysique quantique
«quantiques» décrivent le comportement des atomes et des particules — ce que la physique classique, notamment la mécanique newtonienne...

Cours de Théorie des Graphes iconLe devis ministériel : quels changements cela a-t-il apportés au...

Cours de Théorie des Graphes iconExamen Théorie Niveau 2








Tous droits réservés. Copyright © 2016
contacts
b.21-bal.com