# D1

- Created by: amy
- Created on: 16-03-13 09:03

## Traversable

- A
**degree**or**valency**or**order**of a**vertex**is the**number of arcs incident to it**. - A vertex is
**odd**if it has a**odd**valency. - A vertex is
**even**if it has a**even**valency.

- If all the valencies in a graph are
**even,**then the grpah is**Eulerian**. - If precisley
**two**valencies are odd, and the rest are even, then the grpah is**semi-Eulerian**.

- A graph is
**traversable**if it is possible to transvers( travel along) every arc once without taking your pen from the paper. - A graph is
**traversable**if all the valencies are**even**. - A graph is
**semi-traversable**if it has precisely**two odd valencies**. In this case the start and end point will be the odd valencies. - A graph is
**not traversable**if is has more than two odd valencies.

## Route inspection (chinese postman) algorithm

- The route inspection algorith finds the
**shortest route**covering**all edges**and it returns back to the start point.

- If
*all*the verticies have even valency the network is traverable. The length of the shortest route will be equal to the weight of the network.

Length of inspection route in an Eulerian graph=weight of the network

- If there are only two odd verticies, repeat the shortest path between them and add it to the network.

Length of inspection route in a = weight of network + weight of the shortest path between semi-Eulerian graph the two odd veritices

- If there are more than two odd valencies, you need to consider all possible complete pairings and select the one that gives the smallest total and then add this pairing to the network.

## Route inspection (chinese postman) algorithm

**Route inspection algorithm:**

1. Identify any verticies with odd valency.

2. Consider all possible complete pairings of these verticies.

3. Select the complete pairing that has the least sum/ distance.

4. Add a repeat of the arcs indicated by this pairing to the network.

5. The graph is now Eulerian- so you can find an inspection route through it.

6. Add the lengths of the new edges to the weight of the network to get the length of the inspection route.

## Critical path analysis: model a project by an acti

- A complex project may be broken down into a number of seperate
**activities**. - The completetion of an activity is called an
**event**. - The activities can be written in a table which shows which ones must be completed before others are started. This is called a
**precedence table,**or a**dependence table**.

## Activity Networks

- An activity netwrok provides a visual representation of the information given in a precendence table which makes it easier to work with and understand.
- The type of activity network used is called an
**activity on arc network**.- Here the activities are represented by arcs and events are nodes.
- Each arc is labelled with an activity letter- the beggining and end of an activity are shown at the ends of the arc and an arrow is used to define the direction.
- The nodes are numbered from 0 for the first node -
**source node** - Number each node as it is added to the network.
- The final node is called the
**sink node.**

## Dummies in activity networks/tables

**Dummies**help show the**order**activities must be done in.- They arent real activities, they just show that
**one activity depends**on**another activity**.

- There can only be ever
**one activity**between the**same two events** - No two activities can be shown by the same pair of events- each activity must be shown by a different pair of nodes.
- A
**dummy**is used to stick to the rule.

A dummy is shown by a dotted line, it has an arrow to indicate direction but has no weight.

Dummies are needed for two reasons:

1. if activity D depends *only* on activity B, but activity E depends of activities B and C.

2. to enable the unique representation of activities in terms of their end events.

## Activity networks with early and late times

- Each activity has a
**duration**- a certain amount of time it takes to complete. - Each node in a network represents an event. Is is useful to consider two seperate times associated with each event.
- Each node/
*event*has an**early event time**and a**late event time**.

The **early event time**- is the earliest time you can reach an event. It depends on the durations of the **preceeding activities**.

The **late event time**- is the latest time you can get to an event **without** increasing the duration of the entire project.

The activity network shows this information by using boxes at each vertex/node showing the early and late times:

- The early event times are calculated starting from 0 at the source node and working towards the sink node. This is called a
**forward pass**or**forward scan**. - The late times are calculated from the sink nodes and working backwards towards the source node. This is called a
**backward pass**or**backward scan**.

## Critical paths and activities

- A
**critical activities**must be completed within their alotted time. - If the duration of a
**critical activity**increases, the duration of the whole project increases by the same amount. - A
**critical path**runs from the source node to the sink node and is made up of**critical activities.** - A critical path is the longest bath contained in the network.
- All the nodes on a
**critical path**have the same**early and late event times**. - This means they
**must**be started at a particular time- there is no 'slack' **Adding**up the duration of the actvities on the critical path gives the duration of the whole project or the**critical time**.- An activity connecting two critical events isn't necessarily a critical activity

An activitiy is only critical if: Activity duration= event time of critical - event time of critical node after node before

## Critical paths- float of an activity

- The
**total float**of an activity is**how long**it can be delayed for. (without affecting the duration of the project.

Total float = latest finish time - duration - earliest start time

- The total float of any critical activity is 0.

## Gannt charts (cascade charts)

- A
**gannt chart**shows possible**start**and**finish**times for activities. (that allows the project to be completed on time) - The number scale shows
*elapsed time.*So, the first hour is shown between 0 and 1 on the scale, the second hour is between 1 and 2... etc. - The critical activities are shown as rectangles in a line at the top as there are no flexibilities in when they can start and finish.
- The gannt chart illustrates the degree of flexibility in the timing of each of the activities by the dotted lines.
- The dotted box shows the total float of each activity - the range of movement.

## Scheduling

- The people resposible for completing the activities in a project are referred to as
**workers**. You assume that:- each activity is completed by a single worker in the time given as the duration of the activity
- oce an activity has started, it must be completed by the worker
- once a worker has completed an activity they become immediatly available to start another activity

- Always use the first worker, if there are a achoice of tasks for a worker use the one with the lowest value for its latest finish time as shown on the activity network.
- The process of assigning workers is known as
**scheduling**. Typically, you want to find the minimum number of workers needed to complete a project in the critical time. Starting from a Gannt chart, a**scheduling diagram**can be constructed which shows the assignment of activities to each worker.

## Scheduling

- The
**lower bound**for the number of workers is the**absolute minimum**. - It is the fewest number of workers that could possibly complete the porject within the critical time:

The lower bound: smallest integer sum of all the activity critical time of the project

- Sometimes the lower bound is not enough as it doesnt take into account the
**overlap**and**orders**of the activities. - Without enough workers, the project will take longer.

## Comments

No comments have yet been made