A matching where every member of one set is paired to a member of the other set.
1 of 25
Digraph
Graph in which all edges have a specified direction. (These are called directed edges)
2 of 25
Bipartite graph
2 distinct sets of vertices. Edges only join a vertex of one set to a vertex of the other set, not vertices within a set.
3 of 25
Minimum spanning tree/ Minimum connector
A spanning tree such that the total length of its arcs is as small as possible.
4 of 25
Matching
Is a one to one pairing of some or all of the elements of one set with elements of a second set. One to one means each element of the first set is paired with only one element of the second set.
5 of 25
Path
Finite sequence of edges, end vertex of one edge is the start vertex of the next edge. No vertex appears more than once.
6 of 25
Total float
Amount of time an activities can be delayed without affecting the duration of the project. Eg. F(a,b)=late(b)-early(a)-duration(a,b).
7 of 25
Degree/ Valency/ Order
The number of edges incident to a vertex. A vertex is odd/even if the degree is odd/even.
8 of 25
Cycle/ Circuit
Closed path. Closed means the end vertex of the final edge is the start vertex of the first edge.
9 of 25
Complete graph/ Connected graph
Graph in which all vertices are connected. Denoted Kn if it has n vertices.
10 of 25
Connected vertices
Vertices with a path between them.
11 of 25
Complete graph
A graph in which all of the vertices are connected to every other vertex.
12 of 25
Spanning tree
Sub graph which includes all vertices of the original graph. Is a tree, with no cycles.
13 of 25
Graph
Contains points (vertices/nodes) connected by lines (arcs or edges).
14 of 25
Subgraph of graph G
Is a graph, each of whose vertices belong to G and each of whose edges belongs to G.
15 of 25
Tree
Connected graph with no cycles.
16 of 25
Weighted graph/ Network
Graph with numbers associated with each edge.
17 of 25
Maximal matching
A matching in which the number of arcs is as big as possible.
18 of 25
Critical path
Path from source node to sink node. Which only follows critical activities. The longest path in the network.
19 of 25
Dummy activity
1) Activity _depends only on activity _ but activity _ depends on activities _&_. 2) To enable the unique representation of activities _&_ in terms of their end events.
20 of 25
Critical activity
An activity for which an increase in its duration results in a corresponding increase in the duration of the project. An activity with a float of zero.
21 of 25
Semi-traversible (semi-eulerian) graph
Graph with precisely two odd valences. The start and finish point of a traverse around the graph must be the odd vertices.
22 of 25
Alternating path
Path starting at an unmatched node from one set of a bipartite graph and finishing at an unmatched node from the other set. Using arcs alternately in and not in the in initial matching.
23 of 25
Non-traversible graph
A graph with more than two odd nodes.
24 of 25
Traversible (eulerian) graph
A graph which you can draw over all of the arcs exactly once without taking your pen of the paper. A graph with no odd nodes.
25 of 25
Other cards in this set
Card 2
Front
Graph in which all edges have a specified direction. (These are called directed edges)
Back
Digraph
Card 3
Front
2 distinct sets of vertices. Edges only join a vertex of one set to a vertex of the other set, not vertices within a set.
Back
Card 4
Front
A spanning tree such that the total length of its arcs is as small as possible.
Back
Card 5
Front
Is a one to one pairing of some or all of the elements of one set with elements of a second set. One to one means each element of the first set is paired with only one element of the second set.
Comments
No comments have yet been made