Scribd
Importer
53 vues4 pages

Correction Ex2022

Le document présente une correction de devoir de synthèse avec des exercices sur les graphes, incluant des calculs de chemins, d'arbres partiels minimaux et d'adjacence. Il analyse également les propriétés des graphes, comme la connexité et le degré des sommets, et conclut sur le nombre chromatique du graphe. Les résultats incluent des longueurs de câblage et des chemins spécifiques entre sommets.

Transféré par

Sajda Chrifa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
53 vues4 pages

Correction Ex2022

Le document présente une correction de devoir de synthèse avec des exercices sur les graphes, incluant des calculs de chemins, d'arbres partiels minimaux et d'adjacence. Il analyse également les propriétés des graphes, comme la connexité et le degré des sommets, et conclut sur le nombre chromatique du graphe. Les résultats incluent des longueurs de câblage et des chemins spécifiques entre sommets.

Transféré par

Sajda Chrifa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Correction du devoir de synthèse – RO - 2022

Exercice 1
1.

A B C D E F G H I J K
ꙭ 0 ꙭ ꙭ ꙭ ꙭ ꙭ ꙭ ꙭ ꙭ ꙭ
26B x ꙭ 12B ꙭ ꙭ ꙭ ꙭ 18B 21B ꙭ
26B x 20D x ꙭ ꙭ ꙭ ꙭ 18B 21B/31D 26D
26B x 20D x ꙭ ꙭ ꙭ ꙭ x 21B/23I 26D/23I
26B x x x ꙭ ꙭ ꙭ ꙭ x 21B 23I
26B x x x ꙭ ꙭ ꙭ 30J x x 23I
26B x x x 32k ꙭ 35K 30J/43K x x x
x x x x 32K ꙭ 35K 30J/34A x x x
x x x x 32K ꙭ 35k/40H x x x x
x x x x x 45E 35k x x x x
x x x x x 47G/45E x x x x x
Le plus court chemin entre B et F est BIKEF de longueur 45

2.

La solution optimale correspond à l’arbre partiel minimal de G.

On commence par le sommet A.

L’ensemble des sommets visités est V = {A}

Les arêtes candidates sont AB(26) et AH(8). On ajoute donc à l’arbre le sommet H et
l’arête AH. V = {A, H}

On considère les arêtes dont l’une des extrémités est dans V et l’autre dans le
complément de V, ceux sont AB(26), HG(10), HJ(9) et HK(20). On ajoute donc à l’arbre
le sommet J et l’arête HJ. V = {A, H, J}

On procède de la même manière jusqu’à avoir V = l’ensemble de tous les sommets.

Le résultat est illustré dans la figure ci-dessous.


La longueur du câblage est 8+9+5+5+9+10+12+14+8+12 = 92Km

Exercice 2

1.

0 1 0 1 0 0
0 0 0 0 0 1
0 1 0 0 1 0
0 0 0 0 0 1
0 0 1 1 0 0
0 0 0 0 1 0
2.

* Pas de circuits commençant en A.

* Les circuits commençant en C sont :


- CEC
- CEDFEC
- CBFEC

* Les circuits commençant en C sont :

- FEDF
- FECEDF
- FECBF

3.

a) Il existe deux chemins de longueur 4 reliant A à D (dans la matrice M4 a14 = 2)

b) Il existe trois chemins de longueur 5 reliant C à E D (dans la matrice M5 a35 = 3)

4.

0 3 4 5 6 6
0 2 3 3 5 4
0 5 7 7 10 8
0 2 3 3 5 4
0 5 7 7 10 8
0 3 5 5 7 5

5. Le graphe G n’est pas fortement connexe car il existe dans SM des 0 en dehors de la
diagonale (la première colonne). En effet, pas de chemins de B vers A, de C vers A, de
D vers A, de E vers A et de F vers A.

Exercice 3

1. La matrice d’adjacence M associé à G est une matrice carré 11x11, donc l’ordre
de G est égal à 11.
2.
- Le graphe G est simple car aucun sommet n’est en relation avec lui-même (la
diagonale ne contient que des 0).
- La matrice M est symétrique donc le graphe G n’est pas orienté.
- La matrice d'adjacence M contient des 0 en dehors de la diagonale donc le
graphe G n’est pas complet.
3. Le graphe est symétrique. Donc :
Le degré de A est le nombre de 1 se trouvant dans la première ligne.
Le degré de B est le nombre de 1 se trouvant dans la deuxième ligne.
Et ainsi de suite …

Sommet Degré
H 5
K 5
D 4
G 3
I 3
J 3
A 2
B 2
E 2
F 2
C 1

4.

Sommet Degré Couleur Sommets candidats pour


avoir la même couleur
H 5 Couleur1 BCDEF
K 5 Couleur2 AFI
D 4 Couleur1 BC
G 3 Couleur3 JE
I 3 Couleur2 AF
J 3 Couleur3 E
A 2 Couleur2 F
B 2 Couleur1 C
E 2 Couleur3
F 2 Couleur2
C 1 Couleur1

Il faut 3 couleurs pour colorer correctement les sommets du graphe G, le nombre


chromatique de G est donc égal à 3.

Vous aimerez peut-être aussi