2
$\begingroup$

An edge will have the same vertices as another edge that it is parallel to, so how can it be uniquely described?

$\endgroup$
1
  • $\begingroup$ "An edge will have the same vertices as another edge that it is parallel to" - no it won't. $\endgroup$
    – nbubis
    May 31 '13 at 0:18
3
$\begingroup$

I would prefer to use a variant of the second definition offered by Zev. A multigraph has a set of vertices $V$, a set of edges $E$. The connection between vertices and edges can be described by a relation on $V\times E$, such that each edge is incident with one or two vertices (just one if you're not inclined to allow loops). Or it can be described by a function that assigns to each edge either one vertex or an unordered pair of vertices.

One place where multigraphs force themselves on us is when we consider duals of plane graphs. So we need to work with embeddings of multigraphs and in this situation the multiset approach would be a little awkward. My suspicion is that working graph theorists would not usually use the multiset definition (but I have not carried out a survey).

$\endgroup$
2
$\begingroup$

For an undirected multigraph, we simply have a multiset of edges, not a set. Thus, if $V=\{a,b,c\}$, we might have $$E=\{[(a,b),2],[(a,c),3]\},$$ which specifies that there are two edges connecting vertices $a$ and $b$, and three edges connecting vertices $a$ and $c$. We still can't technically distinguish "individual edges" between the same vertices; all we know is how many edges there are between any two vertices. However, for many purposes, that's all that's really necessary.

If you want to point to individual edges, you could take the approach typically used for directed multigraphs: we take a quadruple $(V,E,s,t)$, where $V$ is the set of vertices, $E$ is the set of edges, $s:E\to V$ is the function taking an edge to the vertex it starts at (its "source") and $t:E\to V$ is the function taking an edge to the vertex it ends at (its "target"). Then edges $e_1,e_2\in E$ are parallel with the same direction if $s(e_1)=s(e_2)$ and $t(e_1)=t(e_2)$, and parallel with opposite directions if $s(e_1)=t(e_2)$ and $t(e_1)=s(e_2)$.

$\endgroup$

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.