D1 glossary

Question	Answer
Graph	consists of vertices or nodes, connected by edges or arcs
Subgraph	a graph within a graph
Weighted graph or network	a graph with a number (or weight) associated with each edge
Degree or valency	the number of edges attached to a vertex
Path	a finite sequence of edges such that the end vertex of one edge is the start of the next and no vertex appears more than once
Cycle or circuit	a closed path
Digraph	a graph made of directed edges
Tree	connected graph with no cycles
Spanning tree	a subgraph which includes all vertices of the main graph, and is a tree
Minimum spanning tree	a spanning tree such that the total length of its arcs is as small as possible
Complete graph	a graph in which every vertex is connected to every other vertex
Total float F(i,j) of an activity (i,j)	latest time for event j - earliest time for event i - duration of arc
Bipartite graph	consists of two sets of vertices, and arcs only between the two sets
Matching	pairings between sets X and Y in a bipartite graph
Complete matching	a matching where all vertices of set X are paired with a distinct vertice of set Y

Resource summary

	Created by Jake Crossland over 10 years ago