1 of 40

Graph Theory��Chapter 6� Matchings and � Factorizations

大葉大學(Da-Yeh Univ.)�資訊工程系(Dept. CSIE)�黃鈴玲(Lingling Huang)

2 of 40

Outline

6.1 An Introduction to Matchings

6.2 Maximum Matchings in � Bipartite Graphs

6.3 Maximum Matchings in General � Graphs

6.4 Factorizations

Ch6-2

3 of 40

6.1 An Introduction to � Matchings

Ch6-3

Focus: � Find 1-regular subgraphs of maximum � size in a graph.

Marriage Problem:� Given a collection of men and women, where�each woman knows some of the men, under what�conditions can every woman marry a man she �knows? A variation of this problem is to find the�maximum number of woman, each of whom can�marry a man she knows.

4 of 40

Ch6-4

Model the problem:� bipartite graph G = (S₁∪S₂, E), � S₁={men}, S₂={women}, � ab∈E if a knows b.�(1) Under what conditions does G have a 1-regular� subgraph that contains all the vertices that� represent the women?�(2) What is the maximum size of a 1-regular� subgraph of G?

5 of 40

Ch6-5

Optimal Assignment Problem:� Given several job openings and applicants for �one or more of these positions. The hiring company�wishes to receive the maximum possible benefit as �a result of its hiring. For example, the experience�of the applicants may be an important factor to �consider during the hiring process. The company �may benefit by employing fewer people with more�experience than a larger number with less�experience.

6 of 40

Ch6-6

Model the problem:� weighted bipartite graph G = (S₁∪S₂, E), � S₁={applicants}, S₂={jobs}, � a∈ S₁, b∈ S_2, ab∈E if a has applied b,� w(a,b) is the benefit that the company will� gain by hiring applicant a.��⇒ To find a 1-regular subgraph H of G where� the sum of the weights of the edges in H is� a maximum.

7 of 40

Definition:

A matching in a graph G is a 1-regular subgraph of G, that is, a subgraph induced by a collection of pairwise nonadjacent edges. �We also refer to a matching as a collection of edges that induces a matching.

A matching of maximum cardinality in a graph G is called a maximum matching of G.

Ch6-7

8 of 40

Ch6-8

c

M = { ab, cd, ef }�is a maximum matching

M’ = { bc, de } is maximal,

not maximum.

a

b

d

e

f

Maximum (所有matching中最多edge的)� ≥ Maximal (此matching不可再加邊成為� 更大的matching)

9 of 40

Definition:�If G is a graph of order p that has a matching of cardinality p/2, then such a matching is called a perfect matching.

Ch6-9

Note:�If a graph of order p has a perfect matching, then p must be even.

反之未必成立�e.g. K_1,3 has even order but no perfect matching.

10 of 40

Definition:

A matching in a weighted graph G is a set of edges of G, no two of which are adjacent. A maximum weight matching in a weighted graph is a matching in which the sum of the weights of its edges is maximum.

Ch6-10

Note:�A maximum weight matching need not be a maximum matching.

11 of 40

Ch6-11

M = { v₁v₂, v₃v₅ }is a maximum weight matching (weight sum=4)

M’ = {v₁v₂, v₃v₄, v₅v₆ }is a maximum matching

v₁

v₂

v₃

v₅

v₆

v₄

2

1

3

1

12 of 40

Definition:

M : a matching of a graph G, �e: an edge, v: a vertex

(1). e∈M : e is called a matched edge

(2). e ∉M : e is an unmatched edge

(3). v is a matched vertex if v is incident with a� matched edge; v is a single vertex otherwise.

(4). An alternating path of G is a path whose � edges are alternately matched and unmatched.

(5). An augmenting path of G is an alternating � path that begins and ends with single vertices.

Ch6-12

13 of 40

An augmenting path P of G :

Ch6-13

P中的邊將∈M的與∉M的性質交換，

