TEST Graphes Spé math. décembre 2012
-------------------------------------------------------------------------------------------
EXERCICE 1
Un graphe G pondéré simple non orienté d'ordre 7 est représenté ci-dessus.
Le nombre positif sur chaque arête est un nombre de minutes.
1. Donner la matrice adjacente M de G.
2. Ce graphe est-il complet ? connexe ? Expliquer.
3. Quel est l'ordre m du plus grand sous graphe complet de G ?
4. Donner le tableau des degrés des sommets.
5. Soit Δ le degré le plus élévé d'un sommet de G.
Donner un encadrement du nombre chromatique λ.
Déduire alors le nombre chromatique λ .
6.Colorier ce graphe G.
7. On veut déterminer le chemin de plus courte durée entre le sommet
D et L.
Pour cela compléter le tableau suivant:
Sommet de marque fixée à chaque étape |
D | G | M | H | C | S | L | Commentaires |
D: 0 |
0 | 8(D) | 10(D) | + ∞ | + ∞ | + ∞ | + ∞ | De D à G 8mn et de D à M 10mn |
|
||||||||
|
||||||||
|
||||||||
|
||||||||
0 |
Quel est donc le plus dourt chemin de D à L ?
-------------------------------------------------------------------------------------------------------------
EXERCICE 2
Voici un graphe G pondéré non orienté simple d'ordre 8
de sommets A B C D E F G H.
Expliquez le tableau suivant que vous pouvez améliorer.
Que permet-il de savoir?
Marque fixée | A | B | C | D | E | F | G | H | |
A: 0 | 0 | 2 | 1 | 3 | + ∞ | + ∞ | + ∞ | + ∞ | |
C : 1 | 2 | 4 | |||||||
B : 2 | 6 | ||||||||
D :2 | 3 | 4 | |||||||
E: 3 | |||||||||
I : 4 | 0 | 2 | 1 | 2 | 3 | 6 | 4 | 8 | |
--------------------------------------------------------------------------------------------------------------