D1 Definitions

Question	Answer
Graph	A graph consists of vertices [nodes] which are connected by edges [arcs].
Subgraph	A subgraph is a part of a graph.
Weighted graph	A graph in which there is a number associated with each edge [its weight].
Degree of valency/order	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 than once.
Walk	A path in which you are permitted to return to vertices more than once.
Cycle/circuit	A closed ‘path’ i.e. the end vertex of the last edge is the start vertex of the first edge.
Connected	Two vertices are ‘connected’ if there is a path between them. A graph is connected if all its vertices are connected.
Loop	An edge that starts and finishes at the same vertex.
Simple graph	A graph in which there are no loops and not more than one edge connecting any pair of vertices.
Digraph/Directed edges	A graph in which the edges have a direction associated with them
Tree	A connected graph with no cycles.
Spanning tree	A subgraph of a graph which includes all the vertices of the graph and is also a tree.
Bipartite graph	A graph consisting of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
Complete graph	A graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, the connected graph is denoted kn.
Complete bipartite graph	A graph in which there are r vertices in set X and s vertices in set Y [denoted kr,s].
Isomorphic graphs	A graph showing the same information as another but which is drawn differently.
Adjacency matrix	A matrix which records the number of direct links between vertices.
Distance matrix	A matrix which records the weights on the edges. Where there is no weight, this indicated by
Early event time	The earliest time of arrival at the event allowing for the completion of al preceding activities.
Late event time	The latest time that the event can be left without extending the time needed for the project.
Critical activity	An activity where any increase in its duration results in a corresponding increase in the duration of the whole project i.e. it has a total float of zero.
Critical path	A path from the source node to the sink node which entirely follows critical activities. It is the longest path contained in the network.
Total float	The amount of time an activity may be delayed without affecting the duration of the project.
Matching	A matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y, in a bipartite graph.
Maximal matching	A matching in which the number of arcs is as large as possible.
Complete matching	A complete matching is the 1 to 1 pairing of all of the elements of one set, X, with elements of a second set, Y, in a bipartite graph.
Alternating path	A path starting at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately
The purpose of dummies:	1.E.g. If activity D depends only on activity B but activity E depends on activities B and C. 2.To enable the unique representation of activities in terms of their end events.
Explain why there must always be an even [or zero] number of vertices with odd valency in every graph.	Each arc has two ends and so will contribute to two to the total sum of the valencies of the whole graph. Therefore, the sum of the valencies is always even. Therefore, vertices with an odd number of valencies must exist in pairs. Therefore, there is always an even number of odd valencies.
Differences between Kruskal’s and Prim’s Algorithm:	1. Kruskal’s algorithm always starts with the arc of lowest weight while Prim’s can start at any node. 2. Kruskal’s algorithm produces a MST in a ‘chaotic’ manner while Prim’s MST grows with linked arcs. 3. Unlike Kruskal’s algorithm, you do not have to check for cycles with Prim’s algorithm. 4. Prim’s algorithm can be applied to a distance matrix while Kruskal’s algorithm cannot.

Next up

Description

Resource summary

Similar

	Created by Joseph Tedds over 8 years ago