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.
Matching
Matching is the 1 to 1 pairing of some, or all, of the elements of one set (X) with elements of second set (Y) in bipartite graph.
Maximal matching
Matching in which number of arcs is as large as possible.
Complete matching
1 to 1 pairing of all elements of one set, X, with elements of second set, Y, in bipartite graph.
Alternating path
Path starting at unmatched node on one side of bipartite graph and finishes at unmatched node on other side. Uses arcs that alternatively ‘not in’ or ‘in’ the initial matching.
Why dummy?
(One dependent on one, another on two) so that the 2 events can be described uniquely in terms of their end events.
RI: which node should end and why?
“CE” is shortest. So repeat “CE”. Thus start and end at “D” or “G”.
3 differences between Prim and Kruskal.
1) K starts with shortest arc. P starts with any node.
2) K adds arcs, whereas P adds nodes to growing tree.
3) P can use distance matrix.
Explain why there must always be an even number of vertices with odd valency in every graph.
Each arc contributes 1 to the orders of two nodes so the sum of the orders of all nodes is equal to twice the number of arcs, which implies that the sum of the orders of all nodes is even and therefore there must be an even (or 0) number of vertices of odd vertices of odd order hence there cannot be an odd number of vertices of odd order.
Find max number of comparisons in bubble sort.
For list of n numbers, max no. of passes = (n-1). Max no. of swaps= (n-1) + (n-2)+…+1. Thus n(n-1)/2 is max number of comparisons.
