Decision 1 Definitions Flashcards
Graph
Consists of vertices which are connected by edges.
Subgraph
Part of a graph.
Weighted graph
Graph in which there is a number associated with each edge.
Degree of valency/order
Number of edges incident to a vertex.
Path
Finite sequence of edges. End vertex of one edge in the sequence is the start vertex of the next. No vertex appears more than once.
Walk
Path which you are allowed to return to vertices more than once.
Cycle
Closed ‘path’. End vertex of last edge is start vertex of first edge.
Connected
Two vertices are connected if there is path between them. Connected graph= all its vertices are connected.
Loop
Edge that starts and finishes at the same vertex.
Simple graph
Graph with no loops and not more than one edge connecting any pair of vertices.
Digraph
Graph with edges that have direction associated with them- edges=connected edges.
Tree
Connected graph with no cycles.
Spanning tree
Subgraph of a graph which includes all vertices of the graph and is also a tree.
Bipartite graph
Graph consisting of two sets of vertices, X and Y. Edges only join vertices in X to vertices in Y, not vertices within a set.
Complete graph
Graph in which every vertex is directly connected by an edge to each of the other vertices. If graph has n vertices, connected graph is denoted k(n subscript).
Complete partite graph
Graph in which there are r vertices in set X and s vertices in set Y (denoted K(r,s subscript).
Isomorphic graph
Graph showing same information as another but which is drawn differently.
Distance matrix
Matrix which records the weights on the edges. No weight is indicated by ‘-‘.
Minimum spanning tree
A spanning tree such that the total length of its arcs is as small as possible.
Early time
Earliest time of arrival at event allowing for completion of all preceding activities.
Late time
Latest time that event can be left without extending the time needed for project.
Critical activity
Activity where any increase in its duration results in a corresponding increase in the duration of the whole project.
Critical path
Path from source to sink which entirely follows critical activities. Longest path in network.
Total float
Total float, F (i, j) of activity (i, j) is defined to be F(i, j)=l(sub j) - e(sub i) - duration (i, j), where e(sub i) is the earliest time for event i and l(sub j) is the latest time of event j.