[math-fun] Primitive graph operations

I've been thinking a bit recently about representation and manipulation of graphical structure in computers, and specifically have a somewhat open ended question which some of you may have thought about. For matrix like operations, APL and Matlab provides a set of primitive ops (we can argue or not about how good they are...). What are the similarly "primitive" operations needed to flexibly create, modify, search, or otherwise manipulate graph structures? How do things change between directed and undirected graphs? Inquiring minds want to know.