help3001

It's UWAweek 47

help3001

This forum is provided to promote discussion amongst students enrolled in CITS3001 Advanced Algorithms.

Please consider offering answers and suggestions to help other students! And if you fix a problem by following a suggestion here, it would be great if other interested students could see a short "Great, fixed it!" followup message.

How do I ask a good question?

Displaying the 2 articles in this topic

Showing 2 of 202 articles.
Currently 17 other people reading this forum.

UWA week 42 (2nd semester, week 12) ↓

Lecture 16, Cutting the graph (both)

11:07pm Sun 20th Oct, ANONYMOUS

Hi, I have a question regarding the Lecture 16, on the video recording in LMS, timestamp 1:23:11 It was said that the cut on the saturated graph shown as the example would be {S,A,C,D} and {B,T} And it was said that the Source Vertex could reach A C D however could not reach B. I do not understand how this was obtained as the direct edges from Source Vertex only reached A C, not D. Could someone please help clarify? Thanks in advance

UWA week 43 (2nd semester, study break) ↓

Lecture 16, Cutting the graph (both)

12:46pm Mon 21st Oct, Andrew G.

ANONYMOUS wrote:

I have a question regarding the Lecture 16, on the video recording in LMS, timestamp 1:23:11 It was said that the cut on the saturated graph shown as the example would be

{S,A,C,D} and {B,T}

And it was said that the Source Vertex could reach A C D however could not reach B. I do not understand how this was obtained as the direct edges from Source Vertex only reached A C, not D.

Reachability is transitive. s is able to reach d via c. The core point is that the s side of the cut will be exactly those vertices that are reachable from s through the residual graph. That is, the vertices to which s could push flow. This because it means that we can get flow to any vertex in the s-component, and so if any of them have an (unsaturated) edge to something in the t-component, then we could push more flow across the cut.

help3001 articles all ANNOUNCEMENTS recent articles login to post a new article help3001 topics from today and yesterday from the past week from the past two weeks ALL topics, most recent first	login chapter0 unitinfo research projects csforum csse-feedback csbreakdown cssubmit csmarks 2nd semester help fora Algebra Advanced Algorithms Cloud Computing High Performance Computing Intelligent Agents Professional Computing Relational Database Management Systems Systems Programming