4

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 :

Insect name:

country

city

tunnel

Math name:

graph

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

cvertices'

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

disconnected.