Home      d1definitions
Decision 1 Definitions
A list of D1 definitions required for the Edexcel exam

Connected Graph - all pairs of vertices are connected by a path.

Tree -  connected graph with no cycles.

Spanning Tree - of a graph G is a subgraph which includes all the verticles of G and is also a tree.

Minimum Spanning Tree (MST) - a spanning tree with the total length of the arcs being as small as possible.

Graph - consists of points connected by lines.
Valency/Degree - of a vertex is the number of edges incident to it.

Subgraph - of G is a graph each of whose vertices and edges belong to G.

Network - a graph which has a number (weight) associated with each edge.

Path - a finite sequence of edges such that the end vertex of one edge is the start vertex of the next, with no vertex appearing more than once.

Cycle - a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.

Matching - pairing of some or all of the elements in one set with elements of a second set.

Bipartite Graph - consists of 2 sets of vertices X and Y. The edges only join vertices is X to vertices in Y and not vertices within a set.