Math 160 AssignmentHelp With ,data Course AssignmentGhostwriter ,MATLAB Programming AssignmentDebug ,Ghostwriter MATLAB Assignment
Ghostwriter WebGhostwriter C/C++ Programming
Math 160 (Spring Quarter 2020) Homework Project 4 (Combinatorial Optimization Models)
Due date: 06/04/2020, 11:59pm
INSTRUCTIONS
• 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 don’t
need to submit your codes.
• Note that since MAT167 is a prerequisite, concepts/terminology/results related to MAT167
are presumed.
• Knowledge on using MATLAB is presumed.
• Write legibly preferably using word processing if your handwriting is unclear.
• Be organized and use the notation appropriately. Show your work on every problem. Correct
answers 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 any
project (task a needs to be done before b, if there is an arc from a to b). A topological ordering
of the vertices is an assignment of the value yi to each vertex such that for every arc ij then
yi ≥ 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.) has
to take certain required courses that have prerequisites. Create a directed graph whose
nodes are all possible Math courses in each of the majors and there is an arc from course
a to course b if course a is a prerequisite to b, thus a has to be taken before b! How big is
this graph? Let us call this the Mathmajorcourse graph, MMC Make some comments
about the structure of the MMC graph (number of nodes? number of arcs?). How does
the graph differs from a stats major’s graph?
(c) Write a math model that, given one of the 3 majors of the UC Davis mathematics
department, 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 of
time. Assume that there is a limit of two math courses to take each quarter. Can you
find 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 vertices
s, t. We are interested on the “longest” paths using two possible definitions: (a) If we
call the length of a path the sum of the lengths on the path. Write a model to compute
the longest path on a network. (b) If we instead call the length of a path the largest
length among all the arcs in the path, write another model to compute the longest path
on a network under this definition.
(b) Let G be a graph with two distinguished vertices s, t. An even stpath is a path from
s to t with an even number of edges. Describe a computer algorithm to find a shortest
even stpath (one with as few edges as possible).
HINT: Not easy to use the stpath formulation in class. Instead you can reformulate
as 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
. Construct
H starting with the union of G, G0 and joining every vertex v ∈ G different from s, t
with 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 time
use the binary variables xi,j,k, where it equals 1 if the kth leg of the trip, the salesman
goes 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 by
highways, we wish to find out whether there is a tour of the vertices of G (a cycle
visiting each vertex exactly once) which only uses the existing edges in E. Suppose you
have a powerful software that solves the Traveling salesman problem. How would you
use that algorithm for the TSP to answer that question? What costs should you pick
on arcs?
Contact Us(Ghostwriter Service)
 QQ：99515681
 WeChat：codinghelp2
 Email：99515681@qq.com
 Work Time：8:0023:00

Cis 484 Assignmenthelp With ,Ghostwrit...
20200927

Ghostwriter Kit206 Course Assignment,H...
20200927

Comp2100 Assignmenthelp With ,Ghostwri...
20200927

Msbd5015 Assignmentghostwriter ,Python...
20200927

Programming Assignmentghostwriter ,Jav...
20200927

Cisc 360 Assignmenthelp With ,Ghostwri...
20200927

Cs 570 Assignmenthelp With ,Java Progr...
20200927

Help With Isys 1108 Assignment,Help Wi...
20200927

Data Assignmentghostwriter ,Java，C++ ...
20200926

Csc220 Assignmenthelp With ,Data Assig...
20200926

Ghostwriter Csc220 Assignment,Help Wit...
20200926

Bridging Coursework
20200926

Comp Sci 3004/7064 Operating Systems ...
20200926

Comp9311 20T2  Assignment 2
20200926

Ipal Capstone Project
20200926

Ipal Programming In R  Week 2 Assign...
20200926

Csc 503/Seng 474 Data Mining Assignmen...
20200926

Assignment 1 Cmpt 307
20200926

Csci 2300 Lecture Exercise 5
20200926

Csci 2300 Lab 4
20200926
Contact Us  Email：99515681@qq.com WeChat：codinghelp2
Programming Assignment Help！