Definition of graph, using half-edges.

1.3k Views Asked by At

There are several valid definitions of a (multi)graph. Let me quote the one I use (ref.1 §1.1):

Definition: A graph is a triple $(V,E,\psi)$ where $V$ is the vertex set, $E$ the edge set, and $\psi\colon E\to V^2$ a relation that associates with each edge an unordered pair consisting of two vertices (not necessarily distinct).

An alternative definition is that a graph is a set of half-edges (e.g., ref.2, §5.1):

Definition: A graph is a set of half-edges along with a set $V$ of disjoint subsets of half edges known as vertices which partition the set of half edges, and a set $E$ of disjoint pairs of half edges known as internal edges.

How is this latter definition understood in the context of the former? What is the precise definition of a half-edge, when we regard a graph as a triple $(V,E,\psi)$?

References.

  1. Bondy, Murty - Graph Theory with Applications.

  2. Yeats - A Combinatorial Perspective on Quantum Field Theory.

1

There are 1 best solutions below

6
On BEST ANSWER

Starting from the triple $(V,E,\psi)$, or from basically any other definition of graphs, we have a half-edge $h_{v,e}$ for every pair $(v,e) \in V \times E$ such that $v$ is incident to $e$. (In the formal definition with $\psi$, a pair $(v,e)$ such that $v \in \psi(e)$.)

If $e$ is a loop, we should probably be more careful and have two half-edges $h_{v,e}^1$ and $h_{v,e}^2$, because we still want the edge to correspond to a pair of half-edges.

Then a vertex $v$ in the original definition corresponds to the set of half-edges with vertex $v$, and an edge $e$ in the original definition corresponds to the set of (exactly two) half-edges with edge $e$.