Terminale Option Experte / Graphes et matrices 21 exercices (100% corrigés)

a
1. Ordre et degré E.6226 On considère le graphe ci-dessous : 1 Donner l’ordre du graphe. 2 Compléter le tableau ci-dessous : Point A B C D E Degré du point 3 Dans le tableau à double entrée ci-dessous, mettre une croix dans une case si les deux sommets correspondants sont adjacents : A B C D E A B C D E E.6227 On considère le graphe ci-dessous : 1 Donner l’ordre du graphe. 2 Compléter le tableau ci-dessous : Point A B C D Degré du point 3 Dans le tableau à double entrée ci-dessous, mettre une croix dans une case si les deux sommets correspondants sont adjacents : A B C D A B C D 2. Graphe simple E.6224 On considère le graphe ci-dessous : 1 Quel est l’ordre de ce graphe? 2 Compléter le tableau ci-dessous : Sommet A B C D E F Degré du sommet 3 La somme des degrés de tous les sommets est-elle égale au double du nombre d’arêtes? 4 Ce graphe est-il simple? E.6225 Justifier que chacun des graphes ci-dessous n’est pas un graphe simple : a b c c https://chingmath.fr chapExoCorrec/6226 sacados/6226 ABCDE chapExoCorrec/6227 sacados/6227 ABCD chapExoCorrec/6224 sacados/6224 AFBCDE chapExoCorrec/6225 sacados/6225
E.6209 Pour chacune des graphes ci-dessous : 1 Citer l’ordre du graphe ; 2 Citer le degré du sommet A 2 ; 3 Donner les sommets adjacents au sommet A 5 ; 4 Dire si le graphe est simple ou non. Fig 1: Fig 2: Fig 3: 3. Sous-graphe E.6229 On considère le graphe ci-dessous : Parmi les graphes ci-dessous, lesquels sont des sous-graphes du graphe principal? a b c 4. Sous graphe stable E.6272 Une société de gardiennage accueille actuellement sept chiens représentés dans le graphe ci-dessous par les sommets du graphe ; les arêtes représentent les chiens ne pouvant pas être enfermés dans une même cage. 1 Quel est le plus grand sous-graphe stable contenant un maximum de sommets? 2 Combien de cages au minimum faut-il pour garder ces sept chiens sans risquer des confrontations entre ces chiens? 5. Complet et connexe E.6245 On considère les deux graphes ci-dessous : https://chingmath.fr chapExoCorrec/6209 sacados/6209 A1A2A3A4A5A6A7A8 A1A2A3A4A5A6A7 A1A2A3A4A5A6A7 chapExoCorrec/6229 sacados/6229 ABCDEFG CDEFG ABCE ABCD chapExoCorrec/6272 sacados/6272 ABCDEFG chapExoCorrec/6245 sacados/6245
Préciser si ces graphes sont connexes ou pas. 6. Chaine et cycle E.6242 On considère le graphe ci-dessous : Parmi les listes ordonnées ci-dessous, lesquelles forment une chaine de ce graphe : 1 A − E − F − E − G − D 2 E − F − A − B − C 3 D − A − C − D 4 D − C − E − A − F − E 7. Introduction aux matrices E.6142 On appelle ˇ matrice mag-ique ı toute matrice où les sommes des coefficients par ligne, par colonne , par la diagonale principale et par la seconde diagonale donnent toutes le même résultat. Parmi les matrices suivantes, lesquelles sont des matrices mag-iques : a 9 4 5 2 6 10 7 8 3 b 2 7 6 9 5 1 4 3 8 c 8 1 3 0 5 7 4 6 2 E.6141 On considère la matrice A définie par : A = 2 3 − 1 5 3 0 4 − 2 1 3 − 4 7 Pour mettre en évidence les coefficients de la matrice, on note : A = a ij 1 Donner la valeur des coefficients de la matrice suivants : a a 23 b a 34 c a 11 d a 31 2 Déterminer la valeur des calculs suivants : a a 11 + a 21 b a 32 × a 14 c a 24 2 3 Citer l’ensemble des couples de coefficients de la matrice opposés entre eux. E.6123 Une entreprise recense le prix en euros des produits qu’elle utilise en lien avec ses différents fournisseurs. Il obtient le tableau à double entrée suivant : Produit 1 Produit 2 Produit 3 Fournisseur 1 3,50 2,80 1,75 Fournisseur 2 3,25 3 1,70 Il note l’ensemble de ces valeurs dans la matrice M : M = 3 ; 50 2 ; 80 1 ; 75 3 ; 25 3 1 ; 70 Les différents nombres placés dans la matrice s’appellent ˇ les coefficients de la matrice ı. On note, de manière générale, m ij les coefficients de la matrice où i et j sont deux entiers per-mettant de situer la place du coefficient dans la matrice. Plus précisément, le coefficient m ij est le prix du ˇ Produit j ı chez le ˇ Fournisseur i ı. 1 a Donner les valeurs des coefficients suivants : m 12 ; m 22 ; m 13 b Compléter la phrase suivante : ˇ Le coefficient m ij se situe dans la matrice à l’intersection de la ligne . . . et de la colonne . . . ı 2 Écrire la nouvelle matrice N = n ij où le coefficient n ij a pour valeur le prix du produit i chez le fournisseur i . 8. Matrice adjacente d’un graphe non-orienté E.6171 Définition: soit G un graphe à n sommets ( n ∈ N ∗ ) . On appelle matrice d’adjacence du graphe G la matrice M = m ij carrée d’ordre n dont les coefficients ont pour valeur: m ij = 1 si le sommet A i est relié au sommet A j par une arête 0 sinon pour i;j ∈ [[1; n ]] . https://chingmath.fr ABCDEF ABCDEF chapExoCorrec/6242 sacados/6242 ABCDEFG chapExoCorrec/6142 sacados/6142 fichierPlus/6142/ chapExoCorrec/6141 sacados/6141 chapExoCorrec/6123 sacados/6123 chapExoCorrec/6171 sacados/6171
Le graphe ci-dessous représente 7 villes reliées par des routes : Donner la matrice d’adjacence de ce graphe. E.6196 Lors d’une campagne élec-torale, un homme politique doit effectuer une tournée dans les huit villes notées de A 1 à A 8 , en utilisant le réseau au-toroutier. Le graphe G ci-dessous, représente les différentes villes de la tournée et les tronçons d’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) : Donner l’expression de la matrice M d’adjacence du graphe G . E.6228 Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d’activités d’une municipalité. Une arête reliant deux de ces sommets indique l’existence d’une voie d’accès principale en-tre deux lieux correspondants. 1 Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l’ordre alphabétique) . 2 Donner la matrice M associée au graphe (les sommets seront mis dans l’ordre alphabétique) . E.6330 On considère un graphe G ad-mettant la matrice M pour ma-trice d’adjacence. Parmi les représentations ci-dessous, une seule correspond au graphe G . M = 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 a b c Précisera la représentation correcte et on justifiera son choix en expliquant les raisons pour lesquelles on a écarté les deux autres représentations. 9. Matrice adjacente d’un graphe orienté E.6230 Donner la matrice d’adjacence du graphe ci-dessous : E.6170 Donner la matrice M d’adjacence du graphe orienté donné ci-dessous : 10. Introduction aux opérations sur les matrices E.6712 Indication : au cours de l’exercice, une matrice M = m ij aura son coefficient m ij qui exprimera le ˇ prix du produit j chez le fournisseur i . ı https://chingmath.fr A1A2A3A4A5A6A7 chapExoCorrec/6196 sacados/6196 A1A2A3A4A5A6A7A8 chapExoCorrec/6228 sacados/6228 ABCDEFG chapExoCorrec/6330 sacados/6330 ABCDEF ABCDEF ABCDEF chapExoCorrec/6230 sacados/6230 ABCDEFG chapExoCorrec/6170 sacados/6170 A1A2A3A4A5A6A7 chapExoCorrec/6712 sacados/6712
Une entreprise recense le prix en euros des produits qu’elle utilise en lien avec ses différents fournisseurs. Il obtient le tableau à double entrée suivant : Produit 1 Produit 2 Produit 3 Fournisseur 1 3,50 2,80 1,75 Fournisseur 2 3,25 3 1,70 1 Écrire la matrice A reliée à ces prix.. 2 Les fournisseurs décident d’une augmentation sur leurs produits dont les montants sont donnés dans le tableau ci-dessous : Produit 1 Produit 2 Produit 3 Fournisseur 1 0,50 0,20 0,25 Fournisseur 2 0,25 0 0,3 Écrire la matrice B correspondante à ces augmentations. 3 Écrire la matrice C correspond aux nouveaux prix de ces produits chez chacun des fournisseurs. E.6153 Une entreprise se fournit en matière première dans deux pays différents. On considère les deux tableaux suivants : Alu M1 Bois M2 Fer M3 Pays 1 25 14 12 Pays 2 23 11 11 Prix des matières premières Alu M1 Bois M2 Fer M3 Pays 1 3 2 1 Pays 2 2 3 1 Prix du transport 1 a Écrire la matrice A = a ij ij où le coefficient a ij représente ˇ le prix du matériau j dans le pays i ı. b Écrire la matrice B = b ij ij où le coefficient b ij représente ˇ le prix de transport du matériau j dans le pays i ı. c Écrire la matrice C = c ij ij où le coefficient c ij représente ˇ le prix d’achat du matériau j dans le pays i ı. 2 Pour entamer sa production, l’entreprise a besoin de 2 unités d’Aluminium, de 1 unité de bois et de 3 unités de Fer. On représente ces données dans la matrice D = d ij don-née ci-dessous : D = 2 1 3 a Donner une interprétation du nombre : c 11 × d 11 + c 12 × d 21 + c 13 × d 31 b Déterminer le prix total de ses achats lorsque l’entreprise se fournit dans le pays 2 ? E.6143 Trois triathlètes participent à une course. Les temps de parcours, exprimés en minutes de chacune des épreuves, sont donnés dans le tableau ci-dessous : Jacques 1 er athlète Henry 2 e athlète Paul 3 e athlète Course à pied (épreuve 1) 45 62 34 Natation (épreuve 2) 35 24 28 Cyclisme (épreuve 3) 92 95 104 On souhaite représenter les données de ce tableau à double entrée par une matrice A = a ij où le coefficient a ij est le temps de parcours, exprimé en minutes, de l’athlète i lors de l’épreuve j . 1 a Donner les valeurs des coefficients suivants : a 13 ; a 32 b Écrire la matrice A . 2 On considère la matrice B = b ij où le coefficient b ij est la durée, exprimé en heure et arrondie au centième près, du temps de parcours effectué par l’athlète i lors de l’épreuve j . a Écrire la matrice B b Quel mécanisme simple permet de passer de la matrice A à la matrice B ? https://chingmath.fr chapExoCorrec/6153 sacados/6153 chapExoCorrec/6143 sacados/6143