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;
19 Cards in this Set
- Front
- Back
- 3rd side (hint)
|
Cycle |
formed when an arc is used connecting two vertices that are already connected. |
not allowed in minimum spanning trees |
|
|
Kruskal's algorithm |
Finds a minimum spanning tree Needs to be checked for cycles to remove them Starts with the shortest arc |
|
|
|
Prim's algorithm |
Finds a minimum spanning tree Algorithm prevents cycles Starts from any vertex Connects vertices to nearest nodes |
|
|
|
Dijkstra's algorithm |
Finds the shortest route between two vertices |
|
|
|
bipartite graph |
consists of two sets of vertices which arcs can connect between sets but not within sets |
|
|
|
alternating path |
used to find improved matchings, starts at an unmatched vertex in set 1 to an unmatched vertex in set 2, alternating between arcs in/ not in the matching |
|
|
|
matching |
1-1 pairing between the two distinct sets |
|
|
|
complete matching |
1-1 matching where all set 1 and all set 2 elements are matched |
|
|
|
graph |
collection of vertices and nodes |
|
|
|
network |
weighted graph |
|
|
|
walk |
sequence of edges where the end of each edge is the beginning of the next |
|
|
|
trail |
walk where no edges are repeated |
|
|
|
path |
sequence of edges where no vertex appears more than once |
|
|
|
simple graph |
no loops and no more than one edge connecting any pair of vertices |
|
|
|
connected graph |
path exists between every pair of vertices |
|
|
|
tree |
connected graph with no cycles loops or multiple edges |
|
|
|
spanning tree |
tree (connected graph with no cycles loops or multiple edges) including all vertices |
|
|
|
minimum spanning tree |
tree including all vertices of minimum total weight |
|
|
|
digraph |
graph containing directed edges (have a direction) |
|
