[PDF] Introduction ? la théorie des graphes Solutions des exercices

GRAPHES - EXERCICES CORRIGES Compilation - Lycée d Adultes

[PDF] GRAPHES EXERCICES CORRIGES Compilation Lycée d 'Adultes lyceedadultes math Graphesexoscorrigés pdf

Graphes exercices et correction

[PDF] Graphes exercices et correctionmathematiques ac bordeaux graphes exos graphes exos pdf

éléments de théorie des graphes quelques exercices d application

[PDF] éléments de théorie des graphes quelques exercices d 'applicationmathematiques ac bordeaux graphes exo graphes sopena tout pdf

Introduction ? la théorie des graphes Solutions des exercices

[PDF] Introduction ? la théorie des graphes Solutions des exercices apprendre en ligne graphes corriges pdf

Theorie des graphes

[PDF] Theorie des graphes is unice ~malapert graphes slza cours pdf

Feuille TD n° 2 #8211; Exercices (Graphes)

[PDF] Feuille TD n° Exercices (Graphes)dept info labri ENSM% %Graphes% %Correction%Feuille%TD pdf

Exercices Graphes TD n°1

[PDF] Exercices Graphes TD n° graphes TD pdf

graphes

[PDF] graphessite math free terminale es cours terminale es graphes pdf

Théorie des Graphes - usthb

[PDF] Théorie des Graphes usthbperso usthb dz ~mboukala TDTG pdf

Exercices - Théorie des graphes - exercices pratiques :

Exercice Est ce le même graphe ? Master Enseignement Les deux premiers dessins représentent le même graphe Il s 'agit d 'un pentagone où tous les

[PDF] exercices histoire 5eme

[PDF] exercices histoire 6ème ? imprimer

[PDF] exercices hockey sur gazon

[PDF] exercices initiation hockey sur gazon

[PDF] exercices mathématique pdf

[PDF] exercices maths 1ere es

[PDF] exercices maths 1ere s nouveau programme

[PDF] exercices maths 1ere s pdf

[PDF] exercices maths bcpst 1

[PDF] exercices maths terminale stmg

[PDF] exercices mouvement des satellites et des planètes corrigés pdf

[PDF] exercices nombres complexes corrigés

[PDF] exercices nombres complexes terminale s

[PDF] exercices nombres complexes type bac pdf

[PDF] exercices physique nucleaire pdf

CAHIERS DE LA CRM

Introduction à la théorie

des graphes

Solutions des exercices

Didier Müller

CAHIER NO

6COMMISSION ROMANDE DE MATHÉMATIQUE

1 Graphes non orientésExercice 1On obtient le graphe biparti suivant (à gauche) :

P1C1 P2C2 P3C3 P1C1 P2C2 P3C3 En colorant les arêtes de ce graphe (1 couleur = 1 heure de l'horaire), en prenant garde que chaque sommet n'ait pas deux arêtes incidentes de même couleur, on obtient le résultat de droite. De ce graphe coloré, on tire l'horaire suivant :

P1P2P3

1ère heure (rouge)C1C3C2

2ème heure (vert)C1C2C3

3ème heure (bleu)C2C1C3

4ème heure (noir)C1

Exercice 2

On obtient le graphe completK6.

21
36
45
Il faudra 5 jours de tournoi. Voici un calendrier possible :

Jour 1Jour 2Jour 3Jour 4Jour 5

1-22-31-32-41-4

3-44-54-61-52-6

5-61-62-53-63-5

Ce calendrier a été construit d'après les cinq schémas ci-dessous : 21
36
45
21
36
45
21
36
45

CAHIERS DE LACRMNo6 bis1

21
36
45
21
36
45

Exercice 3

On utilise le graphe qui indique les cases atteignables depuis une case courante. Les mouvements sont donc (par exemple) : c3-b1, a3-c2, a1-b3, c1-a2, b1-a3, c2-a1, b3-c1, a2-c3, c3-b1, a3-c2, a1-b3, c1-a2, b1-a3, c2-a1, b3-c1, a2-c3

Exercice 4

Comme Holmes, dessinons un graphe avec les sommets A, B, C, E, F, Get H. Dans ce graphe, on relie deux sommets i et j si les suspectes i et j se sont rencontrées au château. Pour découvrir laquelle des 7 femmes est venue plus d'une fois au château, il faut recher- cher dans le graphe des cycles reliant quatre sommets, sans diagonale. En effet, un tel carré ijkl sans diagonale indique que l'une des quatre suspectes est nécessairement venue plus d'une fois au château. Pour s'en convaincre, on peut faire le petit schéma temporelci-dessous : On voit que i a dû venir deux fois au château pour qu'un cycle sans diagonale apparaisse dans le graphe. Le seul sommet commun à ces trois cycles est le sommet A. C'est donc Ann la coupable.

2No6 bisCAHIERS DE LACRM

Exercice 5Construisons un graphe dont les sommets représentent les sixpersonnes; deux sommets sont reliés par une arête noire lorsque les personnes se connaissent et rouge dans le cas contraire. Il s'agit de prouver que ce graphe contient une cliqueK3dont les arêtes sont de même couleur. Si l'on ne tient pas compte de la couleur des arêtes, on obtient le graphe completK6. De chaque sommet partent cinq arêtes, et au moins trois d'entreelles sont de même couleur (noire ou rouge). Considérons la cliqueK4composée des sommets 1, 2, 3 et 4. Supposons, par exemple, que les arêtes (1, 2), (1, 3) et (1, 4) soient grises. 21
36
45
Considérons alors la cliqueK3composée des sommets 2, 3, 4. Si toutes ces arêtes sont rouges, c'est terminé : on a trois personnes qui ne se connaissent pas. Si une de ces arêtes est grise, c'est aussi terminé : on a troispersonnes qui se connaissent. Par contre, dans unK5, on peut trouver deux graphes partiels complémentaires sansK3. On le voit sur les deux graphes partiels ci-dessous, dont la "superposition" donne le graphe completK5: 1 25
34
"Se connaissent" 1 25
34
"Ne se connaissent pas"

Exercice 6

SoitG= (V,E)un graphe simple. Quand on calcule la somme des degrés des sommets, chaque arête(x,y)deEest comptée deux fois, une première fois pourd(x)et une seconde fois pourd(y). Donc, cette somme est finalement égale à deux fois le nombre d'arêtes.

Remarque

nant qu'une boucle contribue pour 2 dans le calcul du degré d'un sommet.quotesdbs_dbs2.pdfusesText_3