这是一份多伦多大学 CSC373 网络流代写的案例，是一道图论的题目，规定要使用ford fulkerson算法。

An orientation of an undirected graph $G=(V ; E)$ creates a directed graph $G^{\prime}=\left(V ; E^{\prime}\right)$ by giving a direction to each undirected edge $e=(u ; v)$; that is, either $(u ; v)$ becomes a directed edge $(u ; v) \in E^{\prime}$ from $u$ to $\mathrm{v}$, or edge $(v ; u) \in E^{\prime}$ from $\mathrm{v}$ to $\mathrm{u}$. Consider the following graph orientation problem: Given: An undirected graph $\mathrm{G}=(\mathrm{V} ; \mathrm{E})$. Output: An orientation of $\mathrm{G}$ so as to minimize the maximum in-degree of any node. That is, we want to minimize $\max {v \in V}\left(\sum{(u ; v) \in E^{\prime}} 1\right)$.
Desribe a method to optimally solve this problem in polynomial time.
(a) (8 marks) Set up a bipartite graph involving edges and vertices of $G$ as a network whose flow can be used to solve the above problem.
(b) (4 marks) Show how max flow in network of (a) can be used to find the desired orientation.
(c) (4 marks) What is the run time complexity of your algorithm? You may assume knowledge of the run-time complexity of the Ford-Fulkerson algorithm.

Network flow in polynomial time

• Edmonds-Karp algorithm (shortest augmenting path)

Applications of network flow

• Bipartite matching \& Hall’s theorem
• Edge-disjoint paths \& Menger’s theorem
• Multiple sources/sinks
• Circulation networks
• Lower bounds on flows
• Survey design
• Image segmentation

Ford-Fulkerson Recap

• Define the residual graph $G_{f}$ of flow $f$
• $G_{f}$ has the same vertices as $G$

For each edge e $=(u, v)$ in $G, G_{f}$ has at most two edges

• Forward edge $e=(u, v)$ with capacity $c(e)-f(e)$
• We can send this much additional flow on $e$
  o Reverse edge $e^{r e v}=(v, u)$ with capacity $f(e)$
• The maximum “reverse” flow we can send is the maximum amount by which we can reduce flow on $e$, which is $f(e)$
• We only add each edge if its capacity $>0$

Ford-Fulkerson Recap伪代码

MaxFlow(
𝐺
// initialize:
Set
𝑓𝑒=0for all 𝑒in 𝐺
// while there is an
𝑠 𝑡path in 𝐺𝑓
While
𝑃=FindPathFindPath(s,t,Residual( 𝐺,𝑓))!=
𝑓=AugmentAugment(𝑓,𝑃)
UpdateResidual
𝐺 𝑓
EndWhile
Return
𝑓

real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

抽象代数Galois理论代写

偏微分方程代写成功案例

代数数论代考

概率论代考

离散数学代写

集合论数理逻辑代写案例

时间序列分析代写

离散数学网课代修

GENERAL COURSE INFORMATION

COURSE DESCRIPTION (FROM CALENDAR)

Standard algorithm design techniques: divide-and-conquer, greedy strategies, dynamic programming, linear programming, randomization, network flows, approximation algorithms. Brief introduction to NP-completeness: polynomial time reductions, examples of various NP-complete problems, self-reducibility. Students will be expected to show good design principles and reasonable skill at reasoning about the correctness and complexity of algorithms.

TEXTS (ONE OF THE FOLLOWING)

GRADING SCHEME AND TENTATIVE DATES

Midterm test will be held during tutorial slots, 16:00-18:00 (daytime section and 17:00-19:00 (evening section).

THE 20% RULE

You will receive 20% of the points for any (sub)problem for which you write “I do not know how to answer this question.” You will receive 10% if you leave a question blank. If instead you submit irrelevant or erroneous answers you will receive 0 points. You may receive partial credit for the work that is clearly “on the right track.” The 20% rule applies to all term work: assignments, term tests, and even the final.

ASSIGNMENT POLICY

Assignments will be submitted electronically on MarkUs (instructions will follow later). Late assignments will penalized as follows: All assignments are due by 4:59pm on their due date, unless otherwise stated. Late assignments are penalized by 2.5% per hour. After 40 hours your assignment will get a score of zero. Note that lateness penalties will be computed as a percentage of the total marks for the assignment, not of the mark you obtain. This policy will be strictly enforced.

REGRADING POLICY

If you believe that there was a significant mistake in how any question was graded, you may submit a one or two paragraph explanation (along with the original grading) as to why you believe the grade you received was a mistake. That explanation will be then re-considered by the grader. Please do not abuse this policy with minor complaints. Grading is subjective to some extent but we are trying to be as generous as possible. Clerical errors (i.e. grades not properly added or entered on Matrkus) can be rectified by the instructors.

COLLABORATION POLICY AND ACADEMIC INTEGRITY

You are allowed to discuss assignment questions with other students. You are allowed to consult additional materials, e.g., books, papers, websites. You may collaborate without restrictions with anyone on your team. The writeup of your solutions should be your own (or that of your team) and should be done in isolation from other students and resources. In addition, you must clearly identify the names of students (outside of your team) you collaborated with (if any) and provide a clear description of additional materials you consulted (if any). Once a team has been formed, it cannot be changed after the first submission.

The following rule of thumb might help you ensure that you are writing down your own understanding of a solution: (1) do not take notes following discussions with other studentsi or having read a solution on the internet, (2) after understanding a question, take a one-hour break before writing down the solution, (3) while writing down the solution do not consult any materials.

Copying or allowing other students to copy solutions is a serious academic offense and will be reported. You might find the Arts and Science website on academic honesty (and references therein) helpful.

EMAIL POLICY

We read email regularly, but we do NOT promise to reply to all emails. In particular, if your question is of general interest, it would be best to post it on piazza. We will not respond to general questions via email. We will address questions during the lectures, so that everyone can benefit. Similarly, if your question requires a technical answer it is better to ask it during a lecture, or a tutorial, or office hours.Use email for more personal or sensitive questions (e.g., requesting absense due to illness,etc.

ACCESSIBILITY

Students with diverse learning styles and needs are welcome in this course. In particular, if you have a disability/health consideration that may require accommodations, please feel free to approach me and/or Accessibility Services at 416-978-8060; http://accessibility.utoronto.ca.