|
|
Arturo Magidin wrote:
> In article <1162237857.650549.279020@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> MoeBlee <jazzmobe@xxxxxxxxxxx> wrote:
> >I know too little about graph theory, so I have a beginner's question.
> >
> >An edge is an unorded pair of vertices.
>
> That is one way of doing it, yes. But there are others.
>
> For example, you can define a graph as an ordered pair, the first
> being a set V, and the second being an element of {0,1}^{V x V} (maps
> from VxV to {0,1}) which is symmetric ( (a,b) and (b,a) map to the
> same thing).
That makes sense. Though, personally, I would call the function
'commutative' rather than 'symmetric'.
> When V is finite of cardinality n, you can take it as a
> 0,1 n x n matrix which is symmetric.
Okay, I see that.
> >And I've seen ordered pairs used so that there can be two edges between
> >vertex b and vertex c, one edge going in one direction and the other
> >edge going in the opposite direction.
>
> A "graph" with directed edges is often called a "directed graph" or a
> "digraph". In that case, you can consider edges as being ordered
> pairs; or you can simply drop the symmetric condition on the map above.
I see that.
> >But how do we rigorously define having more than two edges between
> >vertex b and vertex c? In other words, how do we define what we picture
> >when we draw more than two lines between vertex b and vertex c?
>
> You can think of a graph as a set V and a map (VxV)->N (the natural
> numbers); then f(a,b) is the number of edges between a and b.
But that doesn't tell us what an ege IS. That just tells us how MANY
edges there are between, say, b and c, without telling us WHAT the
edges are. Maybe that's okay, since maybe all we need is to know "how
many" (i.e., just to have the function you mentioned)? But if we need
to have specific objects to be the edges, then I can see how to do
that, but my suggestion is a little more complicated (though not too
complicated) than the function you mentioned.
Thanks,
MoeBlee
|
|