Last Update: 16 April 2009
Note: or material is highlighted |
Comment:
I.e., E is a set of (unordered) pairs (i.e., a set of "doubletons") of vertices.
Comments:
So, G = {{V}, {V, E}}.
How can we define multigraphs set-theoretically?
The problem is that we
need to allow multiple copies of elements to be in a set, and that's not
allowed by the laws of set theory.
(See Rosen, p. 113,
Def. 3: 2 sets are equal iff they have exactly the same elements.
Therefore, a set cannot have multiple "copies" of any element.)
What we need is a notion called a "multiset" (by mathematicians) or a
"bag" (by computer scientists).
The fundamental principle behind this
notion is that bags can have multiple copies of elements.
Let's
use angle brackets to denote bags. Then the bag
〈x, x〉 ≠ the bag
〈x〉
(whereas the set {x, x} = the
set {x}).
But wait: We want everything to be implemented as sets! And bags
aren't sets! So we need to implement bags as sets.
This can be done by
implementing each member of a bag as an ordered pair whose first element
is the bag-element and whose second element is a numeral
(something like
a subscript)—and, of course, you know how to implement ordered
pairs as sets! Here are some examples of how this can be done:
Bag | Set implementation |
---|---|
〈x〉 | {(x, 1)} |
〈x, y〉 | {(x, 1), (y, 1)} |
〈x, x〉 | {(x, 1), (x, 2)} |
〈x, x, y〉 | {(x, 1), (x, 2), (y, 1)} |
〈x, x, y, y〉 | {(x, 1), (x, 2), (y, 1), (y, 2)} |