#
Chapter
1
#
Notation of Knots and Links
##
1.1
Basic graph theory
**A
***graph*
G consists of a set V(G) of *vertices* and a set E(G) of edges, such
that each edge is *incident* with two (not necessarily distinct) vertices.
The edge is then said to *join* these two vertices, which are called
the
*endpoints* of the edge, and are said to be *adjacent*. Two
edges are *adjacent* if they have a common endpoint. An edge which
joins a vertex to itself is called a *loop*,
while k edges which join the same pair of vertices are called *k-multiple*
edges, and the corresponding graph is called a *multigraph*. If a
multigraph contains only single and 2-multiple (or double) edges, it is
called a *2-graph*. A graph without multiple edges and loops is called
a *simple graph*. A graph without loops is called a *proper*,
or
*reduced* graph.
**If we distinguish the
endpoints of edges, treating them as ***ordered pairs* of vertices,
we obtain *oriented graphs* (or *digraphs*).
**A graph is usually drawn
with enlarged (labelled) dots for the vertices, and straight lines (or
sometimes curves) for edges in such a way that a vertex and an edge are
incident ***iff* they meet in the diagram. The actual placement of points
in the diagram, and whether the lines representing edges are straight,
curved or have to cross one another in any point other then vertex, is
irrelevant.
**The
***valence*
(or
*degree*) of a vertex is the number of edges which are incident
to it. (In a graph with loops, we usually count a loop-edge twice). The
valence of a vertex v will be denoted d(v).
**A vertex of a graph G
is ***single* or *isolated* if its valence
is 0. Usually, a non-oriented graph without isolated vertices will be given
by the list of *unordered pairs* representing edges. In the case of
digraphs, ordered pairs will represent oriented edges. A graph can also
be given by its *adjacency matrix*: a list where in every part the
first datum is a vertex followed by the sequence of vertices adjacent to
it, where the order of adjacent vertices is irrelevant.
**A graph in which all vertices
are k-valent will be called a ***k-valent graph* (or *k-regular graph*).
A graph containing only 3- and 4-valent vertices is called (3,4)-valent
graph. In considering shadows and projections of KLs, 4-valent graphs will
play the main role.
**Among the graphs corresponding
to the five Platonic regular polyhedra, the ***tetrahedron*,
*cube*
and *dodecahedron* graphs are 3-valent, the
*octahedron* graph is 4-valent,
and the *icosahedron* graph is 5-valent.
**
**
**
** |