# D1 definitions

All the definitions needed for edexcel D1 maths

HideShow resource information
• Created by: Samantha
• Created on: 10-06-14 22:17
Arc
A curved line connecting points (nodes or vertices) on a graph
1 of 24
Bipartite graph
A graph consisting of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y
2 of 24
Circuit/ cycle
A closed path
3 of 24
Complete graph
A graph in which each of the n vertices is connected to every other vertex
4 of 24
Complete matching
A matching where every member of the first set X is paired with a member of the second set Y
5 of 24
Critical activity
An activity where any increase in its duration results in a corresponding increase in the duration of the whole project
6 of 24
Degree
The degree of a vertex is the number of edges incident to it
7 of 24
Digraph
A graph with directed edges
8 of 24
Dijkstra's algorithm
An algorithm that finds the shortest path from a single source vertex to all other vertices in a directed graph
9 of 24
Earliest event time
The earliest time at which all of the dependent events may be completed allowing the event in question to begin, calculated using a forward scan
10 of 24
Edge
A line on a graph connecting two nodes
11 of 24
Feasible region
The region that contains all the feasible solutions
12 of 24
Graph
Points (vertices or nodes) which are connected by lines (edges or arcs)
13 of 24
Late event time
The latest time at which any of the dependent events may be completed without delaying the project, calculated using a backward scan
14 of 24
Matching
The pairing of some or all of the elements in one set X with elements of a second set Y
15 of 24
Maximum matching
A matching where the number of pairings between the elements of one set, X, with the elements of a second set, Y is as high as possible
16 of 24
Minimum spanning tree
A tree that contains all vertices and the total length of its arcs is as small as possible
17 of 24
Network
A graph where each edge has a weight
18 of 24
Optimal solution
A feasible solution that meets the objective
19 of 24
Precedence table
A table showing which activities must be completed before others can be started
20 of 24
Source/sink node
The first/last point in a network
21 of 24
Spanning tree
A subgraph which includes all the vertices of G and is also a tree
22 of 24
Tree
A connected graph with no cycles
23 of 24
Vertex (node)
A point on a graph
24 of 24

## Other cards in this set

### Card 2

#### Front

A graph consisting of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y

Bipartite graph

A closed path

### Card 4

#### Front

A graph in which each of the n vertices is connected to every other vertex

### Card 5

#### Front

A matching where every member of the first set X is paired with a member of the second set Y