Network Models: Nodes, Arcs, Conservation, and Capacity
A network model represents a system using nodes and arcs. Nodes can represent locations, states, or junctions; arcs represent permitted connections. An arc may be directed, meaning flow has an allowed direction, or undirected when movement in either direction is modeled symmetrically.
In a flow network, each arc can have a capacity. A feasible assignment respects every capacity and satisfies flow conservation at intermediate transshipment nodes: absent a stated supply, demand, loss, or storage change, flow into the node equals flow out. A source has net outward flow; a sink has net inward flow.
To solve a network problem, first define what one unit of flow means, then list directions and capacities, then test feasibility before optimizing. A proposed high total is not valid if it overloads an arc or creates flow at an intermediate node.
A cut, which separates a source from a sink, can provide a rigorous upper bound on maximum flow through the capacities crossing from the source side.
Network models are broader than a particular project-scheduling chart or a transportation/assignment formulation. This topic focuses on the general representation and flow logic rather than those sibling applications.
Node J is an intermediate transshipment node with no supply, demand, storage change, or loss. If 9 units per minute enter J, what total flow must leave J for the assignment to be feasible?
A directed network has arcs S → A capacity 6, A → T capacity 4, S → B capacity 5, and B → T capacity 5. There are no other arcs. What is the maximum feasible flow from S to T?