Network Flows Case Study
First, starting at s, four gallons per minute are released and split in half at point a, but as the top dark blue path to b allows for three gallons it was tested if three gallons were utilized through he top to either conclude if three gallons would reach the ending destination or be hindered early on.
After reaching b and continuing to g the gallons allotted for the dark blue path lowers to 1, as well as from g to h allowing for 1 gallon. Therefore, from the top dark blue path only one gallon of water Is allowed to pass through to t and two more gallons must be accounted for.
Next, going back to where the original four gallons split at point a, the dark green path would be followed. From point a to point d two gallons are allowed through, and from d to f only one gallon Is allowed to ass along the dark green path. As the amount has been lowered to one gallon the amount of water passed from point f to h and then to point t is one gallon.
As one gallon plus one gallon is less than three gallons the last gallon must be accounted for through the broken down areas in the middle where the gallons allowed were restricted greatly.
As the path from point g to h only allows one gallon it can be eliminated as an option for allowing any additional gallons through the light blue path, leaving point f to point h as the only other option to have the remaining gallon pass through. The most logical option is to utilize the light green path going from c to d with one gallon allowed though. From d to e one gallon is allowed to pass through, and the same Is for e to f. For the path from point f to h there Is two gallons allowed and only one utilized through the dark green path, leaving the second gallon option for utilization by the light green path.
The light green path would continue from h to t completing the path for the third gallon of water passing though, conforming Joe ten plumbers through this system. Example 2 statement a tenure gallons per minute can De passed The smallest amount of mines needed to block access from inland town s to the sea through the river Delta system is seven mines. This was determined by working from left to right, as colored above, adding the amounts of mines needed to eliminate the connection in each section.
Starting with the red paths it was determined that 15 mines would be needed, followed by the orange path determining 11 mines would be needed to block off those three paths. The green paths eliminated would require only seven mines, and while that is the answer to this problem it is detrimental to eliminate all other options for the clocking of paths for this river. The dark purple paths show that nine mines would be required to destroy the path at that area.
The blue paths, while overlapping with some of the purple paths, are more numerous with needing 13 mines to destroy the path.
The brown paths would require 15 mines to block off the river. After the brown path there are no additional option for blocking off the path to the sea. With the knowledge of all the possibilities it can be determined that the lowest amount of mines required is seven mines for the green tat. These mines will need to be placed between points d and g, e and g, e and h, f and h, and between f and I as shown in the diagram colored in green above.
Example 3 At Major University the graders hired have specific courses they are capable of grading with amount wanted to grade as maximum.
Meanwhile, Professor Johnson has the requirements of how many of each section must be graded and can use less than the maximum of the students’ requested maximum amount to complete the courses needed. There are several different ways to resolve this problem. Below is a gram of all possibilities to fulfill the above requirements of courses while also not going over the maximum sections requested by the graders. These solutions are color-coded based on the student graders and can only grade the sections they are approved to grade.
The red numbers represent Student 1, green represents Student 2, and purple represents Student 3. CLC, CA, CA, and CA represent their respected course numbers. The solutions in the boxes are which specific course the student will grade in order to reach the requirements for the courses needing to be graded. The chart above the solutions represents how many sections each student will be completing in order to reach the total seven sections to be graded. If Professor Johnson was looking for the solution that had the amount of courses and variety at its peak then there is one solution that would fit the best.
The best fit is the third listed on the left showing Student 1 grading two Course 1 and one Course 2, Student 2 grading one Course 1, one Course 4, and Student 3 grading one Course 3 and one Course 4.
This one is the best fit because it is the only solution that has every student long exactly two separate types AT courses. The other solutions are most likely not preferred as they have students grading only one course, three of the same course, or three different courses while another student is only doing one course or three of the same course.
The least likely used solutions are going to be the third column’s solutions has Student 2 never grades more than one section. Conclusions The lexicographic ordering rule is very useful in mathematical problems as well as programs. Lexicographic ordering is when a list of words are reordered to be in order alphabetically based on their component letters. This can also be used thematically by using Cartesian products, which pairs two rows in two tables to create combinations of the two.
This could have been used on Example 3 as all possibilities could have been calculated the same way. Capacitate s,t graphs are very useful when viewing the overall problem and trying to find ways to the solution. With these graphs we can find paths and the direction traveled based on the graph. These can be used for anything from plumbing to computer networks. By knowing all the connections in a network the ways the network can be broken down or incapacitated can become more easily visible.
As shown through example one and two the use of the capacitate s,t graphs can be used to find a solution to a problem by finding a way through the network or it can also be used to find ways to destroy the infrastructure.
This can be vital for the survival of a computer network, plumbing, roadways, and many other real-time scenarios. These problems could be used on a daily basis on the Job or within the daily business. From finding where in a circuit there is a broken fuse to finding how exactly to reduce the pressure of the sprinkler system that is overpowered, the use of s,t graphs are very important in our daily uses.
