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)
|
Graph |
A graph consists of vertices/nodes which are connected by edges/arcs |
vertices/nodes, edges/arcs |
|
|
Subgraph |
A subgraph is part of a graph |
|
|
|
Weighted Graph |
If a graph has a number associated with each edge (its weight) then the graph is a weighted graph (network) |
Weight, network |
|
|
Degree, Valency, Order |
A degree/Valency/order of a vertex is the number of edges incident to it. |
Incident |
|
|
Path |
A path is 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. |
Finite |
|
|
Walk |
A walk is a path in which you are permitted to return to vertices more than once. |
Path in which |
|
|
Cycle/circuit |
A cycle/circuit is a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge. |
Closed |
|
|
Connected |
Two vertices are connected if there is a path between them. Does not need to be direct. A graph is connected if all its vertices are connected. |
|
|
|
Loop |
A loop is an edge that starts and finishes at the same vertex. |
|
|
|
Simple graph |
A simple graph is one in which there are no loops and not more than one edge connecting any pair of vertices. |
|
|
|
Digraph |
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph. |
Directed edges |
|
|
Tree |
A tree is a connected graph with no cycles |
Cycles |
|
|
Spanning tree |
A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree. |
Graph G |
|
|
Bipartite graph |
A bipartite graph consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. |
X and Y |
|
|
Complete graph |
A complete graph is a graph in which every vertex is directly connected by and edge to each of the other vertices. If the graph has n vertices the connected graph is denoted kn |
|
|
|
Complete bipartite graph |
A complete bipartite graph denoted kr,s is a graph in which there are r vertices in set X and s vertices in set Y. |
|
|
|
Isomorphic graph |
Isomorphic graphs show the same information but are drawn differently. |
|
|
|
Adjacency matrix |
An adjacency matrix records the number of direct links between vertices. |
|
|
|
Distance matrix |
A distance matrix records the weights on the edges. Where there is no weight, this is indicated by "-" |
|
