1.2 NOTATION , AN D A CATALOG
This can be thought o f as a
disconnected grap h wit h 9
vertices, o r a s two separat e
connected graphs .
Any grap h i s just a collectio n o f connected graphs ; thes e ar e calle d th e compo -
nent s o f th e graph .
The graph s w e have bee n studyin g ar e presente d a s drawing s o n paper . I t
is eas y t o inven t graph s whic h ar e describe d i n othe r ways . Fo r example , w e
can mak e a grap h whos e vertice s ar e al l o f th e tenni s player s i n th e world , an d
where a n edge connects tw o players if they hav e played tennis together. W e hav e
defined a graph , althoug h i t woul d no t b e feasibl e t o actuall y dra w it . Anothe r
graph ca n b e mad e b y lettin g th e vertice s b e th e countrie s o f th e world , an d
having a n edg e connect tw o countries i f those countrie s borde r eac h other . Wit h
the hel p o f a ma p i t woul d b e possibl e t o dra w thi s graph . I t i s amusin g t o
invent fancifu l graph s an d the n tr y t o determin e what propertie s they have . Fo r
example, i s th e tenni s playe r grap h connected ? I f i t is , tha t woul d mea n eac h
tennis playe r ha s playe d someon e wh o ha s playe d someon e wh o has . . . playe d
Jimmy Connors . Th e pla y Six Degrees of Separation mentions , informally , th e
graph whos e vertice s ar e al l o f th e peopl e i n th e world , wit h edge s connectin g
people wh o kno w each other . Th e titl e o f th e pla y come s from speculatio n tha t
you can ge t fro m an y one vertex to any other verte x b y crossing at mos t 6 edges.
In orde r t o mak e a n organize d stud y o f graphs, w e must impar t a fe w mor e
rules. Usuall y we do not allo w our graphs to have more than one edge connectin g
two vertices , an d w e do no t allo w a n edg e t o connec t a verte x t o itself .
A graph with
multiple edges
A graph with loop s
Unless we state otherwise , a 'graph' i s a 'grap h withou t loop s or multipl e edges.*
We classif y graph s accordin g t o ho w man y vertice s the y have . Her e i s a
Previous Page Next Page