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