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
Subgraph |
A subgraph is part of a graph, each of whose vertices belongs to the graph and each of whose edges belong to the graph. |
|
Graph |
A graph consists of points (vertices or nodes) which are connected by lines (edges or arcs). |
|
Weighted graph/network |
When a graph has a number associated with each edge. |
|
Path |
A path is a finite sequence of edges, such that the end vertex of one edge is the start vertex of the next, and in which no vertex appears more than once. |
|
Degree/Valency |
The number of edges connected to a single vertex. |
|
Loop |
An edge that starts and finishes at the same vertex. |
|
When are two vertices connected? |
When there is a path between them. This can be an edge or a sequence of edges. |
|
Cycle/Circuit |
A cycle/circuit is a closed path, ie the end vertex of the last edge is the start vertex of the first edge. |
|
Simple Graph |
A graph in which the are no loops and not more than one edge connecting any pair of vertices. |
|
Walk |
A path in which you are permitted to return to vertices more than once. |
|
Tree |
A connected graph with no cycles. |
|
Digraph |
A graph that has directed edges. |
|
Directed edges |
Edges that have direction associated with them. |
|
Connected Graph |
All pairs of vertices connected by a path. |
|
Distance matrix |
Records weights of edges |
|
Spanning tree |
A subgraph which includes all of the vertices of the graph and is also a tree. All nodes connected and the are no cycles. |
|
completed graph |
A complete graph is where 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 k(n). |