Graph Theory Glossary
Chris Caldwell (C)
1995
This glossary is written to suplement the Interactive
Tutorials in Graph Theory written using the Web Tutor. Here we
define the terms that we introduce in our tutorials--you may need to go to the
library to find the definitions of more advanced terms. Please let me know of any corrections or suggestion!
[ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ]
- adjacent
- Two vertices are adjacent if they are connected by an edge.
- arc
- A synonym for edge. See graph.
- articulation point
- See cut
vertices.
- bipartite
- A graph is bipartite if its vertices can be partitioned into two
disjoint subsets U and V such that each edge connects a vertex from U to one
from V. A bipartite graph is a complete bipartite graph if
every vertex in U is connected to every vertex in V. If U has n
elements and V has m, then we denote the resulting complete bipartite
graph by Kn,m. The illustration shows
K3,3. See also complete
graph and cut
vertices.
- chromatic number
- The chromatic number of a graph is the least number of colors it takes to
color its vertices so that adjacent vertices have different colors. For
example, this graph has chromatic number three.
When
applied to a map this is the least number of colors so necessary that
countries that share non-trivial borders (borders consisting of more than
single points) have different colors. See the Four
Color Theorem.
- circuit
- A circuit is a path
which ends at the vertex it begins (so a loop
is an circuit of length one).
- complete graph
- A complete graph with n vertices (denoted Kn) is a graph with n vertices in which each
vertex is connected to each of the others (with one edge between each pair of
vertices). Here are the first five complete graphs:
- component
- See connected.
- connected
- A graph is connected if there is a path
connecting every pair of vertices. A graph that is not connected can be
divided into connected components (disjoint connected subgraphs). For
example, this graph is made of three connected components.
- cut vertex
- A cut vertex is a vertex that if removed (along with all edges incident
with it) produces a graph with more connected components than the original
graph. See connected.
- degree
- The degree (or valence) of a vertex is the number of edge ends at
that vertex. For example, in this graph all of the vertices have degree three.
In a digraph
(directed graph) the degree is usually divided into the in-degree
and the out-degree
(whose sum is the degree of the vertex in the underlying undirected graph).
- digraph
- A digraph (or a directed graph) is a graph
in which the edges are directed. (Formally: a digraph is a (usually finite)
set of vertices V and set of ordered pairs (a,b) (where a,
b are in V) called edges. The vertex a is the initial vertex
of the edge and b the terminal vertex.
- directed graph
- See digraph.
- edge
- See graph.
- Four Color Theorem
- Every planar
graph can be colored
using no more than four colors.
- graph
- Informally, a graph is a finite set of dots called vertices (or
nodes) connected by links called edges (or arcs). More
formally: a simple graph is a (usually finite) set of vertices V and
set of unordered pairs of distinct elements of V called edges.
Not all graphs are simple. Sometimes a pair of vertices
are connected by multiple edge yielding a multigraph.
At times vertices are even connected to themselves by a edge called a loop,
yeilding a pseudograph.
Finally, edges can also be given a direction yielding a directed graph (or digraph).
- in-degree
- The in-degree of a vertex v is the number of edges with v as
their terminal vertex. See also digraph
and degree.
- initial vertex
- See digraph.
- isolated
- A vertex of degree
zero (with no edges connected) is isolated..
- Kuratowski's Theorem
- A graph is nonplanar
if and only if it contains a subgraph homeomorphic to K3,3 or K5.
- length
- For the length of a path see path.
- loop
- A loop is an edge that connects a vertex to itself. (See the illustration
for degree
which has a graph with three loops.) See pseudograph
for a formal definition of loop.
- multigraph
- Informally, a multigraph is a graph with multiple edges between the same
vertices. Formally: a multigraph is a set V of vertices along, a
set E of edges, and a function f from E to
{{u,v}|u,v in V; u,v distinct}. (The function f shows
which vertices are connected by which edge.) The edges r and s
are called parallel or multiple edges if
f(r)=f(s). See also graph
and pseudograph.
- multiple edge
- See multigraph.
- node
- A synonym for vertex. See graph.
- out-degree
- The out-degree of a vertex v is the number of edges with v
as their initial vertex. See also digraph
and degree.
- parallel edge
- See multigraph.
- path
- A path is a sequence of consecutive edges in a graph and the length of the
path is the number of edges traversed. (This illustration shows a path of
length four.)
- pendant
- A vertex of degree
one (with only one edge connected) is a pendant edge..
- planar
- A graph is planar if it can be drawn on a plane so that the edges
intersect only at the vertices. (For example, of the five first complete
graphs all but the fifth, K5, is planar.)
- pseudograph
- Informally, a pseudograph is a graph with multiple edges (or loops)
between the same vertices (or the same vertex). Formally: a pseudograph
is a set V of vertices along, a set E of edges, and a function
f from E to {{u,v}|u,v in V}. (The function f
shows which vertices are connected by which edge.) An edge is a loop if
f(e) = {u} for some vertex u in V. See also graph
and multigraph.
- terminal vertex
- See digraph.
- undirected edge
- Edges in graphs
are undirected (as opposed to those in digraphs).
- valence
- See degree.
- vertex
- See graph.
If you came to this page from a Web Tutor tutorial, on your browser to return.
[ UT Martin | Back Door | Quick Guide ]
Chris Caldwell
caldwell@utm.edu