Edexcel A-level Maths D1 Decision Definitions

Edexcel A-level Maths D1 Decision Definitions Graph points (vertices or nodes) connected by lines (edges or arcs) subgraph A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G weighted graph or network number/weight associated with each edge degree or valency the number of edges incident to a vertex. path a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more then once cycle (circuit) a closed path: the end vertex of the last edge is the start vertex of the first edge connected vertices vertices that have a path between them connected graph all vertices are connected directed edges/digraph edges that have a direction associated with them tree connected graph with no cycles spanning tree a subgraph which includes all the vertices of G and is also a tree minimum spanning tree/connector total arc length is as small as possible complete graph Each vertex is connected to every other vertex bipartite graph two sets of vertices X and Y with edges between sets (complete) matching the pairing of some or all of the elements of one set with elements of a second set