M中的邊數會加一。

∉M

∈M

∉M

∈M

∉M

Single�vertex

14 of 40

Thm 6.1 :

M₁, M₂ : matchings of G

E=(M₁−M₂)∪(M₂−M₁), H is the spanning

subgraph of G with E(H)=E, then every

component of H is one of the following � type:

(a) K₁

(b) C₂_n for some n

(c) a path (alternating path)

Ch6-14

15 of 40

Ch6-15

G :

H : ( V(H)=V(G) )

H裡沒有degree ≥ 3的點

M₁�M₂

Example:

16 of 40

Thm 6.2

A matching M in a graph G is a maximum

matching if and only if there is no augmenting path, with respect to M, in G.

Ch6-16

Pf:

⇒) trivial

⇐) by Thm 6.1

17 of 40

Homework

Exercise 6.1:� 1

Ch6-17

18 of 40

Outline

6.1 An Introduction to Matchings

6.2 Maximum Matchings in � Bipartite Graphs

6.3 Maximum Matchings in General � Graphs

6.4 Factorizations

Ch6-18

19 of 40

6.2 Maximum Matchings in Bipartite Graphs

Algorithm 6.1 (A maximum matching algorithm for bipartite graphs)�[To determine a maximum matching in a bipartite graph G with V(G)={v₁, v₂, …, v_p} and an initial matching M₁.]

1. i ←1, M ← M₁

2. If i < p, then continue; �otherwise, stop, M is a maximum matching now.

3. If v_i is matched, then i ← i +1 and return to Step 2;�otherwise, v ← v_i and Q is initialized to contain v only.

4. 4.1 For j = 1, 2, …, p and j ≠ i, let Tree(v_j)=F. � (表示v_j不在alternating tree中) � Also, Tree(v_i)=T.

Ch6-19

20 of 40

4.2 If Q=∅ , then i ← i +1 and return to step 2; � otherwise, delete a vertex x from Q and continue.

4.3 � 4.3.1 Suppose that N(x)={y₁, y₂, …, y_k}. Let j ← 1.� 4.3.2 If j ≤ k, then y ← y_j; otherwise, return to Step 4.2.

4.3.3 If Tree(y)=T, then j ← j + 1 and return to� Step 4.3.2; otherwise, continue.� 4.3.4 If y is incident with a matched edge yz, then � Tree(y)←T, Tree(z)←T, Parent(y)←x, Parent(z)←y � and add z to Q, j ← j + 1, and return to Step 4.3.2. � Otherwise, y is a single vertex (找到了!) � and we continue.� 4.3.5 Use array Parent to determine the alternating � v-x path P’ in the tree. Let P ← P’U{xy} be the � augmenting path.

5. Augment M along P to obtain a new matching M’. �Let M ← M’, i ← i +1 , and return to step 2.

Ch6-20

21 of 40

Example (Fig 6.6)

Ch6-21

x₁

x₂

x₃

x₄

x₅

x₆

y₁

y₂

y₃

y₄

y₅

y₆

Initial matching M₁

i=1, x₁ is matched.

i=2, v=x₂

Q :

x₂

y₂

x₃

x₅

y₆

y₁

x₁

y₄

x₄

y₃

x₆

y₅

x₃

x₅

x₄

x₁

x₆

Augmenting path

22 of 40

Example (Fig 6.6)

Ch6-22

x₁

x₂

x₃

x₄

x₅

x₆

y₁

y₂

y₃

y₄

y₅

y₆

New matching M

i=3, x₃ is matched.

i=4, x₄ is matched.

…

i=12, y₆ is matched.

M = { x₂y₆, x₅y₄, x₁y₁, x₄y₃, x₃y₂, x₆y₅ } is maximum.

23 of 40

Homework

Exercise 6.2:� 3

Ch6-23

24 of 40

Outline

6.1 An Introduction to Matchings

6.2 Maximum Matchings in � Bipartite Graphs

