1. NETWORK S
answer is to discover it yourself. Sometime s this will mean spending a long time
on one Task. Tha t i s the nature of mathematical discovery . Yo u will find that
discovering your own mathematics is not a t al l like trying to learn mathematic s
which has already been discovered b y someone else.
1.2 Notation , an d a catalo g
The ideas of the previous section fall under the mathematical topic of graph
theory. Th e fanciful ide a of insects crawling through dark tunnels will continue
to be useful, bu t w e will switch to using the mathematical terminology . Her e is
how to translate :
point o r vertex
line or edg e
An exampl e sentenc e is , " A graph i s made u p o f points an d lines. " Not e tha t
is the plural of 'vertex/ so we can also say, "A graph consists of vertices
connected b y edges."
The actual picture we draw of a graph is called a graph diagram. Jus t a s
the insect s could not distinguis h between certain countries, the same graph can
be represented b y many differen t grap h diagrams . Th e onl y important featur e
of th e grap h i s ho w th e variou s vertice s ar e connected . Eac h grap h diagra m
will hav e additiona l features , suc h a s the length s o f th e edge s and th e relativ e
position o f th e vertices , bu t thes e aspect s o f th e diagra m hav e nothin g t o d o
with th e graph itself.
Here are three diagram s of the same graph:
A diagra m ma y appea r t o sho w tw o edge s crossing , bu t i f ther e i s no t a
vertex a t th e junction the n th e edges do not actuall y meet . Thin k o f it a s two
insect tunnel s which pass each other bu t d o not intersect . Th e topic of drawing
graphs without crossin g edges will be explored i n a later section .
A grap h i s called connecte d i f w e can ge t fro m an y verte x t o an y othe r
vertex b y travelin g alon g edge s o f th e graph . Th e opposit e o f connecte d i s