CHAPTER 1
Directed graph s an d Cuntz-Kriege r familie s
A directed graph E =
,°,Z?1,r,
s) consist s o f tw o countabl e set s
E1
an d
functions r , s :
E1—
E°. Th e element s o f ar e calle d vertices an d th e element s
of E
1
ar e called edges. Fo r each edge e, 5(e ) i s the source o f e and r(e) th e range o f
e; i f 5(e ) = v an d r(e ) = w , the n w e als o sa y tha t i ; emits e and tha t it ; receives e ,
or tha t e is an edg e fro m v t o w. Al l th e graph s i n thes e note s ar e directed , s o w e
sometimes ge t laz y an d cal l the m graphs . I f ther e i s more tha n on e graph around ,
we migh t writ e r # an d SE t o emphasis e tha t w e ar e talkin g abou t th e rang e an d
source map s fo r E.
We usuall y dra w a grap h b y placin g th e vertice s i n a plane , an d drawin g a
directed lin e from 5(e ) t o r(e) fo r eac h edg e e G E
1.
I f necessary, w e label th e edg e
by it s name .
EXAMPLE
1.1I . f = {v,w}, E 1 = {e,/} , r(e ) = 5(e ) = v, s(f) = w an d
r(f)

vi
the n w e could dra w
(1.1) e P ' M W
An edg e which begin s an d end s a t th e sam e verte x v, lik e the edg e e in Exam -
ple 1.1, i s called a loop based at
v1.
A vertex whic h doe s no t receiv e an y edges , lik e
the verte x w i n Exampl e 1.1 , i s called a source. (Usin g th e wor d "source " i n tw o
ways doesn' t see m t o caus e confusion. ) A verte x whic h emit s n o edge s i s calle d a
sink.
Conversely, ever y drawin g lik e (1.1) determine s a graph .
EXAMPLE 1.2. Th e drawin g
eCv0f
represents a grap h E i n whic h = {v}, E 1 = {e,/ } an d e an d / ar e bot h loop s
based a t v. Notic e tha t w e ar e allowin g multipl e edge s betwee n th e sam e pai r o f
vertices; grap h theorist s ofte n don' t allo w this .
Drawings ar e a useful ai d when tryin g to follow argument s abou t graphs . How -
ever, ther e ar e man y way s to dra w th e sam e graph , s o it i s important t o remembe r
that tw o directe d graph s E an d F ar e th e sam e (formally , isomorphic) i f an d onl y
if there ar e bijection s 0 ° : F ° an d (f)
1
:
E1—
F
1
suc h tha t rp o
cpl
= o rp
and SF O cj)1 = fi° o SE
When i t doesn' t matte r wha t a n edg e is called, w e don't bothe r t o labe l i t i n a
drawing; whe n i t doesn' t matte r wha t a vertex i s called, w e denote i t b y a .
1 This i s standar d graph-theor y terminology . Unfortunatel y th e wor d "loop " i s use d i n th e
graph-algebra literatur e t o mea n a close d path .
5
http://dx.doi.org/10.1090/cbms/103/02
Previous Page Next Page