Graphs/Matching - Revision history

Admin: /* Dietel Chapter 2: Matching on Graphs */

2017-08-28T00:30:20Z

Dietel Chapter 2: Matching on Graphs

← Older revision		Revision as of 00:30, 28 August 2017
Line 5:		Line 5:
	* Matching in general graphs		* Matching in general graphs

	Matching ~~- defined as a set M of independent edges on a graph G~~		===Definition of Matching===

	A matching ~~matches vertices in~~ a set U if ~~every~~ vertex in U is incident with an edge in M. (Recall from [[Graphs/Definitions]] that a vertex is incident with an edge e if v is in e, and two vertices are incident with an edge iff they are the endpoint of the edge. The notation for two vertices x and y being incident is xy.		A '''matching''' on a graph <math>G = (V,E)</math> is a set of M independent edges.

			A matching of <math>U subseteq V</math> (meaning U is either a subset of V or is equal to V) if each vertex in U is incident with an edge in the matching M. The vertices in U are '''matched''' by M.

			(Recall from [[Graphs/Definitions]] that a vertex is incident with an edge e if v is in e, and two vertices are incident with an edge iff they are the endpoint of the edge. The notation for two vertices x and y being incident is xy.

			Suppose we have a subgraph H that is on G, <math>H \subseteq G</math> . We are interested in finding a subgraph H such that the edges of H, E(H), form a matching of all the vertices in G. In this case, H is a 1-factor of G. The problem of finding such a subgraph H is the same as finding a spanning tree.

	===Matching in Bipartite Graphs===		===Matching in Bipartite Graphs===

	Consider two partitions A and B on the graph G consisting of disjoint subsets (V,E). We call A and B a '''bipartition'''.		Consider two partitions A and B of the vertices of a graph G consisting of disjoint subsets, i.e., <math>G = (V,E)</math>. We call A and B a '''bipartition'''.

	We wish to find ~~various~~ matchings in G.		We wish to find matchings on the graph G. In particular, we wish to find a matching with as many edges as possible.

	~~Begin~~ with arbitrary matchings, ~~which will help~~ to find matchings with maximum number of edges.		To do that, we can start with arbitrary matchings. We can use any given matching to find additional matchings, and use this to create a procedure to find matchings with a maximum number of edges.

	Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a, and that contains alternating edges that are ~~or are~~ not in the matching edge set.		Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a given vertex in A, which we denote a, and that contains alternating edges that are alternatively in, and not in, the matching edge set.

	Then we can use that to turn M into a larger matching - if we take the symmetric difference of M and E(P) - the edges that are included in the alternating path - we essentially invert the labels of whether the edge is or is not in the matching set. If the path ends at an unmatched vertex of B, this will increase the size of the matching set by 1 because there will be 1 more unmatched edges than matched edges, and when we flip the labels, we end up with 1 more matched edge than unmatched edges.		Then we can use that to turn M into a larger matching - if we take the symmetric difference of M and E(P) - the edges that are included in the alternating path - we essentially invert the labels of whether the edge is or is not in the matching set. If the path ends at an unmatched vertex of B, this will increase the size of the matching set by 1 because there will be 1 more unmatched edges than matched edges, and when we flip the labels, we end up with 1 more matched edge than unmatched edges.

			When searching for large matchings, alternating paths are important. The algorithmic problem of finding large matchings reduces to the problem of augmenting paths.

			===Outline of Remainder===

			This book has just completely left algorithms behind, and is solely concerned with the mathematics of graphs. This makes it hard to get through. From this point forward we'll be making some brief notes of the outlines of concepts Dietel covers, but not spending much time going through the details. Too many other things to focus on.

			Matching in bipartite graphs:
			* Maximum cardinality of a matching in G is equal to minimum cardinality of a vertex cover (Konig 1931)
			* Necessary and sufficient conditions for existence of a 1-factor? Marriage condition - every subset of A must have enough neighbors in B.
			* Marriage theorem: G contains a matching of A if and only if <math>\|N(S)\| \geq \|S\| \quad \forall S \subseteq A</math>
			* Corollary: if G is k-regular with k >= 1, then G has a 1-factor.
			* The marriage theorem is one of the most frequently applied graph theorems
			* Can recast problems of bipartite matching to apply the marriage theorem
			* Theorem: every regular graph of positive even degree has a 2-factor. (Petersen 1891)

			Matching in general graphs:
			* Tutte's condition: split graph into its odd components, each of which can be "shrunk" down to a single vertex. Then each odd component will send an edge out to another subgraph.
			* This is a necessary condition for the existence of a 1-factor, but it is also sufficient.
			* Theorem: a grpah G has a 1-factor if and only if number of odd components of G - S is less than the size of S, for all <math>S \subseteq V(G)</math> (Tutte 1947)
			* Corollary: every bridgeless cubic graph has a 1-factor. (Recall cubic graphs are 3-connected graphs, i.e., each vertex on the graph has 3 edges.)
			* Gallai-Edmonds matching theorem

			Path covers:
			* Revisiting Konig's duality theorem for bipartite graphs
			* The theorem gives the number of disjoint directed paths needed to cover the vertices of G
			* But how many paths in a given directed graph suffice to cover its entire vertex set?
			* Theorem: Every directed graph G has a path cover by at most alpha(G) paths, where alpha(G) is the maximum cardinality of an independent set of vertices in G (Gallai and Milgram 1960)
			* Corollary: in every finite partially ordered set the minimum number of chains covering P is equal to the maximum cardinality of an antichain in P. (Whatever that means.)

			Note:
			* Lovasz and Plummer, Matching Theory, Annals of Discrete Math, 29, North Holland 1986.
			* Hall's marriage theorem, proved in 1935, remains a commonly-applied graph theoretic result. It proves the general case of partition sets of different sizes. The special case where both partition sets have the same size was proved by Frobenius (1917) in a paper on determinants.

	==Flags==		==Flags==

Admin: /* Matching in Bipartite Graphs */

2017-08-28T00:01:19Z

Matching in Bipartite Graphs

← Older revision		Revision as of 00:01, 28 August 2017
Line 11:		Line 11:
	===Matching in Bipartite Graphs===		===Matching in Bipartite Graphs===

	Consider two partitions A and B on the graph G consisting of disjoint subsets (V,E).		Consider two partitions A and B on the graph G consisting of disjoint subsets (V,E). We call A and B a '''bipartition'''.

	We wish to find various matchings in G. Begin with arbitrary matchings, which will help to find matchings with maximum number of edges.		We wish to find various matchings in G.

			Begin with arbitrary matchings, which will help to find matchings with maximum number of edges.

	Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a, and that contains alternating edges that are or are not in the matching edge set.		Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a, and that contains alternating edges that are or are not in the matching edge set.

Admin: /* Dietel Chapter 2: Matching on Graphs */

2017-08-18T03:32:46Z

Dietel Chapter 2: Matching on Graphs

← Older revision		Revision as of 03:32, 18 August 2017
Line 5:		Line 5:
	* Matching in general graphs		* Matching in general graphs

			Matching - defined as a set M of independent edges on a graph G

			A matching matches vertices in a set U if every vertex in U is incident with an edge in M. (Recall from [[Graphs/Definitions]] that a vertex is incident with an edge e if v is in e, and two vertices are incident with an edge iff they are the endpoint of the edge. The notation for two vertices x and y being incident is xy.

			===Matching in Bipartite Graphs===

			Consider two partitions A and B on the graph G consisting of disjoint subsets (V,E).

			We wish to find various matchings in G. Begin with arbitrary matchings, which will help to find matchings with maximum number of edges.

			Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a, and that contains alternating edges that are or are not in the matching edge set.

			Then we can use that to turn M into a larger matching - if we take the symmetric difference of M and E(P) - the edges that are included in the alternating path - we essentially invert the labels of whether the edge is or is not in the matching set. If the path ends at an unmatched vertex of B, this will increase the size of the matching set by 1 because there will be 1 more unmatched edges than matched edges, and when we flip the labels, we end up with 1 more matched edge than unmatched edges.

	==Flags==		==Flags==

Admin: /* Flags */

2017-08-18T03:23:19Z

Flags

← Older revision		Revision as of 03:23, 18 August 2017
Line 10:		Line 10:
	==Flags==		==Flags==

	{{~~GraphFlag~~}}		{{GraphsFlag}}

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

Admin: Created page with "==Dietel Chapter 2: Matching on Graphs== Outline: * Matching in bipartite graphs * Matching in general graphs ==Flags== {{GraphFlag}} {{AlgorithmsFlag}} Category:Gr..."

2017-08-18T03:21:36Z

Created page with "==Dietel Chapter 2: Matching on Graphs== Outline: * Matching in bipartite graphs * Matching in general graphs ==Flags== {{GraphFlag}} {{AlgorithmsFlag}} Category:Gr..."

New page

==Dietel Chapter 2: Matching on Graphs==

Outline:
* Matching in bipartite graphs
* Matching in general graphs

==Flags==

{{GraphFlag}}

{{AlgorithmsFlag}}

[[Category:Graphs]]
[[Category:Algorithms]]
[[Category:Diestel]]