Introduction to Graph Theory Matchings
undefined
Graph Theory Matchings
Matthew dreher
History
•
9th century AD. In
Rudraṭa's
Kavyalankara with the knights tour
•
One of the first writing on graph theory was by Euler in 1736 on the Seven
Bridges of Königsberg problem
•
First graph theory book was made by a Hungarian mathematician Dénes
Kőnig in 1936 (
theory of finite and infinite graphs
)
Distinct representatives
Distinct representatives
Matchings
Hall’s Marriage Theorem
•
Hall’s Theorem: Let G be a bipartite graph with partite sets U and W such
that r = |U|≤|W|. Then G contains a matching of size r if and only if |N(X)|≥|X|
for every nonempty subset X of U
Maximum Matching
•
In any graph, let M be a subgraph G is a maximum matching if M has the
maximum size among all matchings in G
•
M is a perfect matching if vertex of G is incident with some edge of M, it a
necessary condition that G has a even number of vertices
Finding a maximum matching
Tutte's theorem
•
A graph, G = (V, E), has a perfect matching if and only if for every subset U of
V, the subgraph induced by V − U has at most |U| connected components
with an odd number of vertices
Stable marriage problem
•
Def: A perfect matching is a stable matching if it yields no unstable
unmatched pair, that is, (x, a),(y, b) are matched, but x prefers b to a, and b
prefers x to y.
•
Gale-Shapley Proposal Algorithm (1962):
•
Each man and each woman have a preference list
•
At each round, man proposes to its top choice who has not reject him yet.
•
Each proposed woman choose to accept or reject the proposing man according to her
preference list.
example
•
Let x=a,b,c and y=d,e,f
•
preference list A(d,e,f),B(d,f,e),c(f,e,d),d(a,b,c),e(c,a,b),f(b,c,a)
a
b
c
d
e
f
a
d
b
e
c
f
a
b
c
d
e
f
Refences
•
Benjamin, Arthur, et al.
The Fascinating World of Graph Theory
. Princeton
University Press, 2015.
JSTOR
, www.jstor.org/stable/j.ctt9qh0pv. Accessed 2
Nov. 2020.
Graph Theory Matchings have a rich history dating back to the 9th century AD. Distinct Representatives and Hall's Theorem play important roles in determining matchings in graphs. Understanding concepts like bipartite graphs, maximum matchings, and Hall's Marriage Theorem is essential in graph theory analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graph Theory Matchings Matthew dreher
History 9th century AD. In Rudra a'sKavyalankarawith the knights tour One of the first writing on graph theory was by Euler in 1736 on the Seven Bridges of K nigsberg problem First graph theory book was made by a Hungarian mathematician D nes K nigin 1936 (theory of finite and infinite graphs)
Distinct representatives Suppose that {?1, ?2,, .,?N} is a collection of n>=2 finite nonempty sets The system of sets is said has a Distinct representatives if there exists n distinct elements ?1, ?2,.., ?nsuch that ?? ?? Therefore there is a subgraph that is a one-to-one mapping
Distinct representatives While it s a necessary condition that |?1 ?2 ?n|>=n for a system to be a Distinct representatives it s not a sufficient condition Hall s Theorem: A collection {S1, S2,..., Sn} of n nonempty finite sets has a system of distinct representatives if and only if, for each integer k with 1 k n, the union of any k of these sets contains at least k elements
Matchings Let U = {?1, ?2,..., ?n} and W = ?1 ?2 ?n, |W|>=n Construct a bipartite a graph G between U and where U are the sets ?ind the vertices in W are the elements belonging to the union of the ?i sets has a system of distinct representatives if and only if the graph G has n edges, no two of which are adjacent. A collection of edges
Halls Marriage Theorem Hall s Theorem: Let G be a bipartite graph with partite sets U and W such that r = |U| |W|. Then G contains a matching of size r if and only if |N(X)| |X| for every nonempty subset X of U
Maximum Matching In any graph, let M be a subgraph G is a maximum matching if M has the maximum size among all matchings in G M is a perfect matching if vertex of G is incident with some edge of M, it a necessary condition that G has a even number of vertices
Finding a maximum matching Input: let G be a bipartite made of set x and y and let U be the set of unmatched vertices in X, output a maximum matching Initialization: let S=U and T= empty set Initialization: If S has no unmarked vertex, stop and report T union(X -S) as amaximum matching Otherwise, select an unmarked x S. For each y N(x) with xy M, if y is unmatched, terminate and report an M-augmenting path from U to y; otherwise, y is matched to some w X by M, then include y in T and include w in S. After exploring all such edges, mark x and iterate
Tutte's theorem A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V U has at most |U| connected components with an odd number of vertices
Stable marriage problem Def: A perfect matching is a stable matching if it yields no unstable unmatched pair, that is, (x, a),(y, b) are matched, but x prefers b to a, and b prefers x to y. Gale-Shapley Proposal Algorithm (1962): Each man and each woman have a preference list At each round, man proposes to its top choice who has not reject him yet. Each proposed woman choose to accept or reject the proposing man according to her preference list.
example Let x=a,b,cand y=d,e,f preference list A(d,e,f),B(d,f,e),c(f,e,d),d(a,b,c),e(c,a,b),f(b,c,a) d a d a a d e b e b b e c f c f c f
Refences Benjamin, Arthur, et al. The Fascinating World of Graph Theory. Princeton University Press, 2015. JSTOR, www.jstor.org/stable/j.ctt9qh0pv. Accessed 2 Nov. 2020.