6.3 Maximum Matchings in General � Graphs

6.4 Factorizations

Ch6-24

25 of 40

6.3 Maximum Matchings in General Graphs

For general graphs, the task of finding augmenting paths is complicated by the presence of odd cycles that have a maximum number of matched edges.

Ch6-25

⇒ 將Alg 6.1 修改為tree中允許點重複，�但每點不可同時是自己的祖先

26 of 40

Example (Fig 6.9)

Ch6-26

w

v

c

a

b

u

z

y

d

v

w

Initial matching M₁

x

a

c

d

c

b

u

y

x

w

v

w

x

y

z

Augmenting path

27 of 40

Example (Fig 6.10)

Ch6-27

2

4

5

6

11

8

3

7

9

Initial matching M₁

10

4

2

5

3

1

6

8

7

9

7

10

Augmenting path

1

8

6

28 of 40

Homework

Exercise 6.3:� 3 (先任給一個matching)

Ch6-28

29 of 40

Outline

6.1 An Introduction to Matchings

6.2 Maximum Matchings in � Bipartite Graphs

6.3 Maximum Matchings in General � Graphs

6.4 Factorizations

Ch6-29

30 of 40

6.4 Factorizations

Definition. A factor of a graph G is a spanning subgraph of G. (It is possible that a factor has no edges.) Suppose that G₁, G₂, …, G_n are pairwise edge-disjoint spanning subgraphs of G such that Uⁿ_i₌₁E(G_i) = E(G). Then G is factorable or factored into the subgraphs or factors G₁, G₂, …, G_n, and we write G = G₁ ⊕ G₂ ⊕… ⊕ G_n. This expression is also called a factorization of G into the factors G₁, G₂, …, G_n.

Ch6-30

31 of 40

Definition. An r-regular factor of a graph G is an r-factor of G.

Ch6-31

Thus, a graph has a 1-factor if and only if it contains a perfect matching.

Definition. If there is a factorization of a graph G into r-factors, then G is said to be r-factorable.

In this case, G is k-regular for some k that is a multiple of r.

32 of 40

Ch6-32

H₁

H

H₂

H₃

A 1-factorization of K_3,3

33 of 40

Ch6-33

H

A 2-factorization of K₅

H₁

H₂

34 of 40

Ch6-34

A 1-factorable cubic (3-regular)graph

G

H₂

H₃

H₁

35 of 40

Theorem 6.10 Every regular bipartite multigraph of degree r ≥ 1 is 1-factorable.

Ch6-35

Proof. (by induction on r)

Theorem 6.11 For every positive integer n, the graph K₂_n is 1-factorable.

Proof. (參考下頁K₆的分解方法)

36 of 40

Ch6-36

A 1-factorization of K₆

H₁

H₂

H₃

H₄

H₅

中心點 v 每次先連一點 x，再將剩下的點配對，�產生的邊需垂直於 vx

37 of 40

Ch6-37

Definition A spanning cycle in a graph G is called a Hamiltonian cycle.

Proof. (參考下頁K₇的分解方法)

Theorem 6.12 For every positive integer n, the graph K₂_n+₁ is can be factored into n�Hamiltonian cycles.

38 of 40

Ch6-38

3 Hamiltonian cycles of K₇

F₁

v₀

v₁

v₂

v₃

v₄

v₅

v₆

F₂

v₀

v₁

v₂

v₃

v₄

v₅

v₆

F₃

v₀

v₁

v₂

v₃

v₄

v₅

v₆

39 of 40

Ch6-39

Petersen Graph �(在圖論的一些性質中常扮演反例的角色)

Petersen graph is not 1-factorable.�(證明略過)

40 of 40

Homework

Exercise 6.4:� 3, 4 (參考Fig 6.14)

Ch6-40

C₄×K₂:

⇒

Ex 3. Show that C_n×K₂ is 1-factoriable for every n ≥ 4.