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;
17 Cards in this Set
- Front
- Back
|
Graph |
A graph consists of vertices (nodes) which are connected by edges (arcs). |
|
|
Subgraph |
A subgraph is a part of a graph. |
|
|
Degree of valancy/order |
The number of edges incident to a vertex. |
|
|
Path |
A finite sequence of edges, such that the end vertex of one edge in the sequence in the start vertex of the next, & in which no vertex appears more than one. |
|
|
Walk |
A path in which you're permitted to return to vertices more than once. |
|
|
Cycle/circuit |
A closed 'path' i.e. the end vertex of the last edge is the start vertex of the first edge. |
|
|
Connected |
2 vertices are 'connected' if there's a path between them. A graph is connected if all its vertices are connected. |
|
|
Tree |
A connected graph with no cycles. |
|
|
Spanning tree |
A subgraph of a graph of a graph which includes all the vertices of the graph & is also a tree. |
|
|
Bipartite graph |
A graph consisting of 2 sets of vertices, X & Y. The edges only join vertices in X to vertices in Y, not vertices within a set. |
|
|
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. |
|
|
Differences between Kruskal's & Prim's Algorithms |
Kruskal's algorithm always starts with the arc of the lowest weight while Prim's can start at any node. Kruskal's algorithm produces a minimum spanning tree in a 'chaotic' manner while Prim's minimum spanning tree grows with linked arcs. Unlike Kruskal's algorithm, you don't have to check for cycles with Prim's algorithm. Prima algorithm can be applied to a distance matrix while Kruskal's algorithm can't. |
|
|
Explain why there must always be an even (or zero) number of vertices with odd valency in every graph. |
Each arc has 2 ends & so will contribute to 2 to the total sum of the valencies of the whole graph. Therefore, the sum of the valencies is always even. Therefore, vertices with an odd number of valencies must exist in pairs. Therefore, there's always an even number of odd valencies. |
|
|
Matching |
A matching is the 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. |
|
|
Maximal matching |
A matching in which the number of arcs is as large as possible. |
|
|
Complete matching |
A complete matching is the 1 to 1 pairing of all of the elements of one set, X, with the elements of a second set, Y, in a bipartite graph. |
|
|
Alternating path |
A path starting at an unmatched node on one side of the bipartite graph & finishes at an unmatched node on the other side. It uses arcs that are alternately 'not in' or 'in' the initial matching. |
