Proposition 3.5.4 — a forest has a source with at most one successor or a sink with exactly one predecessor
ProvedProjSchedTW.NetPresentValue.forest_source_or_sinkforestgraph-theoryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be the arc set of a directed forest on a finite nonempty node set : there are no loops and no pair of opposite arcs, and the underlying undirected graph has no cycle (so every weakly connected component is a tree). A source is a node without predecessors and a sink a node without successors. Then there is a node such that
In the book this property of forests (Berge 1976) is what makes the steepest descent direction problem for the net present value objective solvable by repeatedly removing such a node from the spanning forest.
Preamble
import Mathlib
Formal statement
namespace ProjSchedTW.NetPresentValue
/-- Proposition 3.5.4 (p. 252). A forest (a directed graph each of whose weakly connected
components is a tree, §3.2, p. 216) on a finite nonempty node set `V`, given by its arc set `A`
(no loops, no pair of opposite arcs, underlying undirected graph acyclic), possesses a source (no
predecessor) with at most one successor or a sink (no successor) with exactly one predecessor. -/
theorem forest_source_or_sink {V : Type} [Fintype V] [DecidableEq V] [Nonempty V]
(A : Finset (V × V)) (hasymm : ∀ a b : V, (a, b) ∈ A → (b, a) ∉ A)
(hacyc : (SimpleGraph.fromRel (fun a b => (a, b) ∈ A)).IsAcyclic) :
∃ v : V,
((∀ u, (u, v) ∉ A) ∧ (A.filter (fun e => e.1 = v)).card ≤ 1) ∨
((∀ w, (v, w) ∉ A) ∧ (A.filter (fun e => e.2 = v)).card = 1) := by sorry
end ProjSchedTW.NetPresentValue
Source
Neumann, Schwindt & Zimmermann, Project Scheduling with Time Windows and Scarce Resources, 2nd ed., Springer 2003, p. 252, Proposition 3.5.4; definition of tree and forest p. 216
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.