Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
24 Cards in this Set
- Front
- Back
|
Graph |
A graph(G) consists of nodes connected by arcs |
|
|
Subgraph |
A subgraph of G contains nodes and arcs of G |
|
|
Weighted graph |
A graph with numbers associated with each arc |
|
|
Valency (degree) |
The degree or valency of a node is the number of edges incident to it |
|
|
Path |
A finite sequence of arcs, such that the end node of one arc is the start node of the next and no node appears more than once. |
|
|
Cycle (circuit) |
A closed path |
|
|
Connected |
Nodes are connected if there's an arc between them |
|
|
Connected graph |
All nodes are connected |
|
|
Digraph |
Where arcs have directions associated with them |
|
|
Tree |
A connected graph with no cycles |
|
|
Spanning tree |
A subgraph of G which includes all the nodes of G and is also a tree |
|
|
Minimum spanning tree |
A spanning tree such that the total length of its arcs is as small as possible |
|
|
Complete graph |
A graph where each node is connected to every other node |
|
|
Bipartite graph |
Consists of 2 sets of vertices, X and Y. Arcs only join X nodes to Y nodes, not nodes within a set |
|
|
Matching |
The pairing of some or all of the elements of one set X with elements of a second set Y |
|
|
Complete matching |
Every member of X is paired with a member of Y |
|
|
Other names for nodes |
Vertices, points |
|
|
Other names for arcs |
Edges, lines |
|
|
Other name for a cycle |
Circuit |
|
|
Other name for a minimum spanning tree |
Minimum connector |
|
|
Total float |
The total float F(i, j) of activity (i, j) is defined to be F(i, j) = lj – ei – duration (i, j), where ei is the earliesttime for event i and lj is the latest time for event j.
|
|
|
Early event time |
The earliest time of arrival at the event, allowing for the completion of all preceding activities |
|
|
Late event time |
The latest time that the event an be left without extending the time needed for completion |
|
|
Critical activity |
An activity where any increase in its duration results in a corresponding increase in the whole project duration. Total float=0 |
