Bipartite matching - Githubissues

darwinrlo / public

0 stars 0 forks source link

Bipartite matching #10

Open darwinrlo opened 4 years ago

darwinrlo commented 4 years ago

Definition: bipartite graph

A connected, undirected graph is bipartite iff the vertices of the graph can be grouped into two mutually exclusive subsets, called partitions, such that all edges cross the partition.

Note that, since the graph is connected, each vertex is incident to an edge.

darwinrlo commented 4 years ago

Claim: Every path in a bipartite graph zig-zags between the two partitions.

Since the graph is bipartite ー that is, all the edges cross the partition ー there are no edges between vertices in the same partition. So every edge of a path leads to the other partition, which creates a zig-zag shape.

darwinrlo commented 4 years ago

Claim: A path starting in one partition will end up in the other partition after an odd number of edges.

A zig takes the path to the other partition. A zag brings it back.
For every edge that is a zig, if another edge follows it, it is a zag.
After the first edge, a zig, every other edge -- like the first one, odd-numbered edges -- is also a zig. After a zig -- or an odd number of edges -- the path is in the other partition.

darwinrlo commented 4 years ago

Definition: alternating path w.r.t. a matching.

An alternating path w.r.t. to a matching is a path between two vertices in different partitions that, in addition to zig-zagging between the two partitions, also zig-zags between be outside and being inside the matching.

darwinrlo commented 4 years ago

Definition: matching

A matching of a bipartite graph is a selection of the edges such that no two vertices in either partition are in more than one selected edge.