4
$\begingroup$

An edge set of a graph is a set of doubletons, pairing edges. For example: Graph

has an edge set of $\{\{6,4\},\{4,5\},\{4,3\},\{5,2\},\{5,1\},\{3,2\},\{1,2\}\}$. A set, by definition, cannot have duplicate elements, else it is not a set.

Multigraph

is a multigraph. All graphs have edge sets, yet the edge set of the multigraph would have to contain duplicate sets in its edge set to properly represent its edges, but then it wouldn't have an edge set, because a set cannot possibly have duplicate elements. I suppose its edge set would be $\{\{1,3\},\{1,2\},\{2,4\},\{2,4\},\{2,4\}\}$, but then it wouldn't be a set, having three instances of the same member.

Question

How do I represent the edge set of a multigraph, which have multiple edges along the same vertices?

$\endgroup$
5
$\begingroup$

I believe the term multiset is used to refer to a set that may have duplicate elements. This term makes sense here, especially since it is cohesive with the term multigraph. If you really want to keep the edgeset as a set you could let each element of the egdeset be a pair that consists of the edge itself and the mutliplicity of the edge. So the edgeset of the multigraph you posted would be $$ \{(\{1,2\},1),(\{1,3\},1),(\{2,4\},3)\} $$ If we go with the multiset term, the question then becomes this: should we call it a multiedgeset or an edgemultiset?

$\endgroup$
  • 1
    $\begingroup$ I would refer to the "edge set" and "edge multiset". I've never seen "edgeset" (or "vertexset", for that matter) run into a single word. $\endgroup$ – David Richerby Jan 2 '15 at 10:42
7
$\begingroup$

There are different ways to do that and it really depends on what you want to do.

A very nice way is to define an undirected multigraph as $G=(V,E,\text{sig}: E\to \mathcal{P}_2(V))$. Here, $V$ is just any set, we call it vertices, $E$ is just any set, let us call them edges and $\text{sig}: E\to \mathcal{P}_2(V)$ is a map that tells us for a given edge $e\in E$, which two vertices $e$ connects.

Why it is superior to the multiset-option?

Alternatively, you can define $E$ as a multiset, i.e. $E \subseteq \mathcal{P}_2(V)$ together with a multiplicity-map $m: E\to \mathcal{N}$.

I prefer the first way with this signature map $\text{sig}$ over the multiset variant, because it matches the intuition of "different" edges better. IMO the multiset-option describes edges with multiplicities but not multiple edges.

Assume you want to express something like "Take two different edges $e_1$ and $e_2$" formally.

For the $\text{sig}$-option you say "Take $e_1,e_2 \in E$ with $e_1 \not = e_2$". But for the multiset-option, it gets difficult because just saying "Take $e_1,e_2 \in E$, $e_1\not=e_2$" is not enough!

$\endgroup$
  • $\begingroup$ I'm not familiar with the notation $\mathcal{P}_{2}(V)$. As long as it allows for loops (one-element subsets of $\mathbb{V}$), then I would agree with this definition. :-) $\endgroup$ – ml0105 Jan 2 '15 at 5:00
  • $\begingroup$ Normally $\mathcal{P}_k(V) := \{ s \in \mathcal{P}(V) \mid \#s = k\}$. So if you don't want loops, take $\mathcal{P}_2(V)$, but if you want loops, take $\mathcal{P}_2(V) \cup \mathcal{P}_1(V)$. And if you want directed graphs, take $V\times V$. $\endgroup$ – Thorsten Jan 2 '15 at 5:02
  • $\begingroup$ Thanks for clarifying the notation! Yes- multigraphs are defined to include loops and multiple edges, so $\mathcal{P}_{2}(V) \cup \mathcal{P}_{1}(V)$ should be the codomain of the function. $\endgroup$ – ml0105 Jan 2 '15 at 5:27
  • $\begingroup$ What is the $\text{sig}$ function? $\endgroup$ – Conor O'Brien Jan 2 '15 at 6:26
  • 1
    $\begingroup$ $\text{sig}$ is part of the graph structure. $E$ is the set of edges and for a concrete edge $e$, $\text{sig}(e)$ tells which vertices $e$ connects. $\endgroup$ – Thorsten Jan 2 '15 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.