Unit 4 Exam- Networks

Question 1

What is the statement when proving the Hungarian algorithm reasonableness?

Answer 1

It is mathematically proven that the Hungarian algorithm will allocate tasks in the minimum time if performed correctly. Therefore, this solution is reasonable.

Question 2

What must you always do before using a method?

Answer 2

Always state the method you are using.

Question 3

How do you state the degree of a node?

Answer 3

Deg (B)=4
Deg (D)=2

Question 4

What are connected and disconnected graphs?

Answer 4

In connected, each vertex is directly or indirectly connected to all other vertices.

In disconnected graphs, there are random disconnected segments.

Question 5

What are bridges?

Answer 5

If an edge is removed, the graph becomes disconnected. This can include if there are multiple nodes connected, but it is still disconnected from the whole thing.

Question 6

What is a complete graph?

Answer 6

A simple graph (no loops or multiple edges) where every vertex is directly connected to every other vertex.

Question 7

In an adjacency matrix, what does each number represent?

Answer 7

0 means no connection, 1 means connection, 1 can also be a loop on one vertex, and 2 is a multiple edge.

Question 8

What is a tree diagram?

Answer 8

A connected graph with no loops, multiple edges, or cycles.

Question 9

What is a walk, trail, path, and cycle?

Answer 9

-Walk: any sequence of connected edges. They can be open or closed (open is when they start and end at same vertex)
-Trail: a walk where there are no repeated edges but can have repeated vertices. (can be open or closed)
-Path: no repeated edges and no repeated vertices (these are open).
-Cycle: A cycle is the closed version of a path.

Question 10

What methods are used for spanning trees?

Answer 10

• you know its a spanning tree when they want all vertices connected or they state they don’t want any loops or cycles.
• Prim’s algorithm is used for this
• You can also do spanning trees given a table

Question 11

What methods are used for flow networks?

Answer 11

*For this, they will usually ask for the maximum flow.
- Many paths method.
- Cuts method.

Question 12

What methods are used for shortest path questions/ weighted networks?

Answer 12

*Usually involves finding shortest route/ travelling situations.
- Network diagram approach.
- Guess and check method.

Question 13

What methods are used for allocation problems?

Answer 13

*Questions are usually based on who can perform tasks and who cannot and these times.

*Times given:
- Hungarian method
- Or using tree diagrams and adding the minutes.

*No times given
- Bipartite graphs are used.
- Evaluation matrix are creates from these graphs (1= can do action).

Question 14

What methods are used for project networks?

Answer 14

*Involve steps that must be taken in a project, and usually the times these take.

-Activity networks: activities and immediate predecessors are in a table- usually required to graph this.
-Forward and backward scan (from graph to table)

Involves: finding dummy activities, critical path, est, lft, lst, and float time.

Question 15

Note about these methods:

Answer 15

Always state the method you’re using and include a key if needed.

Question 16

For the cuts method, how do you know if an arrow pointing directly up or down is considered to be flowing from source to sink?

Answer 16

Focus on the nodes instead on the edges. When the edge is cut, is the top node on the source side of the cut or the sink? if the top is on source and bottom is sink, then it is included.

Question 17

When do I do a column reduction in the Hungarian method?

Answer 17

• only do a column reduction on the columns that have no zeros in them and aren’t previously covered by the row reduction.

Question 18

What is something to remember for the last step of the Hungarian method?

Answer 18

You circle the smallest number, but you also subtract from the one that is circled (so it should become zero).
Add onto the numbers with two cross sections and subtract from the uncovered numbers.

Question 19

What are the steps of the critical path for project networks?

Answer 19

1. Plot the project network from the nodes and immediate predecessors.
2. Add the boxes with a key (left is EST and right is LST)
3. Do a forward scan *remember the first box should be 0 (you look for bigger no. when two goes into one)
4. Now do a backward scan (look for smaller no. when two goes into one)
5. Write the minimum time
6. Make up the table with: activity, duration, EST, LST, and float time.
7. draw and write the critical path.

Question 20

For project networks, how do you know when you have to chose from multiple paths for one box?

Answer 20

If there are multiple going into the same one and you must fill out that one because there isn’t another box along the way. Sometimes it looks like multiple going into the same one but its not, just because they are connecting from weird angles.

Question 21

How do you know EST?

Answer 21

This is the left hand side of the box. You will use the box coming before the edge. e.g., the first activity with no IP’s will be 0.

Question 22

How do you know LST?

Answer 22

LST is the right hand side of the box, but you pick the box coming AFTER the action instead of before.
THEN you subtract the duration of the action from that number.

Question 23

How do you know float time?

Answer 23

Float time is LST-EST.

Question 24

How do you know something is on the critical path?

Answer 24

If the float time is 0 or if the left hand side of the box is the same as the right hand side, this is the critical path.

Question 25

How do you know the critical path on a multiple choice question?

Answer 25

The critical path is always the longest path. Use the guess and check method to find the longest path.

Question 26

How do you do the many paths method?

Answer 26

• Fill out your first path of choice in one colour.
• Find the smallest number out of this path. Then, cross that number and mark it zero. Then, put lines through this and it cannot be crossed again.
• subtract the smallest value from every number on this path.
• list this number on the side in that colour saying “maximum flow”
• repeat and continue adding up the maximum flow numbers.

Question 27

How do you do a minimum spanning tree?

Answer 27

• Start out on any line and draw dashes across the edge.
• Connect to the next smallest no. until you have connected EVERY NODE
• remember you cannot make any loops or cycles and if it crosses over itself you have to go the other way.
• add all these numbers up to find minimum time.

Question 28

In a project network, what do you do if an activity doesn’t connect to an end node or there are more than one activities without immediate predecessors?

Answer 28

You are able to create your own “start” or “finish” node and connect everything to that. You cant just have activities floating without ending.

Question 29

If it asks for a planar graph, what do you do?

Answer 29

Make a graph where there are no overlaps, and also use directions likely from an adjacency matrix.

Question 30

What is the inspection method for allocation?

Answer 30

• When given a matrix with the weight of tasks, create a bipartite graph if it helps.
• Then, create a tree diagram of all the
  possibilities of choosing an allocation, then add these sequences up to find the lowest one.

Question 31

When do you use a dummy?

Answer 31

So, say there is a node called “node 1” with two immediate predecessors going into it. Lets say C and D are going into it. However, you look and see that C is somewhere behind another activity and cannot be connected that way. That means it must be a dummy, and you would connect the dummy from C, into the activity that directly connects to the “node 1”

Question 32

How do you make a minimum spanning tree given a table?

Answer 32

• First, scan the full table for the lowest number there.
• Look at the table to see what connection these represents, for example, A-B, and plot this with the weight.
• Scan the table and look for the next smallest number connecting to either A or B and plot the next connection.
• keep doing this until all nodes are connected.
  -REMEMBER you cant make any loops or circuits.