This is the number of edges incident to the vertex.
1 of 14
What is a 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.
2 of 14
What is a walk?
A walk is a path in which you are permitted to return to vertices more than once.
3 of 14
What is a 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.
4 of 14
What does connected mean?
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
5 of 14
What is a loop?
A loop is an edge that starts and finishes at the same vertex.
6 of 14
What is a simple graph?
A simple graph is one in which there are no loops and not more than one edge connecting any pair of vertices.
7 of 14
What is a tree?
A tree is a connected graph with no cycles.
8 of 14
What is a spanning tree?
A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree
9 of 14
What is a 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.
10 of 14
What is a complete graph?
A complete graph is a graph in which every vertex is directly connected by an edge to each of the other vertices.
11 of 14
What is an isomorphic graph?
Isomorphic graphs show the same amount of information but are drawn differently.
12 of 14
What is an adjacency matrix?
An adjacency matrix records the number of direct links between vertices.
13 of 14
What is a distance matrix?
A distance matrix records the weights on the edges. Where there is no weight, this is indicated by "-"
14 of 14
Other cards in this set
Card 2
Front
What is a path?
Back
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.
Comments
No comments have yet been made