consists of vertices (nodes) which are connected by edges (arcs)
1 of 19
Subgraph
is part of a graph
2 of 19
Weighted graph (network)
graph has a number associated with each edge (its weight)
3 of 19
The degree or valency (or order) of vertex
the number of edges incident to it
4 of 19
A path
is a 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
5 of 19
A walk
is a path in which you are permitted to return to vertices more than once
6 of 19
A cycle (circuit)
is a closed 'path', i.e the end vertex of the last edge is the start vertex of the first edge
7 of 19
thw vertices are connected
if there is a path between them. A graph is connected if all its vertices are connected
8 of 19
A loop
is an edge that starts and finishes at the same vertex
9 of 19
A simple graph
is one in which there are no loops and not more than one edge connecting any pair of vertices
10 of 19
Directed edges
if the edges of a graph (digraph) have a direction associated with them
11 of 19
Tree
is a connected graph with no cycle
12 of 19
Spanning tree
G is a subgraph which includes all the vertices of G and is also a tree
13 of 19
Bipartite graph
consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices withon a set
14 of 19
Complete graph
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 donated Kn
15 of 19
Complete bipartite graph
graph in which there are r vertices in set X and s vertices in set Y
16 of 19
Isomorphic graph
show the same information but are drawn differently
17 of 19
Adjacency matrix
records the number of direct links between vertices
18 of 19
Distance matrix
recirds the weights on the edges. Where is no weight, this is indicated by '-'
19 of 19
Other cards in this set
Card 2
Front
is part of a graph
Back
Subgraph
Card 3
Front
graph has a number associated with each edge (its weight)
Back
Card 4
Front
the number of edges incident to it
Back
Card 5
Front
is a 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