A graph consists of vertices (nodes) which are connected by edges (arcs)
1 of 30
Subgraph
A subgraph is a part of a graph
2 of 30
Weighted Graph
A graph in which there is a number associated with each edge (its weight)
3 of 30
Degree of valency/order
The number of edges incident to a vertex
4 of 30
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
5 of 30
Walk
A path in which you are permitted to return to vertices more than once
6 of 30
Cycle/ Circuit
A closed path i.e. the end vertex of the last edge is the start vertex of the first edge
7 of 30
Loop
An edge that starts and finishes at the same vertex
8 of 30
Simple Graph
A graph in which there are no loops and not more than one edge connecting any pair of vertices
9 of 30
Digraph/ Directed Edges
A graph in which the edges have a direction associated with them- the edges are known as directed edges
10 of 30
Tree
A connected graph with no cycles
11 of 30
Spanning Tree
A subgraph of a graph which includes al the vertices of the graph and is also a tree
12 of 30
Minimum Spanning Tree
A spanning tree such that the total length of its arcs is as small as possible
13 of 30
Bipartite Graph
A graph conisisting of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set
14 of 30
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
15 of 30
Complete Bipartite Graph
A graph iin which there are r vertices in set X and s vertices in set Y (denoted Kr,s)
16 of 30
Isomorphic Graphs
A graph showing the same information as another but which is drawn differently
17 of 30
Adjacency Matrix
A matrix which records the number of direct links between vertices
18 of 30
Distance Matrix
A matrix which records the weights on the edges. Where there is no weight, this is indicated by '-'.
19 of 30
Eulerian Graph
All valencies are even. Graph is traversable
20 of 30
Semi-Eulerian Graph
If precisely two vertices are odd and the rest even, the graph is semi-traversable
21 of 30
Early event time
The earliest time of arrival at the event allowing for the completion of all preceeding acctivities.
22 of 30
Late event time
The latest time that the event can be left without extending the time needed for the project.
23 of 30
Critical Activity
An activity where any increase in its duration results in a corresponding increase in the duration of the whole project i.e. float of 0
24 of 30
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
25 of 30
Total Float
The amount of time an activity may be delayed without affecting the duration of the project
26 of 30
Matching
A matching is a 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
27 of 30
Maximal Matching
A matching in which the number of arcs is as large as possible
28 of 30
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
29 of 30
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 alternated 'not in' or 'in' the initial matching
30 of 30
Other cards in this set
Card 2
Front
A subgraph is a part of a graph
Back
Subgraph
Card 3
Front
A graph in which there is a number associated with each edge (its weight)
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 in which no vertex appears more than once
Comments
No comments have yet been made