” Math 160程序 写作、data课程程序 辅导Math 160 (Spring Quarter 2020) Homework Project 4 (Combinatorial Optimization Models)Due date: 06/04/2020, 11:59pmINSTRUCTIONS All homework projects need to be done individually. No teams can be formed. All homework projects will have many problems, both theoretical and practical. Submit your homework project to Canvas as one single pdf file. In this project, you dontneed to submit your codes. Note that since MAT-167 is a prerequisite, concepts/terminology/results related to MAT-167are presumed. Knowledge on using MATLAB is presumed. Write legibly preferably using word processing if your hand-writing is unclear. Be organized and use the notation appropriately. Show your work on every problem. Correctanswers without support work will not receive full credit.1. Math models for UC Davis Advising: The optimal order of enrolling in courses!A directed graph G = (V, A) can be used to represent the order of actions to be take in anyproject (task a needs to be done before b, if there is an arc from a to b). A topological orderingof the vertices is an assignment of the value yi to each vertex such that for every arc ij thenyi yj + 1. The assignment says the best order to do a project.(a) Show that a directed graph has a topological ordering, then there is no directed cycle.Write a simple discrete model To detect whether a directed graph has a cycle.(b) A UC Davis student in major X (say applied math major, economic major, etc.) hasto take certain required courses that have pre-requisites. Create a directed graph whosenodes are all possible Math courses in each of the majors and there is an arc from coursea to course b if course a is a pre-requisite to b, thus a has to be taken before b! How big isthis graph? Let us call this the Math-Major-course graph, MMC Make some commentsabout the structure of the MMC graph (number of nodes? number of arcs?). How doesthe graph differs from a stats majors graph?Math 160作业 写作、data课程作业 辅导、MATLAB程序设计作业调试、 辅导MATLAB语言作业(c) Write a math model that, given one of the 3 majors of the UC Davis mathematicsdepartment, tells the students at least one good order, one that does not skip prerequisites,in which to take their math courses and graduate in minimum amount oftime. Assume that there is a limit of two math courses to take each quarter. Can youfind at least two good orders in each of the majors?2. Finding the best path: Here are some some challenges about optimal paths:(a) Let G be a directed graph With distances or costs on its arcs and two special verticess, t. We are interested on the longest paths using two possible definitions: (a) If wecall the length of a path the sum of the lengths on the path. Write a model to computethe longest path on a network. (b) If we instead call the length of a path the largestlength among all the arcs in the path, write another model to compute the longest pathon a network under this definition.(b) Let G be a graph with two distinguished vertices s, t. An even st-path is a path froms to t with an even number of edges. Describe a computer algorithm to find a shortesteven st-path (one with as few edges as possible).HINT: Not easy to use the st-path formulation in class. Instead you can reformulateas a minimum cost perfect matching problem! Construct an auxiliary graph H from G,make a copy of the graph G, and remove vertices s, t. Call that new graph G0. ConstructH starting with the union of G, G0 and joining every vertex v G different from s, twith its copy in G0. Use H.(c) Consider again, the TSP for n cities and cost of travel cij .(a) Write a new model for the TSP, different from the ones we saw in class. This timeuse the binary variables xi,j,k, where it equals 1 if the k-th leg of the trip, the salesmangoes from city i to city j. Your formulation must have a cubic number of constraints.What are they?(b) Given a graph G = (V, E) representing say the cities of California connected byhighways, we wish to find out whether there is a tour of the vertices of G (a cyclevisiting each vertex exactly once) which only uses the existing edges in E. Suppose youhave a powerful software that solves the Traveling salesman problem. How would youuse that algorithm for the TSP to answer that question? What costs should you pickon arcs?如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
