|
|
In article <1162320926.102162.305360@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
MoeBlee <jazzmobe@xxxxxxxxxxx> wrote:
>Arturo Magidin wrote:
[...]
>> 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)?
Indeed. Usually, you only care about how many (if any) edges go from
one vertext to another. You can solve the problem of multiplicities by
considering multisets of ordered pairs (for directed graphs), or
multisets of unordered pairs (for graphs with no directed edges).
Or, if you insist on having some sort of "objective" interpretation,
you can think of a graph as a kind of topological complex, with the
vertices being the 0-simplexes and the edges being 1-simplexes that are
glued to 0-simplexes at the ends. Then there is no problem with
multiple edges, or with edges going from vertex to itself
(self-loops): they just correspond to different simplexes.
>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.
Sure.
Or as someone else suggested, you can have a graph be an ordered
quadruple: (V,E,i,t), where V and E are sets, i:E->V and t:E->V are
functions, and you think of V as being the "vertices", E as being the
"edges", i(e) as being the 'initial endpoint of e' and t(e) as being
the 'terminal endpoint of e'. Mutliples edges would correspond to
multiple elements e1,...,ek in E with {i(ej),t(ej)} = {i(e1),t(e1)}
for j=1,...,k (if you want undirected edges; if you want directed
edges, you would require i(ej)=i(e1) and t(ej)=t(e1)). You can impose
any number of conditions (e.g., no "self edges") by specifying
properties of the function. Then an edge ->is<- "an element of E".
As usual, one does not really worry about ->what<- the things are, but
about what their properties are. (We don't usually care about the
precise definition of an ordered pair, we just care about the
important property that (a,b)=(x,y) if and only if a=x and b=y,
whether this is achieved through Kuratowski's definition, or some
other definition; likewise, we usually don't really care about "what"
an edge is, we care about the fact that "u is adjacent to v" if and
only if there is "an edge from u to v", and that "u is n-adjacent to
v" [or some other terminology] if and only if there "are at least n
distinct edges from u to v", whatever the actual realization of "edge"
may be).
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
|
|