Prescribed and bounded indegree orientations #
For a finite multigraph G, loops and parallel edges allowed, and natural vertex bounds
a ≤ b, an orientation with a v ≤ indegree v ≤ b v at every vertex exists exactly when every
vertex set S satisfies
|E(S)| ≤ b(S), whereE(S)is the set of edges internal toS, anda(S) ≤ |I(S)|, whereI(S)is the set of edges incident withS.
With a = b = d this is Hakimi's theorem: an orientation with indegree d exists exactly
when d sums to the number of edges and |E(S)| ≤ d(S) for every S. The one-sided bounds and
the outdegree forms are corollaries.
The proof is a reduction to interval-excess feasibility over ℤ. The edge-to-endpoint network
Graph.EndpointHom has a node for each actual edge and each actual vertex, and a capacity-one
arrow from an edge node to each distinct end of the edge, so that a loop has a single arrow.
Prescribing excess -1 at edge nodes and excess in [a v, b v] at vertex nodes, the integral
feasible assignments are exactly the orientations within the bounds: the unit leaving an edge
node goes to the chosen head (Graph.orientationEndpointEquiv). The cut criterion of
TauCeti.ExcessIntervalFlow.nonempty_iff for this network reduces to the two displayed families
of inequalities (Graph.forall_cutBound_endpointBound_iff).
Main declarations #
Graph.EndpointHom: the arrows of the edge-to-endpoint network.Graph.orientationEndpointEquiv: orientations within vertex bounds are the integral feasible assignments of the edge-to-endpoint network.Graph.exists_orientation_indegree_mem_Icc_iff: the bounded-indegree theorem.Graph.exists_orientation_indegree_eq_iff: Hakimi's prescribed-indegree theorem.
References #
- S. L. Hakimi, On the degrees of the vertices of a directed graph, J. Franklin Inst. 279 (1965), 290–308.
- A. Frank, Connections in Combinatorial Optimization, Oxford University Press, 2011.
The arrows of the edge-to-endpoint network of G. Its nodes are the actual edges and the
actual vertices of G. There is one arrow from each edge node to each distinct end of that
edge, so a loop has a single arrow, and there are no other arrows. The family is exposed so that
its Fintype instance compiles consistently in importing modules.
Instances For
Arrow sums in the edge-to-endpoint network only see arrows from edge nodes in T to vertex
nodes in T'.
The excess at an edge node is minus the total value leaving it.
The excess at a vertex node is the total value entering it.
Vertex bounds of the edge-to-endpoint network compare exactly as the bounds at vertex nodes.
The assignment of the edge-to-endpoint network sending the unit of each edge node to the chosen head of the edge.
Instances For
The head assignment takes values between 0 and 1.
The excess of the head assignment of an orientation is -1 at edge nodes and the indegree at
vertex nodes.
Edge-to-endpoint reduction. Orientations of G with indegrees between a and b are
equivalent to the integral assignments of the edge-to-endpoint network with arrow bounds 0 and
1, excess -1 at edge nodes, and excess between a and b at vertex nodes. An orientation
sends the unit of each edge node to the chosen head of the edge.
Instances For
The orientation of a feasible assignment of the edge-to-endpoint network chooses as head of an edge the end whose arrow carries the edge's unit.
The indegree of the orientation recovered from a feasible endpoint assignment is the excess at the corresponding vertex node.
Reduction of the cut inequalities. For the edge-to-endpoint network, the cut inequalities
over all sets of nodes are equivalent to |E(S)| ≤ b(S) and a(S) ≤ |I(S)| over all sets
S of vertices.
Bounded-indegree orientations. For vertex bounds a ≤ b, a finite multigraph has an
orientation with every indegree between a and b exactly when every vertex set S has at most
b(S) internal edges and at least a(S) incident edges.
A finite multigraph has an orientation with indegrees between a ≤ b, or some vertex set
has more than b(S) internal edges or fewer than a(S) incident edges.
Upper-bounded indegrees. A finite multigraph has an orientation with every indegree at
most b exactly when every vertex set S has at most b(S) internal edges.
Lower-bounded indegrees. A finite multigraph has an orientation with every indegree at
least a exactly when every vertex set S has at least a(S) incident edges.
Hakimi's theorem. A finite multigraph has an orientation with indegree d exactly when
d sums to the number of actual edges and every vertex set S has at most d(S) internal
edges.
A finite multigraph has an orientation with indegree d, or d does not sum to the number
of actual edges, or some vertex set S has more than d(S) internal edges.
Outdegree forms #
The outdegree form of Graph.exists_orientation_indegree_le_iff.
The outdegree form of Graph.exists_orientation_le_indegree_iff.
The outdegree form of Hakimi's theorem Graph.exists_orientation_indegree_eq_iff.