A graph, each of whose vertices and edges belongs to the main graph.
4 of 20
Weight
A number associated with each edge is called its weight.
5 of 20
Weighted graph
Also known as a network. A graph whose edges have a weight.
6 of 20
Degree of a vertex
Also known as the valency of a vertex. The number of edges incident to it.
7 of 20
Path
A finite sequence of edges, such that the end vertex of one edge of the sequence is the start vertex of the next, and in which no vertex appears more than once.
8 of 20
Cycle
Also known as a circuit. A closed path i.e. the end vertex of the last edge is the start vertex in the first edge.
9 of 20
Connection
A path between two vertices.
10 of 20
Connected graph
A graph whose vertices are all connected.
11 of 20
Directed edges
Edges which have a direction associated with them.
12 of 20
Digraph
A graph which is made up of edges which have directions associated with them.
13 of 20
Tree
A connected graph with no cycles.
14 of 20
Spanning tree
A subgraph which includes all the vertices of the main graph and is also a tree.
15 of 20
Minimum spanning tree
Also known as a minimum connector. A spanning tree such that the total length of its arcs is as small as possible.
16 of 20
Complete graph
A graph in which each of the n vertices is connected to every other vertex.
17 of 20
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.
18 of 20
Matching
The pairing of some or all of the elements of one set, X, with elements of a second set, Y.
19 of 20
Complete matching
A matching where every member of X is paired with a member of Y.
20 of 20
Other cards in this set
Card 2
Front
Also known as nodes. Points on a graph.
Back
Vertices
Card 3
Front
Also known as arcs. Lines on a graph.
Back
Card 4
Front
A graph, each of whose vertices and edges belongs to the main graph.
Back
Card 5
Front
A number associated with each edge is called its weight.
Comments
No comments have yet been made