A bipartite graph can be divided into two sets of nodes where all edges have one end in each. The graph must be undirected. In a matching, no element of a set may appear in more than one pair ( each node may appear in at most one edge). Perfect edge means exactly one edge for every node(no disconnected nodes). These concepts are firmly imbued with Network Flow. We will use concepts shown by Network Flow to attempt to solve the problem: What is the size of the largest matching in a some bipartite graph G? As we will learn, this problem requires advanced techniques to solve which we have not yet covered.

First, we need to understand the basics of flow networks. Flow is what travels along the edges in a flow network between nodes. Each edge has a capacity Ce representing the maximum amount of flow that it can transport. Further, flow networks must have two special nodes: a source node which the original flow comes from and a sink node which is the final node receiving the flow(takes all that is transported through). There are several required conditions for a graph to represent a flow network. No node may exceed its capacity(capacity condition) and the amount of flow from a given edge cannot exceed the amount of flow into it(conservation condition). The maximum flow problem involves finding a flow of maximum possible value in some flow network. To solve this, we will focus on how some node's capacities put bounds on flow. A “cut” of a flow network is basically just a path that some quantity of flow follows between nodes from source to sink. Unfortunately, Dynamic Programming does not work here. It is important to note that we can divide flow distribution along multiple cuts in our network. For this reason, we cannot appear to use a greedy algorithm either. A graph representation made after the flow has been distributed is called a residual graph. Capacity values are placed by each edge(now represent actual expected flow values) and each node can have both backward and forward edges. A backward edge is made when flow is diverted from the current path back to go on a different cut. Flow can only be diverted when the current node's capacity is exceeded. Clearly, residual graphs will often have more edges than non residual graphs. New capacities of each edge are called residual capacities. Bottleneck capacity is the lowest capacity of any node in some path(cut?). We build a function augment to manage the flows of various edges in residual graphs. For each edge in some cut, if the edge is forward, its flow is increased by the bottleneck and if it is backward its flow is decreased by the bottleneck. Finally, we can use a simple algorithm to compute the residual graph with max flow. All that this algorithm does is apply the augment function to some s-t path in the graph while an s-t path exists. We call this the Ford-Fulkerson Algorithm. This section was a little complicated at times but I found the material interesting and intuitive. This gets an 8/10.

We now dive into an explanation of why the Ford Algorithm works. Clearly, the conservation principle applies to cuts just as it applies to individual edges: the amount of flow going into a cut can never be less than the amount of flow which leaves. Further, we define the capacity of a cut as the sums of the capacities of the nodes contained within it. We know that if a flow does not allow a path in the resulting residual graph, then it must have the highest capacity of all flows and lowest bottleneck. I am confused how the book derived this or what exactly it means(very unclear). This section gets a 2/10. It appears to make jumps and concepts that should be intuitively simple into symbolic monstrosities. Seems too dense and abstract to understand without further discussion. I can still grasp most of the concepts but the proofs and wording provided in the book are very hard to make sense of.