﻿ 留学生Cs代写 代写计算机科学 - CS代写, 作业代写

# 留学生Cs代写 代写计算机科学

2022-10-24 09:27 星期一 所属： CS代写 浏览：53

## Homework Assignment 5, due June 3 11:59PM

### 1 Last (5th) homeworkassignment

Work is to be your own. If you do use outside sources or help, be sure to cite them carefully.

### 1.1 Network Flow 1 (40pts)  留学生Cs代写

Show your knowledge of the Ford Fulkerson Network Flow Algorithm by carefully carrying out the steps on the graph pictures below. Use the Edmonds-Karp heuristic, which is the rule that each augmenting path should use as few edges as possible. Indicate your sequence of steps. State the current flow amount after each augmenting path.

### 1.2 Running Time (10pts)

What is the (published) big-Oh running time for the above version of network flow on a graph with n vertices and edges?

### 1.3 Network Flow 2 (40pts)  留学生Cs代写

Show your knowledge of the Ford Fulkerson Network Flow Algorithm by carefully carrying out the steps on the graph pictures below. Use the rule that each augmenting path should use as few “reverse arcs” as possible. Indicate your sequence of steps.. State the current flow amount after each augmenting path.

### 1.4 Minimum Weight Cut (10pts)

Indicate a minimum-weight cut to separate s from t on the last picture.