题库网 (tiku.one)

 找回密码
 立即注册

 

      

上传图片附件

未使用图片

小贴士: 允许的图片文件格式为: gif, jpg, jpeg, png, webp,上传完成后会在上方生成预览,用鼠标连续双击缩略图,或拖动缩略图,该图片就被绑定至本题,显示在题目下方

本次作答已使用

小贴士: 此栏目显示的是当前作答使用的所有图片,绑定到某一题目的图片同时会显示在该题目下方; 删除使用的图片会将其转移到<未使用图片>类别


习题练习:IB MAI HL Geometry & Trigonometry Topic 3.7 Graph Theory



 作者: admin   总分: 19分  得分: _____________

答题人: 匿名未登录  开始时间: 24年02月25日 22:19  切换到: 整卷模式

标记此题
1#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
George, an experienced civil engineer, is designing a high5ogn r (tv1.nd-speed railway network to connect seven cities (A-G), as illustrated in the graph below. The nvn1tord. (5 gpossible railways and costs of building them are represented by the graph edges, where costs are in billions of dollars.


George needs to design the lowest cost high-speed railway network that will connect the seven cities. Each city does not need to directly connect with all other cities, however each city must have a connection to the rail network.
1.Name an algorithm which will allow George to find the lowest cost high-speed railway network.
2.(1)Find and list the railway connections of the lowest cost high-speed railway network.
(2)Hence, write down the cost of building this network.
参考答案:    

标记此题
2#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A local government is planning to connect nine nearby mountain villages (A-I)gpb1f+dt 6ch: n tnr00 to a new local airport (O) with roads, a fnbg +rcp dt:00htn16s illustrated on the graph below.

The numbers on the graph edges represent the distance in kilometres between the villages and airport.


Every village does not need to be connected directly, however it must be possible to traverse to the airport from any village.
1.Determine the most efficient way to connect the villages to the airport.
2.Determine the total length of road the local government will need to build.
参考答案:    

标记此题
3#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
Omni Communications Inc. is planning to connect six cit7qyx k ri- 5q1szdqk4;ies (A-F) with a fibre optic network. Due to the high speed of information trs45q1qkzdi r;kx q- 7yansfer over a fibre optic network, each city does not need to be connected directly to each other.
The numbers on the graph below indicate the cost, in thousands of dollars, for each possible connection between the cities.



Determine the network of cables that will minimize the total cost of connecting these six cities to the fibre optic network, and the associated cost.
参考答案:    

标记此题
4#
 
填空题 ( 1.0 分) 切至整卷模式 搜藏此题  
  Peter is a salesman who works for a skin care prod1kj ux4xti m,zc87s/ g52qgx jucts company. He travels to a nearby city to find new customers. He research/28c7j x15im4jt,xg zksuqx g es six beauty salons on Yelp and pins their locations on Google Map.

The numbers on the graph below indicate the travel times in minutes between Peter's hotel (at A) and the beauty salons (B-G).

Peter is currently located at his hotel and wants to visit each beauty salon once, before returning to the hotel.


1.Write down the term which is used to describe this type of route.

Peter decides to visit beauty salon E first.
2.Find the route that he can take.

3.Calculate the total travel time, in hours and minutes, for his route.    hours    minutes

参考答案:     查看本题详细解析

标记此题
5#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A biotechnology company is investv(dfrz+-c 2 onigating the costs of building a fibre optic network to connect the 8 research labs it owns. The weighted graph below shows the labs (A-H) and the cost, in o(v-+cr fndz 2thousands of dollars, for building each connection.
Due to the fast information flow provided by fibre optic networks, the company decides that each lab does not need to be directly connected to each other, however each lab needs to have a connection to the overall network.

1.(1)Using Kruskal's algorithm, find a minimum spanning tree for the graph. Clearly indicate the order in which the edges are added to the tree.
(2)Hence draw the minimum spanning tree for the graph.
2.Find the minimum cost of building the fibre optic network.
参考答案:    

标记此题
6#
 
填空题 ( 1.0 分) 切至整卷模式 搜藏此题  
  A team of network technicians at a cloud stora8s35) e0jm ljii bl9ahr3fq(c ge company randomly move between data centers A, B, C and D, with prilb5lq8 03rmih)a9sfj(cje3 obabilities shown on the graph below.

1.Find the value of p and the value of q. p =    q =   
2.(1)Complete the weighted adjacency table below.

(2)Hence write down a transition matrix A for the graph.
3.Given that the team is currently in data center C, find the probability that they will return to C after visiting exactly two other data centers.

参考答案:     查看本题详细解析

标记此题
7#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A postman starts at the Post Office located at O and needs f/hi 0vzttwxhv7 ;/y4i.b g d sv(g;8ito travel along every road illussx.48gv(/fwvyt; dv/hb g7 0i ti;hzitrated by the edges in the graph below. The numbers on the graph represent distances in kilometres.

1.Find a solution to the Chinese Postman Problem for the graph.
2.Write down the length, in kilometres, of an optimal Chinese postman route.
参考答案:    

标记此题
8#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A package delivery company offers 24 hours delive4mbutof*6bi 8 ry service to a limited number of cities in close proximity. The directed graph below shows four cities served (A-D) and the r6m bti o8fb4u*outes of delivery between them.



1. Find an adjacency matrix $\boldsymbol{A}$ for the shipping network.
2. Find the number of ways it is possible to ship a package from city $\mathrm{C}$ to city $\mathrm{A}$ using exactly three delivery routes.
3. (1) Find the matrix $\boldsymbol{S}_{3}$ , where $\boldsymbol{S}_{3}=\sum_{i=1}^{3} \boldsymbol{A}^{i}$ .
(2) Hence write down the number of ways it is possible to deliver a package from city A to city D using three or less delivery routes.
(3)State all possible ways to ship a package from city A to city D using three or less delivery routes.
参考答案:    

标记此题
9#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The graph $\boldsymbol{G}$ as the adjacency matrix $\boldsymbol{M}$given below.



1. Draw a possible graph of $\boldsymbol{G}$ .
2. Interpret the meaning of the diagonal elements of $\boldsymbol{M}^{2}$ , with regards to $boldsymbol{G}$ .
3. Find the number of walks of length 4 starting at A and ending at D .
4. List the two trails of length 4 starting at A and ending at D .
参考答案:    

标记此题
10#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The tourism and travel company, Zeppelin Adventurep0 rlsknh jt0g5. ;pe3 vg)8wf, provides airship trips between five cities of e0 0hnp; fvt3sgwp5kg) lj. 8rSpain. The airship trip routes are shown on the map below.



1. Write down the number of trip routes offered.
2. Find an adjacency matrix $\boldsymbol{A}$ for the airship trips network.
3. Find:
(1) the number of routes, m , between two cities that cannot be made using at most one stopover.
(2) the maximum number of trips, k , needed to fly between any two cities.

Zeppelin Adventure is considering offering a new trip option for customers. They are considering either a new route from Barcelona to Valencia, or make the route between Madrid and Zaragoza two -way.
4. Determine the route that minimises the value of m , from part (c) (i).
参考答案:    

标记此题
11#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A postman starts at the Post Officf(uvi r f spb /32pqp1ty2pk+-e located at O and needs to travel along every road illustrated by the edges in tu( f+v-rbpy p t2/skpi1f 3pq2he graph below. The numbers on the graph represent distances in kilometres of the roads.



1. Find a solution to the Chinese Postman Problem for the graph.
2. Write down the length, in kilometres, of an optimal Chinese postman route.
参考答案:    

标记此题
12#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The complete graph $\boldsymbol{K}$ has the following weighted adjacency table.



Consider the travelling salesman problem for $\boldsymbol{K}$ .
1. By first finding a minimum spanning tree on the subgraph of $\boldsymbol{K}$ formed by deleting vertex $\mathrm{A}$ and all edges connected to $\mathrm{A}$ , find a lower bound to this problem.
2. Find the total weight of the cycle ABCEDA.
3. State a conclusion from your results found in part (a) and part (b).
参考答案:    

标记此题
13#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The weights of the edgesa ro(pduu3f+- of a graph $\boldsymbol{H}$ are given in the following table.


1. (1) Draw the weighted graph $\boldsymbol{H}$ on the vertices below.


(2) Using Kruskal's algorithm, find a minimum spanning tree for $\boldsymbol{H}$ . Clearly indicate the order in which the edges are added to the tree.
(3) Write down the weight of the minimum spanning tree.

Consider the following weighted graph $\boldsymbol{J}$ .



2. (1) Find a solution to the Chinese postman problem for the graph $\boldsymbol{J}$ .
(2) Write down the total weight of the solution.
3. (1) State the travelling salesman problem.
(2) Explain why there is no solution to the travelling salesman problem for the graph $\boldsymbol{J}$ .
参考答案:    

标记此题
14#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The weighted graph $\boldsymbol{H}$, representing the travelling costs between five customers, has the following weighted adjacency table.


1. Draw a possible graph of $\boldsymbol{H}$ .
2. Starting from customer $\mathrm{E}$ , use the nearest-neighbour algorithm to determine an upper bound to the travelling salesman problem for $\boldsymbol{H}$ .
3. By removing customer A, use the method of vertex deletion to determine a lower bound to the travelling salesman problem for $\boldsymbol{H}$ .
参考答案:    

标记此题
15#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
A baker, starting a business baking bread and muffins, plans to visit 5 nearby fzjfd5u aec1 -ev; gvv6 m+0o0o7gcr-cafes (A-E) to enquire if they want to stock her goods in their cafes. The distances between the cafes, in-6ocg veam+1 gcd; 0r-v ofejvu075zf km, are shown in the following weighted adjacency table.

1.Draw a possible graph for this weighted adjacency table.
2.Starting from cafe C, use the nearest-neighbour algorithm to determine an upper bound to the travelling salesman problem for this graph.
3.By removing cafe E, use the method of vertex deletion to determine a lower bound to the travelling salesman problem for this graph.
参考答案:    

标记此题
16#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
Every night a street cleaner is tasked with cleaning the s /g*jfttd*qg2x68;n f kl p2rxtreets in his designatex; 82k g6*f p/ xdrnf2*jtltqgd area.
The diagram below shows his designated area, with the weights indicating the time, in minutes, it takes to clean each street, and intersections indicated by letters.



The street cleaner must clean every street and wishes to minimise the time the task will take.
1. The street cleaner starts and finishes at the company depot, located at point K. Determine the total time it will take him to complete his task.

A new road is to be constructed directly from the intersection at point B to the intersection at point G, and it is estimated that this street will take 25 minutes to clean. The street cleaner has also been told he can now start the job at any intersection, and finish at any other intersection, and another employee will pick him up and drop him off.
2. Determine the difference in total time the job will take once the new road is completed.
参考答案:    

标记此题
17#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The distances by road, in kilomeayo*4vbu za+)vh 4. aytres, between six cities in the Netherlands are shown in the foloh 4zuv*y)4 avaa.+ yblowing table.



A telecommunications company has gained approval to connect the six cities with fiber optic cabling along the road system.
1. Using Kruskal's algorithm, calculate the minimum length of fiber optic cable needed for all six cities to be connected to the fibre optic network.

Visitors to the Netherlands can travel between cities on a train network represented by the following graph.



2. State, justifying your answer, whether the graph has any Hamiltonian:
(1) paths;
(2) cycles.
3. State, justifying your answer, whether the graph has any Eulerian:
(1) trails;
(2) circuits.

Clare plans to visit the Netherlands. She wants to arrive in Eindhoven, travel all the available train routes exactly once, and then depart from Amsterdam.
4. Find the route between two cities Clare will need to travel by an alternate method of transport in order to make this possible.
参考答案:    

标记此题
18#
 
问答题 ( 1.0 分) 切至整卷模式 搜藏此题  
The weights of the edges in the 4bk (lpe4gbdnp6uv6+o j )4aa complete graph $boldsymbol{G}$are given in the following table.


1. Starting at vertex A, use the nearest-neighbour algorithm to find an upper bound for the travelling salesman problem for graph $\boldsymbol{G}$.
2. By first deleting vertex A, use the deleted vertex algorithm together with Kruskal's algorithm to find a lower bound for the travelling salesman problem for $boldsymbol{G}$ .
参考答案:    

标记此题
19#
 
填空题 ( 1.0 分) 切至整卷模式 搜藏此题  
  The table below shows the costs, in euros, of the directfp8 et kd225dd bus rides between six towns (A-F). Cells with dashes indicate that there are no direct bus rides between the two townsf825dt epdk d2.




1. Draw a weighted graph showing the direct bus rides between the towns and their costs.
2. (1) Write down the adjacency matrix for the graph of direct bus rides between the towns.
(2) Hence find the number of different ways to travel from and return to town F in exactly 6 bus rides.
3. State whether it is possible to travel from and return to town \mathrm{F} in exactly 6 bus rides, having visited each of the other 5 towns exactly once.
The following table shows the minimum cost to travel between the six towns. A travelling salesman wants to visit each of the six towns, starting and finishing at town F.



4. Find the value of p and the value of q .p =    q =   
5. Use the nearest-neighbour algorithm to find an upper bound for the cost of the travelling salesman's trip.    euros
6. By deleting vertex F , use the method of vertex deletion to find a lower bound for the cost of the travelling salesman's trip.   euros

参考答案:     查看本题详细解析

  • :
  • 总分:19分 及格:11.4分 时间:不限时
    未答题: 已答题:0 答错题:
    当前第 题,此次习题练习共有 19 道题
    本系统支持习题练习,作业与考试三大模式,作业考试自动评分,成绩排序一键导出,可设定动态变量同一试卷千人千题
    如果您对本系统感兴趣,想加入我们或者想进行任何形式的合作,请加微信 skysky1258

    浏览记录|使用帮助|手机版|切到手机版|题库网 (https://tiku.one)

    GMT+8, 2024-12-25 15:54 , Processed in 0.139728 second(s), 59 queries , Redis On.