# Decision 1 Definitions EDEXCEL AS MATHS

Graph
Consists of points (called vertices or nodes) which are connected by lines (edges or arcs)
1 of 20
Degree/Valency/Order if a vertex
The number of edges incident to it.
2 of 20
Traversable
A graph is traversable if it is possible to traverse (travel along) every arc just once without taking your pen from the paper.
3 of 20
Network
A graph whose edges have a numerical value (weight).
4 of 20
Directed Graph (Digraph)
Travelling in one direction along an edge.
5 of 20
Path
A finite sequence of edges, such that the end vertex of one edge is the start vertex of the next. And in which no vertex appears more than once.
6 of 20
Walk
A path in which you are permitted to return to vertices more than once.
7 of 20
Cycle or Circuit
A closed "path"
8 of 20
Loop
An edge that starts and finishes at the same vertex.
9 of 20
Simple graph
A graph where there are no loops and doesn't have more than one edge connecting any pair of vertices.
10 of 20
Subgraph
Part of the original graph.
11 of 20
Tree
A connected graph with no cycles.
12 of 20
Spanning tree
A subgraph that contains all of the vertices of the original graph and is also a tree.
13 of 20
Minimum spanning tree (MST)
A spanning tree such that the total length of its arcs is as small as possible.
14 of 20
Bipartite graph
Two sets of nodes. Arcs may connect nodes from different sets, but never from the same set.
15 of 20
Complete matching
If both sets have n nodes, a complete matching is a matching with n arcs.
16 of 20
Maximal matching
Matching in which the number of arcs is as large as possible.
17 of 20
Critical activity
Any increase in its duration results in a corresponding increase in the duration of the whole project.
18 of 20
Critical path
A path from the source node to the sink node which entirely follows critical activities. A critical path is the longest path contained in the network.
19 of 20
At each node on a critical path...
The early event time is equal to the late event time.
20 of 20

## Other cards in this set

### Card 2

#### Front

Degree/Valency/Order if a vertex

#### Back

The number of edges incident to it.

Traversable

Network

### Card 5

#### Front

Directed Graph (Digraph)