D1

• 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. 

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

• Ifall 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 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. 

• 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. 

• 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 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. 

• 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. 

• 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

• 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. 

• 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. 

• 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. 

• 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.