A graph consists of vertices (nodes) which are connected by edges
1 of 27
Subgraph
Part of a graph
2 of 27
Weighted graph
A graph in which there is a number associated with each edge
3 of 27
Degree of valency
The number of edges incident to a vertex
4 of 27
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 no vertex appears more than once
5 of 27
Cycle
A closed path i.e.the end vertex of the last edge is the starting vertex of the first edge
6 of 27
Connected
Two vertices are 'connected' if there is a path between them. A graph is connected if all of it's vertices are connected
7 of 27
Digraph
A graph in which the edges have a direction associated with them- edges are directed edges
8 of 27
Tree
A connected graph with no cycles
9 of 27
Spanning tree
A subgraph of a graph which includes all the vertices of the graph and is also a tree
10 of 27
Bipartite graph
A graph consisting of 2 sets of vertices, X and Y. the edges only join vertices in X to vertices in Y, not vertices within the same set
11 of 27
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
12 of 27
Distance matrix
A matrix which records the weights on the edges, No weight is indicated by '-'
13 of 27
Minimum spanning tree
A spanning tree such that the total length of its arcs are as small as possible
14 of 27
Differences between Kruskal's and Prim's
Kruskal's always starts at the arc of lowest weight, Prim's can start at any node. Kruskals produces a minimum spanning tree is a chaotic manner, Prim's grows with linked arcs. Prim's algorithm does not have to be checked for cycles.
15 of 27
Eularian graph
All the valencies are even- graph is transversable
16 of 27
Semi-Eularian graph
Precisely 2 valencies are odd, the rest are even- semi-transversable
17 of 27
Early event time
The earliest time of arrival at an event allowing for the completion of all preceding events
18 of 27
Late event time
The latest time that an event can be left without extending the overall time of the project
19 of 27
Critical activity
An activity where any increase in it's duration results in a corresponding increase in the overall time.
20 of 27
Critical path
A path from the source node to the sink node which entirely follows critical activities. Longest path contained in the network
21 of 27
Total float
The amount of time an activity may be delayed without affecting the duration of the project
22 of 27
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.
23 of 27
Matching
A one-to-one pairing of some or all of the elements of one set, X with another set Y in a bipartite graph
24 of 27
Maximal matching
a matching in which the number of arcs is as large as possible
25 of 27
Complete matching
1 to 1 pairing of all the elements in set X, with elements of set Y, in a bipartite graph
26 of 27
Alternating path
A path starting with an unmatched node on one set and finishing with an unmatched node on the other set. Uses arcs that are alternately 'in' and 'not in' from the initial matching
27 of 27
Other cards in this set
Card 2
Front
Part of a graph
Back
Subgraph
Card 3
Front
A graph in which there is a number associated with each edge
Back
Card 4
Front
The number of edges incident to a vertex
Back
Card 5
Front
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and no vertex appears more than once
Comments
No comments have yet been made