Outside the high school program / Graph 57 exercises (including 51 corrected)

a
ChingQuizz : 3 exercises available for Quizz assessment : 1. Sharing by levels (Bellman algorithm in a circuitless graph) E.7675 Consider the directed graph below : 1 Write the adjacency matrix associated with this graph. 2 Is the graph circuit-free? If so, divide it into levels and propose a new representation of the graph. E.7678 In the Bayel master glass-makers’ company, there are seven different workshops used to create the pieces. To study the different passages of a piece from one workshop to another, we associate a letter with each workshop. Atelier Compassage Décors Flettage Moules Sommet C D F M Atelier Polissage Rebrulâge Soufflerie Sommet P R S The directional graph below shows the various possible pas-sages of a part from workshop to workshop. 1 Using the graph vertices in alphabetical order, determine the adjacency matrix associated with this graph. 2 Is the graph circuit-free? If so, divide it into levels and give a new representation of this graph. E.8188 A group of friends decides to cre-ate an ˇ Escape Game ı in Montpellier. This attraction will feature several rooms, each representing a theme with a puz-zle to solve. 1 Here is the list of themes proposed for the creation of their attraction : E : Space J : The Jungle N : Snow S : Sherlock Holmes W : Wall Street M : the sea A : airplanes I : computers This group imagined the different possibilities for mov-ing from one themed room to another. They represented these passages in the graph below using directed edges : a By arranging the vertices in alphabetical order, give the adjacency matrix associated with this graph. b Is this graph cycle-free? If so, divide it into levels and propose a new presentation for this graph. 2 In room ˇ Space ı, , the constellation Ursa Major is dis-played, consisting of 7 stars : Dubhe ( D ), Merak ( R ), Phecda ( P ), Megrez ( M ), Alioth ( A ), Mizar ( I ) and Alkaid ( K ). https://chingmath.fr chapExoCorrec/7675 sacados/7675 ABCDEFG chapExoCorrec/7678 sacados/7678 MSRFCPD chapExoCorrec/8188 sacados/8188 EJNSWMAI
The lines represent possible movements and the numbers indicate distances expressed in light years. Participants must find the shortest path to travel from the star Alkaid ( K ) to the star Dubhe ( D ) as quickly as possible. Use the table below to present Dijkstra’s algorithm ap-plied to this graph in order to determine the shortest path between these two stars. K I A M P R D We will then specify the shortest path and its distance. 2. Linear programming: simplex method E.7676 A company produces differ-ent qualities of glass. Because of supply problems, it monitors the use of two elements : silica, germanium and arsenic. In addition, we have the following information : To build one hundred glass dishes, the company uses : 3 kg silica, 1 kg germanium and 1 kg arsenic. To build one hundred glass bowls, the company uses : 1 kg silica, 2 kg germanium and 10 kg arsenic. The company has 3 kg of silica, 2 kg of germanium and 9 kg of arsenic. We’ll note x and y the numbers of hundreds of glass dishes and hundreds of glass bowls respectively. Each dish is sold 4 e and each bowl is sold 3 e . 1 Express the constraints of the problem as a system of inequalities. Express the function giving sales achieved in hundreds of euros as a function of x and y . 2 In this question, we’re looking to optimize sales. a Represent below the set of solutions réalisables. b By graphical method, determine the solution maximiz-ing the value of the expression 4 · x +3 · y . c Deduct the maximum sales the company can achieve. https://chingmath.fr KIAMPRD1631541571741419 chapExoCorrec/7676 sacados/7676 x-0,200,20,40,60,811,21,4y-0,20,20,40,60,811,21,4
E.8189 A jeweler begins mass pro-duction of two types of jewelry: The ˇ Egypt ı ring, which requires 6 grams of gold, 4 grams of platinum, and 6 grams of silver. The ˇ Babylon ı necklace, which requires 30 grams of gold, 5 grams of platinum, and 3 grams of silver. The jeweler has 180 grams of gold, 45 grams of platinum, and 60 grams of silver in his workshop. Note that x and y are the numbers of rings ˇ Egypt ı and neck-laces ˇ Babylon ı made, respectively. Each ring will be sold for 17 e and each necklace for 51 e . Let’s help the jeweler decide how many rings and necklaces he should make in order to maximize his revenue if he sells all of his products. 1 Express the constraints of the problem in the form of a system of inequalities. Express the function giving the revenue in dollars as a function of x and y . 2 In this question, we are looking to optimize revenue. a Represent all possible solutions below. b Using a graphical method, determine the solution that maximizes the value of the expression 17 · x +51 · y . c Deduce the maximum revenue that the jeweler can achieve. 3. Simplex algorithm E.7677 A company produces differ-ent qualities of glass. Because of supply problems, it monitors the use of two elements : silica, germanium and arsenic. In addition, we have the following information : To build one hundred glass dishes, the company uses : 3 kg silica, 1 kg germanium and 1 kg arsenic. To build one hundred glass bowls, the company uses : 1 kg silica, 2 kg germanium and 10 kg arsenic. The company has 3 kg of silica, 2 kg of germanium and 9 kg of arsenic. We’ll note x and y the numbers of hundreds of glass dishes and hundreds of glass bowls respectively. Each dish is sold 4 e and each bowl is sold 3 e . 1 Express the constraints of the problem as a system of inequalities. Express the function giving sales achieved in hundreds of euros as a function of x and y . 2 Using the simplex algorithm, find the maximum sales under the constraints given previously. 4. TD 5 L4 E.8088 For the graph G below : https://chingmath.fr chapExoCorrec/8189 sacados/8189 x-3-2-101234567891011y-3-2-11234567891011 chapExoCorrec/7677 sacados/7677 chapExoCorrec/8088 sacados/8088 1234567
1 Determine the matrix M associated with the graph G . 2 Determine d + and d − . 3 Is the graph circuit-free? If so, divide it into levels. 4 Then give a new representation of the graph. E.8089 For the graph G below : 1 Determine the matrix M associated with the graph G . 2 Determine d + and d − . 3 Is the graph circuit-free? If so, split into levels. 4 Then give a new representation of the graph. E.8090 Plot the following adjacency matrix graph : 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 E.8091 Plot the following adjacency matrix graph : 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 E.8092 We want to transport chem-icals by rail. A , B , C , D , E , F , G and H stand for eight chemicals. In the table below, a cross means that the prod-ucts cannot be stored in the same wagon, as there would be a risk of explosion. 1 Construct the graph where the vertices are the chemicals and the edges represent the storage incompatibilities of these products with each other. 2 Write the corresponding adjacency matrix. 3 We want to use as few railcars as possible to transport all these chemicals. Explain how the Welsh-Powell algo-rithm can answer this question. 4 Apply this algorithm. 5. TD 6 L4 E.8093 Students A , B , C , D , E and F have to take exams in different disciplines, each exam oc-cupying half a day: Chemistry : students A and B . Electronics : students C and D . Computer science : students C , E , F and G . Mathematics : students A , E , F and H . Physics : students B , F , G and H . We aim to organize the shortest possible exam session. E.8094 Here’s a validated graph mod-eling American air traffic. What is the cheapest way to get from Miami to Los Angeles? https://chingmath.fr chapExoCorrec/8089 sacados/8089 ABCDEFGH chapExoCorrec/8090 sacados/8090 chapExoCorrec/8091 sacados/8091 chapExoCorrec/8092 sacados/8092 chapExoCorrec/8093 sacados/8093 chapExoCorrec/8094 sacados/8094 San FranciscoLos AngelesDenverChicagoBostonNew YorkAtlantaMiami39$55$99$89$129$69$79$65$99$39$79$99$69$129$
E.8095 A haulier wants to get from Nantes to Brest by road as quickly as possible. Help him find his way The numbers shown represent journey times in min . E.8278 Airport managers must assess the minimum number of runways required based on the type of aircraft and the length of the runway required for takeoff. To comply with regulations on safety distances based on flight frequency, certain aircraft cannot land on the same runways. The table below summarizes these incompatibilities: a cross indicates that these aircraft cannot take off from the same runway. A320 A321 B373 A380 A350 B777 A320 × × × × A321 × × × B373 × × × A380 × × A350 × × × × B777 × × What is the minimum number of runways that the airport must have? E.8279 Here’s the validated graph that models the plan of a neighborhood that a courier has to cross to deliver a parcel in minimum time from the departure ware-house A to the delivery point K . Each vertex represents a crossing and each arc a street. The value assigned to the arc represents the travel time in minutes. Which is the fastest route? 6. TD 7 L4 E.8096 We want to assign 5 tasks to 5 machines. The costs of the assignments are given by the following table : machine 1 machine 2 machine 3 machine 4 machine 5 Task 1 15 40 5 20 20 Task 2 22 33 9 16 20 Tâche 3 40 6 28 0 26 Task 4 8 0 7 25 60 Task 5 10 10 60 15 5 Find an assignment leading to minimum cost using the Hun-garian algorithm. E.8097 Determine by the Hungarian method a minimum cost assignment associated with the fol-lowing cost matrix: 7 2 1 9 4 9 6 9 5 5 8 8 3 1 8 7 9 4 2 2 4 3 7 4 8 https://chingmath.fr chapExoCorrec/8095 sacados/8095 NantesRennesVannesLorientQuimperPontivyCarhaixChateaulinBrest BrestBrestCarhaixCarhaixChateaulinChateaulinLorientLorientNantesNantesPontivyPontivyQuimperQuimperRennesRennesVannesVannes3535506035352550454540757560457545254575757040754570 chapExoCorrec/8278 sacados/8278 chapExoCorrec/8279 sacados/8279 ABCDEFGHIJK123115774211513212 chapExoCorrec/8096 sacados/8096 chapExoCorrec/8097 sacados/8097
E.8098 Solve : max: 1 200 · x 1 +1 000 · x 2 under duress : 3 x 1 + 4 x 2 160 6 x 1 + 3 x 2 180 x 1 0 x 2 0 Solve this problem graphically and then by the simplex algo-rithm. E.8280 As part of his company’s anti-pollution policy, a carrier wants to travel from Montpellier to Cahors with the lowest possible emissions of particulate pollutants : The numbers shown represent the emissions of particulate pol-lutants on the journey. Determine the route to be taken by the transporter. 7. TD 8 L4 E.8099 A worker makes 2 types of diary Ag 1 and Ag 2 : Ag1 1 hour of manufacture Cost of manufacture : 3 e Profit : 2 e Ag2 2 hours of manufacture Cost of manufacture : 2 e Profit : 3 e The worker works 8 hours a day. The worker can invest 12 e = jour to manufacture his diaries. How many diaries of each type must be made per day to maximize profit? E.8100 A chocolatier decides to make chocolate eggs. In reserves, he has 18 kg of cocoa, 8 kg of hazelnuts and 14 ‘ of milk left. It has two specialties: the Extra egg and the Sublime egg. An Extra egg requires 1 kg of cocoa, 1 kg of hazelnuts and 2 ‘ of milk. A Sublime egg requires 3 kg of cocoa, 1 kg of hazelnuts and 1 ‘ of milk. He will make a profit of 20 euros by selling an Extra egg, and 30 euros by selling a Sublime egg. How many Extra and Sublime eggs must he make to make the highest possible profit? 8. Graph coloring E.7665 Seven white rectangles are shown below : Color these seven rectangles with as few colors as possible. https://chingmath.fr chapExoCorrec/8098 sacados/8098 chapExoCorrec/8280 sacados/8280 13520515513580858055855520530125155959530505035555512535MontpellierMontpellierRodezRodezVillefranche de R.VillefranchedeRouergueFigeacFigeacAlbiAlbiCarcassonneCarcassonneToulouseToulouseMontaubanMontaubanCahorsCahors MontpellierCarcassonneToulouseAlbiMontaubanRodezVillefranchedeRouergueFigeacCahors chapExoCorrec/8099 sacados/8099 chapExoCorrec/8100 sacados/8100 fichierPlus/8100/diapoCorrection.pdf sacados/7665
E.7664 The collection points for a truck from a company recycling ˇ waste paper ı and the possible routes between these points are represented by the graph be-low : The depot is represented by vertex A and the other vertices represent the various collection points. To make his plan more legible, the truck driver wants to color the vertices of the graph representing his network so that no two adjacent vertices ever have the same color. How many colors can he use? E.7666 A cosmetics company commissions a marketing study on a given population. The marketing study shows that certain products are never purchased simultaneously. Incompatibilities are represented by the following graph, where two connected vertices repre-sent two products that are never in the same order. For ex-ample, products A and B , represented by connected vertices, are never in the same order. The company would like to divide the products into lots made up of products that are not incompatible with each other. What is the minimum number of batches required? Justify your answer with an algorithm and propose a product alloca-tion. E.7667 Determine the chromatic number » of the graph below : E.7668 A group of friends are organizing a hike in the Alps. They have represented by the graph below the summits B , C , D , F , T , N through which they can choose to pass. An edge between two vertices coincides with the existence of a path between the two vertices. 1 Copy and complete the following table : Sommets B C D F N T Degree of sommets du graphe 2 The group wishes to associate each vertex with a color so that vertices connected by a path do not have the same color. Let n be the chromatic number of the graph. a Show that : 4  6 b Propose a coloring of the graph to determine its chro-matic number. https://chingmath.fr chapExoCorrec/7664 sacados/7664 ABCDEFGH sacados/7666 Extrait Antilles-Guyane Septembre 2013 ABCDEFGH sacados/7667 ABCDEFG sacados/7668 BCFDTN
E.7669 On the occasion of the Football World Cup 2006 in Germany, a tourist agency is organizing coach trips through the various cities where a national team’s matches will be played. For safety reasons, supporters of certain national teams taking part in the 2006 soccer World Cup cannot be accommodated in the same hotel. The incompatibility graph between fans of different teams is given below : for example, a fan of team A cannot be accom-modated with a fan of team B 1 Determine the chromatic number of this graph, justifying the value found. 2 Prove a distribution of fans by hotel using a minimum number of hotels. E.7673 An airline offers direct flights be-tween certain cities, noted A , B , C , D , E , F and G . This leads to the following G graph, whose vertices are cities and edges represent air links: 1 Is the graph G complete? What is the order of G ? 2 a On boarding passes, the company assigns each air-port a color, so that two airports linked by a direct flight have different colors. Suggest a coloring scheme suitable for this condition. b What can we deduce about the chromatic number of G ? 3 a What is the nature of the subgraph formed by the vertices A , B , C and D ? b What is the minimum number of colors the company must use to be able to assign a color to each airport in compliance with the conditions of 2 ? 9. Eulerian chain and cycle E.6243 Consider the graph opposite : Determine an Eulerian chain of this graph. E.6244 Consider the graph opposite : 1 Justify that the graph is complete. 2 Determine an Eulerian cy-cle. E.6273 Consider the graph G below : 1 a Determine with justification whether the graph G is complete. b Determine with justification whether the graph G is connected. 2 a Give the degree of each vertex of the graph G . b Justify whether the graph G admits an Eulerian cycle or an Eulerian chain. 3 a Give the matrix M associated with the graph G (ver-tices will be arranged in alphabetical order) . b We give : https://chingmath.fr sacados/7669 APCQERG sacados/7673 ABCDEFG chapExoCorrec/6243 sacados/6243 ABCDEF chapExoCorrec/6244 sacados/6244 ABCDE chapExoCorrec/6273 sacados/6273 ABCDEFGHI
M 2 = 4 2 2 1 2 2 2 1 1 2 5 1 3 1 1 1 2 0 2 1 4 2 1 1 1 2 2 1 3 2 4 1 1 0 1 0 2 1 1 1 2 2 0 0 0 2 1 1 1 2 2 0 0 0 2 1 1 0 0 0 3 2 1 1 2 2 1 0 0 2 4 1 1 0 2 0 0 0 1 1 2 Show, by calculation, that the coefficient of the sev-enth row and fourth column of the matrix M 3 is equal to 3 . E.6274 Consider the graph G below : 1 Does this graph admit an Eulerian chain? Justify the answer. If so, give such a chain. 2 Does this graph admit an Eulerian cycle? Justify your answer. If so, give such a cycle. 3 Give the matrix M associated with the graph G . The vertices will be taken in alphabetical order : A , B , C , D , E , F , G . E.6275 Which of the following statements are true? Answers must be justified. Consider the graph G shown below : 1 The graph G admits an Eulerian chain. 2 The graph G admits an Eulerian cycle. 3 The graph G is complete. 4 The graph G the graph admits a stable subgraph of order 4 . 5 The graph G is not connected. E.6276 Consider a play area reserved for children. Children can move on five platforms noted A , B , C , D and E . These platforms are connected by a number of ramps, as shown in the diagram below : This play area is represented by the graph G below : A platform is represented by a vertex and a ramp is repre-sented by an edge. 1 Give a complete subgraph of order 4 of the graph G . 2 Is this graph connected? Is it complete? Justify answers. 3 Does this graph contain an Eulerian chain? Justify the answer. 4 If we add an edge to this graph, which vertices can we then connect so that the resulting graph contains an Eu-lerian cycle? Justify your answer. E.6291 Let M be the square matrix of order 5 : M = 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 Construct the graph associated with M . We’ll call A , B , C , D , E the vertices. Is this graph connected? Is it complete? 2 Is there an Eulerian chain? Is there an Eulerian cycle? https://chingmath.fr chapExoCorrec/6274 sacados/6274 ABCDEFG chapExoCorrec/6275 sacados/6275 ABCDE chapExoCorrec/6276 sacados/6276 ADCBE ABCDE chapExoCorrec/6291 sacados/6291
E.6292 Consider the graph G below : 1 Justify the following statements : a The graph G admits at least one Eulerian chain. b The chain D − A − B − C − F − B − E − F − A − E is not an Eulerian chain of G . 2 Determine a complete subgraph of G , having the largest possible order. E.6293 The object of study is a city’s sewer network. This network is modeled by the graph below : the vertices represent the stations and the edges, the pipes. Does this graph admit an Eulerian chain? E.6294 Consider the undirected graph G with vertices A , B , C , D , E whose matrix is : 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 Three propositions are proposed below and of these, only one is correct. Which one? a The graph G has 12 edges. b The graph G admits an Eulerian chain. c The graph G is complete. E.6295 Consider the following G graph : 1 Is the graph G connected? Explain the answer. 2 Does the graph G admit Eulerian chains? If so, specify one. 3 Justify the non-existence of an Eulerian cycle for the graph G . Which edge can then be added to this graph to obtain a graph containing an Eulerian cycle? E.6296 The graph below represents the plan of a city. The vertex A designates the location of the technical services. The vertices B , C , D E , F and G designate the locations of public gardens. A ridge represents the avenue connecting two locations. We are interested in the unweighted graph. Answer the following four questions without justification : a Is this graph connected? b Is this graph complete? c Does this graph admit an Eulerian chain? d Does this graph admit an Eulerian cycle? E.6329 Consider the graph opposite : 1 Using a table, give the degrees of each vertex of this graph. 2 Justify that this graph admits an Eulerian chain. 3 Justify that the following three chains are not Eulerian chains. a B − A − D − E − B − F − A − C − F − D b F − D − A − B − E − D − A − C − D − F c B − E − D − C − A − D − F − B − A 4 Give an Eulerian chain of this graph. https://chingmath.fr chapExoCorrec/6292 sacados/6292 ABCDEF chapExoCorrec/6293 sacados/6293 ABCDEFG chapExoCorrec/6294 sacados/6294 chapExoCorrec/6295 sacados/6295 Extrait d'Antilles-Guyane Juin 2009 ABCDEF chapExoCorrec/6296 sacados/6296 ABCDEFG chapExoCorrec/6329 sacados/6329 ABCDEF
E.6331 We consider a house composed of 6 rooms whose plan is given below : 1 By associating each room with a vertex, construct the graph G representing the house where the edges repre-sent the presence of a door allowing passage from one room to another. 2 Justify your answers : a Does the graph G admit an Eulerian chain? If so, write down this chain. b Does the graph G admit an Eulerian cycle? If so, write down this cycle. E.6338 The plan of a MJC (Maison de la Jeunesse et de la Culture) has been schematized below by a graph whose vertices are the rooms and edges are the pas-sages (doors, corridors or staircases) between the rooms. We call H the entrance hall and B the director’s office. At the end of the day, a duty officer goes round the MJC to collect from each room (director’s office and hall included) items forgotten by the children. 1 Specify whether this graph is connected, justifying the answer. 2 Determine, justifying, whether the service agent can pass through all the rooms using each passage once and only once. 3 The vertices are arranged in alphabetical order. Give the adjacency matrix M associated with the graph. 4 We give : M 4 = 31 15 26 21 27 18 12 15 12 15 12 18 12 6 26 15 31 18 27 21 12 21 12 18 20 17 18 5 27 18 27 17 34 17 16 18 12 21 18 17 20 5 12 6 12 5 16 5 10 Deduce the number of paths of length 4 between vertices B and H . E.6339 During an election campaign, a politician must tour the cities A , B , C , D , E , F , G , and H using the highway network. The graph G below shows the different cities on the tour and the highway sections connect-ing these cities (a city is represented by a vertex, a highway section by an edge) : 1 Determine, with justification, whether graph G is : a complet b connexe 2 a Justify that it is possible to organize the tour by passing through each city at least once, while using each highway section only once. b List a route of this type. 3 We call M the adjacency matrix associated with graph G (the vertices being taken in alphabetical order) . a Determine matrix M . b The matrix is given : M 3 = 0 5 3 5 1 1 4 1 5 2 7 2 8 3 3 5 3 7 6 4 9 3 9 10 5 2 4 0 9 2 3 8 1 8 9 9 4 4 10 4 1 3 3 2 4 2 6 6 4 3 9 3 10 6 6 9 1 5 10 8 4 6 9 4 Determine, with justification, the number of paths of length 3 connecting E to H . Specify these paths. 10. Labeled graph https://chingmath.fr chapExoCorrec/6331 sacados/6331 ABCDEF chapExoCorrec/6338 sacados/6338 Extrait Liban Mai 2014 ABCDEFH chapExoCorrec/6339 sacados/6339 ABCDEFGH
E.6390 To access his email, Antoine has cho-sen a code that must be recognized by the following labeled graph, with vertices 1 , 2 , 3 and 4 : A succession of letters constitutes a possible code if these let-ters follow each other on a path of the above directed graph, starting only at vertex 1 and exiting at vertex 4 . Codes SES and SPPCES are thus possible codes, unlike SUN and SPEN . 1 Of the following three codes, write on your copy the (s) code (s) reconnu (s) by the graph. SUCCES ; SCENES ; SUSPENS 2 Copy and complete the adjacency matrix A associated with the graph. We’ll take the vertices in the order 1 − 2 − 3 − 4 . A = 0 1 0 0 1 2 1 0 : : : : : : : : : : : : : : : : : : : : : : : : 3 Using a calculator, we calculated : A 4 = 5 12 8 3 12 29 20 8 0 0 1 1 0 0 0 0 Deduce the number of 4 letter codes recognized by the graph. What are these codes? 11. Dijkstra’s algorithm E.6372 During an election campaign, a politician has to tour the cities A , B , C , D , E , F , G and H , using the motorway network. The graph G below, represents the various cities on the tour and the sections of freeway con-necting these cities (a city is represented by a vertex, a section of freeway by an edge) : Organizational constraints force this politician to go to the city F after the city A . The graph G shows the lengths in kilometers of each freeway section. Using Dijkstra’s algorithm, determine the shortest motorway route from A to F . Specify the length in kilometers of this route. E.6373 Consider the graph G below. The number of seconds required to cover each edge is indicated : Using Dijkstra’s algorithm, determine the path that connects vertex G to vertex D in the minimum time. Determine this minimum time, expressed in seconds. E.6370 Consider the graph below, which shows the travel times for each of them. Determine the shortest chain connecting the vertices A and D . https://chingmath.fr chapExoCorrec/6390 sacados/6390 chapExoCorrec/6372 sacados/6372 ABCDEFGH400600600400350550450300900600200400300 chapExoCorrec/6373 sacados/6373 ABCDEFGHI304570603080503590256035402025 chapExoCorrec/6370 sacados/6370 ABCDEF45746742
E.6351 Consider the graph below : 1 a Construct the adjacency matrix M of this graph (vertices will be considered in alphabetical order) . b Using the calculator, determine the expression of the matrix M 3 . c Justify that there are 5 chains of length 3 connecting vertex A to vertex F ? Give these five chains. 2 The distances of each edge have been added to this graph. What is the shortest chain of length 3 connecting vertex A to vertex F ? E.6378 The director of the E company visits his suppliers, he travels from supplier A to supplier H and wants to travel as few kilometers as possible. His assistant draws up the following graph which diagrams the journeys, in kilometers, between the six towns in the re-gion, noted B , C , D , E , F and G and the two sites, A and H . Determine the shortest route connecting the two sites A and H and indicate the number of kilometers involved. Justify your answer. E.6379 Part of a ski area is represented by the graph below. The vertex A represents the top of the ski runs and the vertex I represents the bottom. The vertices B , C , D E , F , G and H represent crossing points. Each of the edges is weighted by the distance, in hundred meters, between two vertices. Using Dijkstra’s algorithm, determine the minimum distance to connect vertex A to vertex I . E.6385 A region is provided with a train network, represented by the graph Γ below. Stations are symbolized by the vertices A , B , C , D , E , F and G . Each edge represents a line connecting two stations. Travel times (including transfer) in minutes between each ver-tex have been added to the graph. 1 Determine the shortest path in minutes, connecting sta-tion B to station G . 2 What is the length in minutes of this path? https://chingmath.fr chapExoCorrec/6351 sacados/6351 ABCDEFG ABCDEFG4784274417585 chapExoCorrec/6378 sacados/6378 Extrait d'Asie Juin 2013 ABCDEFGH100175158114150956570107821133111249 chapExoCorrec/6379 sacados/6379 ABCDEFGHI7162113181581285651218713719 chapExoCorrec/6385 sacados/6385 ABCDEFG4871821102515123110177
E.6389 The collection points of a truck from a company recycling ˇ waste paper ı and the travel time (in minutes) between these points, are represented by the graph below. The depot is represented by vertex A and the other vertices represent the various collection points. The driver needs to get from the depot A to the collection point H . He is looking for the path that minimizes the travel time. Determine this path, explaining the process used, and specify the minimum travel time obtained. E.6116 Consider the graph G below, where the travel time, in minutes, to connect two vertices of this graph is indicated on each edge. Using Dijkstra’s algorithm, determine the path that connects vertex A to vertex F in the shortest possible time. E.6367 Consider the graph G below, where the travel time, in minutes, to connect two vertices of this graph is indicated on each edge. Using Dijkstra’s algorithm, determine the path that connects vertex A to vertex F in the shortest possible time. 12. Dijkstra algorithm with path equalities E.6374 The graph below shows all the taxiways used by aircraft at a given airport. These taxiways, on which aircraft taxi before or after landing, are called taxi-ways . The edges of the graph represent the traffic lanes (the ˇtaxi-waysı) and the vertices of the graph are the intersections. In the graph below, we have indicated the direction of traffic for aircraft in the different lanes, as well as the travel time for each in minute(s). 1 a Write the matrix M associated with this graph (ar-range vertices in alphabetical order) b Name all paths of length 3 connecting A to T . 2 The plane that landed at the end of the runway at A and must get to the terminal at T as quickly as possible. Determine the fastest route and give its duration. E.6368 Consider the graph below : What is the shortest path from vertex B to vertex H ? https://chingmath.fr chapExoCorrec/6389 sacados/6389 ABCDEFGH3711371143928104712 chapExoCorrec/6116 sacados/6116 ACBDEF155251475101811 chapExoCorrec/6367 sacados/6367 ACBDEF155257510186 chapExoCorrec/6374 sacados/6374 ABCDEFT4341;50;51230;50;50;540;5 chapExoCorrec/6368 sacados/6368 ABCDEFH24364135324
E.6369 Consider the following G graph : Using Dijkstra’s algorithm, determine the two shortest paths connecting vertices A and F . 13. Annales E.6232 A leisure park offers its visitors accrobranches courses. The various courses are modeled by the graph Γ below where the vertices correspond to the five trees marking their ends. Each route is represented by an edge of the graph and can be completed in both directions. 1 The leisure park organizer would like visitors to be able, if they so wish, to complete a full accrobranches itinerary, i.e. a route using each route once and only once and start-ing this route with tree number 1 . Justify that this wish is achievable and propose such an itinerary. 2 On note M the matrix associated with the graph Γ con-sidering the vertices taken in ascending order of tree num-bers. a Écrire the matrix M . b On gives, below, the matrices M 2 and M 3 . M 2 = 3 2 2 1 1 2 4 1 1 2 2 1 2 1 1 1 1 1 2 2 1 2 1 2 3 ; M 3 = 4 7 3 5 7 7 6 6 6 7 3 6 2 3 5 5 6 3 2 3 7 7 5 3 4 The leisure park organizer wishes to organize ˇ express ı itineraries that will start at tree number 1 , take three accrobranches courses and finish at tree 4 . These routes may take in the same course several times. Determine, justifying your result, the number of ˇ it-inéraires expressı réalisables (On do not ask to give these different itinéraires) 3 Pour complete these ˇ itinéraires express ı, one installs a giant toboggan on the tree 4 . The shape of this slide is modeled by a function f whose curve C is given below in an orthonormal frame. This curve passes through the points I , J and K with coordinates (2 ; 8.1) , (10 ; 2.5) and (20 ; 0) respectively. The function f is defined on 0 ; 20 by: f ( x ) = ax 2 + bx + c where a , b and c are three real numbers. a Justifier that a , b and c are solutions of the system : 400 a + 20 b + c = 0 100 a + 10 b + c = 2.5 4 a + 2 b + c = 8.1 b Déterminer the matrices X and V so that the previous system is equivalent to : U · X = V où U = 400 20 1 100 10 1 4 2 1 c Déterminer a , b and c . https://chingmath.fr chapExoCorrec/6369 sacados/6369 ABCDEF52441455241 chapExoCorrec/6232 sacados/6232 02468101214161820246810IJK
E.6423 The graph below shows the high-ways between the main cities in southern France : Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Mont-pellier (P), Brive (R), Toulouse (T), Valence (V) and Biarritz (Z). 1 For this question, justify each answer a Determine the order of the graph. b Determine whether the graph is connected. c Determine whether the graph is complete. 2 A tourist lands at Lyon airport and rents a car. Determine, with justification, whether he will be able to visit all the cities by taking each highway once and only once. 3 He finally decides to go only from Lyon to Biarritz. Let N be the matrix associated with the graph, with the vertices arranged in alphabetical order : B , C , L , M , P , R , T , V , Z . Here are the matrices N and N 3 : N = 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 N 3 = 4 2 1 1 3 6 6 1 5 2 0 5 2 8 6 1 1 3 1 5 0 2 1 0 3 5 0 1 2 2 2 5 2 1 4 1 3 8 1 5 2 1 8 7 1 6 6 0 2 1 2 8 3 2 6 1 3 1 8 8 4 1 6 1 1 5 4 7 3 1 2 1 5 3 0 1 1 2 6 1 2 a Detailing the calculation, determine the coefficient of the third row and last column of matrix N 4 . b Give an interpretation. 4 The toll prices in euros are now indicated on the edges of the graph. a Using Dijkstra’s algorithm, determine the route the tourist should take to minimize the cost of tolls from Lyon to Biarritz. b Determine the cost of this trip in euros. E.6402 In the game ˇ Save the Princess ı, , the objective is to rescue a princess while collecting treasures located in the corridors of the châateau. The layout of the châateau is represented by the weighted graph below. The vertices of this graph represent the rooms, and the edges represent the corridors connecting the rooms. Part A 1 The player is in room A . They decide to visit each of the corridors in order to find as many treasures as possible. Can he find a route that allows him to pass through all the corridors once and only once? Justify your answer. 2 In each corridor there are a certain number of monsters. The labels on the weighted graph indicate the number of monsters present in the corridors. The player wants to start at A and reach the princess locked in room G . Determine the path he must take to rescue the princess while fighting as few monsters as pos-sible. How many monsters would he have to face? Part B For a regular player, it is estimated that : if he wins a game, the probability that he will win the next game is 0.7 ; If he loses a game, the probability that he will lose the next game is 0.6 We denote P n = u n v n the probabilistic state during the n th game, where u n denotes the probability that the game will be won and v n the probability that the game will be lost. 1 Translate the data in the statement into a probabilistic graph. We will name the vertices U (for the game won) and V (for the game lost) . 2 Deduce the transition matrix by considering the vertices in order U , V . https://chingmath.fr chapExoCorrec/6423 sacados/6423 Liban Mai 2013 ZBTRCPLVM ZBTRCPLVM4;4019;6017;5011;5014;6019;6011;508;6010;7016;209;407;1015;70 chapExoCorrec/6402 sacados/6402 Extrait d'Antilles-Guyane Septembre 2014 ABCDEFG573112141414819
3 We assume that the first game is lost, so the initial prob-abilistic state is P 1 = 0 1 . Show that the probability that the player wins the 3 e game is 0.52 . 4 Determine the probability that the player wins the 15 e game. Round the result to two decimal places. 14. Unclassified financial years E.6115 Consider the graph G below : 1 a Determine and justify whether the graph G is com-plete. b Determine and justify whether the graph G is con-nected. 2 a Give the degree of each vertex of the graph G . b Determine and justify whether the graph G has an Eu-lerian cycle or an Eulerian chain. 3 Let M be the matrix associated with graph G (the ver-tices will be arranged in alphabetical order) . The following two pieces of information are given : M = 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 M 2 = 4 2 2 1 2 2 2 1 1 2 5 1 3 1 1 1 2 0 2 1 4 2 1 1 1 2 2 1 3 2 4 1 1 0 1 0 2 1 1 1 2 2 0 0 0 2 1 1 1 2 2 0 0 0 2 1 1 0 0 0 3 2 1 1 2 2 1 0 0 2 4 1 1 0 2 0 0 0 1 1 2 Determine, by calculation, the coefficient of the seventh row and fourth column of the matrix M 3 https://chingmath.fr chapExoCorrec/6115 sacados/6115 ABCDEFGHI