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;
28 Cards in this Set
- Front
- Back
|
What is a graph? |
Something that consists of points which are connected by lines |
|
|
What are the points called? |
Vertices or nodes |
|
|
What are the lines called? |
Edges or arcs |
|
|
What is a subgraph? |
A subgraph of G is a graph, each of whose vertices belong to G and each of whose edges belong to G. |
|
|
What is a weighted graph? |
A graph where each edge is associated with a number (its weight) |
|
|
What is the weight usually? |
Distance |
|
|
What is the degree/ valency of a vertex? |
The number of edges incident to it. |
|
|
What is a 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. |
|
|
What is a cycle? |
A cycle/circuit is a closed path. The end vertex of the last edge is the start vertex of the first edge. |
|
|
What happens if 2 vertices are connected? |
There's a path between them |
|
|
What if all vertices are connected? |
The graph is connected |
|
|
What do you call edges with a direction associated with them? |
Directed edges. |
|
|
What is a graph with directed edges known as? |
A digraph |
|
|
What is a tree? |
A connected graph with no cycles |
|
|
What is a spanning tree of graph G? |
A subgraph which includes all the vertices of G and is also a tree |
|
|
What is a minimum spanning tree? |
A spanning tree such that the total length of its arcs is as small as possible. Sometimes called a minimum connector |
|
|
What is a complete graph? |
A graph in which every vertex is connected to every other vertex. |
|
|
What is a bipartite graph? |
This consists of 2 sets of nodes, x and y. Only x and y vertices can connect, not those in the same set. |
|
|
What is a matching? |
The one to one pairing of some or all of the elements of one set x with the second set y. |
|
|
What do you do in the maximum matching algorithm? |
Represent all possible matches on a bipartite graph. Start with an initial matching. Find an alternating path starting with an unmatched node and ending with an unmatched node on the other side. Change the status of all arcs. Write the new matching. If not complete, continue. |
|
|
What do you do in Kruskal's algorithm? |
Write all the arcs in order from lowest value to highest.Go down the list and accept arcs unless they form a cycle, then reject them. |
|
|
What do you do in Prim's algorithm? |
A node is stated. From this, you must choose the arc with the lowest node. You then look at these 2 nodes and find the lowest valued arc. This is continued until no more arcs can be drawn without making a cycle. |
|
|
What do Prim and Kruskal's algorithm do? |
They find the minimum spanning tree |
|
|
How do you find the total weight of the tree? |
Add up the weights of all the arcs |
|
|
What is a similarity between Prim and Kruskal's algorithm? |
The total weight is the same |
|
|
What are 4 differences between Prim and Kruscal's algorithm? |
Prim's builds the MST in a connected fashion. Kruskal's algorithm always begind with the smallest arc. Prim's has a starting node Prim's can be completed from a table without drawing a graph |
|
|
How do you use Prim's algorithm with a table? |
Look at the starting node given and put a 1 above it. Circle the lowest value in this column, write it down and then cross out the row. Put a 2 over the letter the arc goes to, cross out the row and circle the lowest value from these two columns. Continue until all rows are crossed out. |
|
|
What does crossing out the rows do? |
Prevents cycles forming. |
