D1 Definitions Flashcards
How do you find the middle point in a list?
In a list containing N items the ‘middle’ item has position [1/2(N + 1)] if N is odd [1/2(N + 2)] if N is even, so that if N = 9, the middle item is the 5th and if N = 6 it is the 4th
What is a graph?
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
What is a subgraph?
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
What is meant by a weighted graph?
If a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph or network.
What is the degree (valency) of a vertex.
The degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree
What is a path?
A path is a finite sequence of edges, such that the end vertex of an edge in the sequence is the start vertex of the next, and in which no vertex appears more then once
What is a cycle?
A cycle (circuit) is a closed path, ie the end vertex of the last edge is the start vertex of the first edge.
What is a meant by a digraph?
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
What is a tree?
A tree is a connected graph with no cycles
What is a spanning tree?
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
What is a minimum spanning tree?
A minimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as possible. (MST is sometimes called a minimum connector.)
What is meant by a complete graph?
A graph in which each of the n vertices is connected to every other vertex is called a complete graph.
What is a bipartite graph?
A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. (If there are r vertices in X and s vertices in Y then this graph is Kr,s.)
What is a matching?
A matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. If every member of X is paired with a member of Y the matching is said to be a complete matching.
What is the float of an activity?
The total float F(i,j) of activity( (i,j) is defined to be F(i,j)=Lj-Ei-duration of (i,j), where Ei is the earliest time for event i and Lj is the latest time for event j.
