D1 maths definitions

Question	Answer
The degree/valency/order of a vertex	number of edges incident to it
A weighted graph	A graph that has a number associated with each edge (it’s weight)
A graph	A group of vertices (nodes) which are connected by edges
A sub-graph	Part of a graph
A path	A sequence of edges. The end vertex of one edge is the start vertex of the next. Vertexes are not repeated
A walk	A path in which you are permitted to return to vertices more than once
A cycle	A closed path
A loop	An edge that starts and finishes at the same vertex
Tree	A connected graph with no cycles
A spanning tree	A sub-graph which includes all vertices of the graph and is also a tree
Bipartite graph	Two sets of vertices X and Y. The edges only join vertices in X to Y
A simple graph	A graph with no loops and not more than one edge connecting any pair of vertices
Directed edges	The edges of a graph have a direction associated with them
Digraph	Edges with direction in the graph
A complete graph	Every vertex is directly connected by an edge to each of the other vertices
A complete bipartite graph	r vertices in set X and s vertices in set Y
Isomorphic graph	shows the same information but drawn differently from a graph
An adjacency matrix	Records the number of direct links between vertices
A distance matrix	Records the weights on the edges. When there is no weight, it is indicated by “-“

Resource summary

	Created by emilycompton1996 almost 11 years ago