Flashcards in Definitions Deck (33):
The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.
A graph whose vertices can be divided into two sets such that no two vertices in the
same set are adjacent.
A walk that begins and ends at the same vertex, and has no repeated edges.
Complement of a graph G
A graph with the same vertices as G but which has an edge between any two
vertices if and only if G does not.
A bipartite graph in which every vertex in one set is joined to every vertex in the
A simple graph in which each pair of vertices is joined by an edge.
A graph in which each pair of vertices is joined by a path.
A walk that begins and ends at the same vertex, and has no other repeated vertices.
Degree of a vertex
The number of edges joined to the vertex; a loop contributes two edges, one for
each of its end points.
A graph that has at least one pair of vertices not joined by a path.
A circuit that contains every edge of a graph.
A trail that contains every edge of a graph.
Consists of a set of vertices and a set of edges.
between two simple
graphs G and H
A one-to-one correspondence between vertices of G and H such that a pair of
vertices in G is adjacent if and only if the corresponding pair in H is adjacent.
A cycle that contains all the vertices of the graph.
A path that contains all the vertices of the graph.
An edge joining a vertex to itself.
A spanning tree of a weighted graph that has the minimum total weight.
Occur if more than one edge joins the same pair of vertices.
A walk with no repeated vertices.
A graph that can be drawn in the plane without any edge crossing another.
A graph without loops or multiple edges.
Spanning tree of a
A subgraph that is a tree, containing every vertex of the graph.
A graph within a graph.
A walk in which no edge appears more than once.
A connected graph that contains no cycles.
A sequence of linked edges.
A graph in which each edge is allocated a number or weight.
A tree in which each edge is allocated a number or weight.
Chinese postman problem
To determine a cycle where each vertex is visited once only, returning to the original vertex of least total weight
Travelling salesman problem
To determine the shortest route that visits each vertex and returns to the original vertex, of least weight.
Pigeon Hole Principle
If kn+1 objects (where k, n are members of the positive integers) are divided into n groups, there will be a group that contains at least k+1 objects.