# MEI Decision 1 Graph Types

HideShow resource information
• Created by: Caraa
• Created on: 02-06-13 13:43
Bipartite
Two sets of vertices
1 of 29
Networks
Have numbers on each arc
2 of 29
Digraphs
Edges have directions
3 of 29
Complete
All vertices are connected to every other vertex
4 of 29
Simple
No loops or multiple edges
5 of 29
Connected
All vertices can be reached from all vertices
6 of 29
Subgraphs
Parts of other graphs
7 of 29
A Path
A route that doesn't repeat any vertices
8 of 29
A Cycle
Path that brings you back to your starting point
9 of 29
A Hamilton Cycle
A cycle that goes through every vertex once
10 of 29
A Walk
Any route on a graph
11 of 29
A Trail
A walk that doesn't repeat any edges
12 of 29
Tree
Graphs that have no cycles
13 of 29
Spanning Tree
Subgraphs that are trees
14 of 29
Planar
Arcs only cross at vertices
15 of 29
Conditions for an algorithm
Finite
16 of 29
The order
Tells you how fast it is (can be quadratic, cubic etc...)
17 of 29
The size
Number of inputs eg number of items in the list
18 of 29
Sum of the orders on a graph equals...
double the number of edges
19 of 29
Transversable means?
You can get from any vertex to any other by covering all arcs only once
20 of 29
Two odd
Semi-transverable. There is a route between the two
21 of 29
More than two odd
Non transverscable
22 of 29
All even
Transverable. There is a route between all
23 of 29
Kruskals?
Ascending order
24 of 29
Early event time?
Earliest you can reach an event
25 of 29
Late event time?
Latest you can reach an event without increasing the duration of the whole project
26 of 29
What does the minimum completion time assume?
Unlimited resources
27 of 29
Float time
How long an activity can be delayed for if the project is to be completed on time. Late finish - duration - early start
28 of 29
Independent float time
Amount you can delay the activity for all activities before to start as late as possible and all after to start as early. early finish - duration - late start
29 of 29

## Other cards in this set

### Card 2

Networks

#### Back

Have numbers on each arc

Digraphs

Complete

Simple