Terminology for Graph Theory

HideShow resource information
Graph
Collection of vertices & edges.
1 of 19
Vertex/Node
The dots in a graph (usually where 2 or more edges meet, but not necessarily).
2 of 19
Edge/Arc
A line between two vertices.
3 of 19
Tree
A graph with no cycles.
4 of 19
Order (degree) of a vertex or Valency
The number of edges starting or finishing at that vertex.
5 of 19
Simple graph
A graph with no loops or multiple edges.
6 of 19
A path
A route from one vertex to another which does not repeat any edge.
7 of 19
A cycle
A route starting and finishing at the same vertex.
8 of 19
Connected graph
A graph in which there is a route from each vertex to any other vertex.
9 of 19
Complete graph
A simple graph in which every pair of vertices is connected by an edge.
10 of 19
Bipartite graph
One in which the vertices are in two sets and each edge has a vertex from each set.
11 of 19
Planar graph
One which can be drawn with no edges crossing.
12 of 19
Sub graph
Any set of edges & vertices taken from a graph is a sub-graph.
13 of 19
Hamiltonian cycle
A cycle that visits every vertex of the graph.
14 of 19
Eulerian cycle
A cycle that travels along every edge of the graph.
15 of 19
Eulerian graph
A gaph with no odd verticles.
16 of 19
Di-graph
A graph in which the arcs have a particular direction.
17 of 19
Spanning tree
A subgraph of a graph which includes all the vertices of the graph and is also a tree.
18 of 19
Minimum spanning tree
A spanning tree such that the total length of edges is as small as possible.
19 of 19

Other cards in this set

Card 2

Front

The dots in a graph (usually where 2 or more edges meet, but not necessarily).

Back

Vertex/Node

Card 3

Front

A line between two vertices.

Back

Preview of the back of card 3

Card 4

Front

A graph with no cycles.

Back

Preview of the back of card 4

Card 5

Front

The number of edges starting or finishing at that vertex.

Back

Preview of the back of card 5
View more cards

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »