Restknoten

Restknoten, also known as remainder nodes or residual nodes, are a concept primarily found in graph theory and network flow problems. In the context of a flow network, a residual graph is created to represent the remaining capacity of edges after a certain amount of flow has been assigned. A restknoten is a node within this residual graph.

The residual graph plays a crucial role in algorithms like the Ford-Fulkerson method for finding the maximum flow in a network. When flow is pushed along an edge from node u to node v, the capacity of the forward edge (u, v) decreases in the residual graph, and a backward edge (v, u) is often created with a capacity equal to the amount of flow pushed. This backward edge represents the ability to "cancel" or reroute flow if a better path is found.

Therefore, restknoten are simply the vertices that exist in this dynamic residual graph. Their presence and the capacities of the edges connected to them indicate how much additional flow can be sent through the network. The existence of a path of positive capacity edges from the source to the sink in the residual graph signifies that the maximum flow has not yet been reached, and augmenting the flow along such a path is possible.