Networks Assignment - maths year 12 assessment PDF

Preview

Summary

maths year 12 assessment...

Description

Networks

A Network is a term to describe a group or system of interconnected objects. There are many situations in everyday life that involve connections between objects.

Eulerian Circuit

A Eulerian Circuit uses every edge of a network graph exactly once and starts and ends at the same vertex. Eulerian circuits exist if every vertex of the graph has an even degree.

NETWORK DIAGRAM: A representation of a group of objects called vertices that are connected together by lines. Network diagrams are also called graphs.

Hamiltonian Cycle A Hamiltonian path, (passes through every vertex of a graph exactly once), that starts and finishes at the same vertex. C

B

A

D F E

Vertex [ ]: is a point in a network diagram at which lines of pathways intersect or branch.

SOLUTION :

Edge: the line that connects the vertices.

A–B–C–D–E–F–A

Degree: the number of edges that are connected to it. starts and ends at the same vertex as shown in the diagram. It counts as one edge, but it contributes two to the degree of the vertex. Directed Edge: Has an arrow and travel is only possible in the direction of the arrow. An undirected edge has no arrow and travel is possible in both directions. Weighted Edge: an edge of a network that has a number assigned to it that implies some numerical value such as cost, distance or time.

By: Kiana Gashtirajaie

Minimal Spann Spanning ing Tree

Minimum spanning trees represent the least weight required to keep all of the vertices connected in the graph.

Shortest Path

The shortest path between two vertices in a network is the path where the sum of the weights of its edges is minimised.

Critical Path Anal Analysis ysis

CRITICAL PATH : The Critical path is the sequence of the critical activities. They are activities that cannot be delayed without affecting the overall completion time of the project.

The EST for activity D is 6 and the LST for activity D is 9. This means activity D has a float time of (9 – 6) = 3 hours. Activity D can be delayed by 3 hours without delaying the rest of the project.

The EST for activity C is 8 and the LST for activity C is 8. This means activity C has a float time of (8 – 8) = 0 hours.

*The critical path is highlighted in red.

Activity C has no flexibility around its starting time at all. Any delay to the start of this activity will delay the whole project and extend the minimum time for completion. This means that activity C is a critical activity.

PROCESS:

Flow Capacity

The maximum flow that the edge allows (weight of the edge)

TERMINOLOGY :

FLOAT TIME :

The diagram on the right shows two pipes that are joined together, connecting the source of water to the sink. There is a small pipe with capacity 25 litres per minute Even though the large pipe has a capacity joined to a large pipe with greater than 25 litres per minute, the small capacity 58 litres per minute. pipe will only allow 25 litres of water When an edge is at its through each minute. The flow through the maximum flow, we say it is large pipe will never be more than 25 litres saturated. per minute. The large pipe will experience flow below its capacity. We say that it has an excess flow capacity, which is like the float time from the critical path analysis section.

By: Kiana Gashtirajaie

Maximum-Flow M Minimum-Cut inimum-Cut The Theorem orem

EXAMPLE :

1. Construct a network graph using the values in the cells as the flow capacity of the edges. 2.

Mark the possible paths and their capacity (trial and error process). These are: Green — 3; brown — 3; purple — 1. Purple path has a capacity of 1.

3. Identify the minimum cut (red dotted line). 4. Find the minimum cut capacity. 5. Find the maximum flow capacity.

By: Kiana Gashtirajaie...