Bài giảng Một Số Tính Chất Của Đồ Thị Hai Phần

5.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN	Giả sử G = (V1, V2, F) là đồ thị hai phần n đỉnh. 	Ký hiệu: k là số phần tử của tập đỉnh tựa bé nhất.Định lý 5.2: 1) Số ổn định trong của đồ thị hai phần G là bằng n-k. 2) Số phần tử của cặp ghép lớn nhất của G là bằng k.15.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý Từ tính chất: C là tập đỉnh tựa  V \ C là tập ổn định trong, suy ra:	C là tập đỉnh tựa nhỏ nhất  V \ C là tập ổn định trong lớn nhất.	Số ổn định trong = |V \ C| = |V| - |C| = n-k.25.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: 2) Giả sử W là cặp ghép lớn nhất và C là tập tựa nhỏ nhất.Lập ánh xạ t : W  C như sau: e  W, t(e) là một đỉnh của e thuộc C.t(e) tồn tại vì C là tập đỉnh tựa.Nếu cả hai đỉnh của e đều thuộc C , ta lấy một trong hai đỉnh đó. 35.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: 	Nếu u, v  W và u  v thì t(u)  t(v) vì hai cạnh u và v không có đỉnh chung. Vậy: | W |  | C | = k. Chứng minh điều ngược lại: k  | W |. 	45.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: 	Ký hiệu: B là tập các đỉnh của W trong V1. 	Lập ánh xạ h : B  V2 như sau:	 a  B ,  b  V2 : (a, b)  W ta đặt h(a) = b.	- h(B) chính là tập các đỉnh của W trong V2. 	- Nếu a, c  B và a  c thì h(a)  h(c) vì các cạnh trong W chứa a và c không kề nhau.55.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: Một đường đi trong đồ thị G được gọi là đường đannếu nó có dạng ,với w1, w2, ... , wq  W ; u1, u2, ... , uq  W.Ký hiệu: B1 = { a  B  đường đan đi từ a đếnmột đỉnh nào đó nằm ngoài B }. Đặt B2 = B \ B1 và C = B2  h(B1).Ta chứng minh rằng, C là tập đỉnh tựa của đồ thị G. 65.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: Phản chứng: Giả sử rằng tập C không phải tập đỉnh tựa của đồ thị hai phần G. Khi đó, có cạnh (a, b) không tựa vào tập C: 	a  B2 và b  h(B1). Vì W là cặp ghép lớn nhất, nên (a, b) phải kề với cạnh nào đó trong W: a  B hoặc b  h(B). 75.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: Trường hợp: a  B. Suy ra: a  B1. Tồn tại đường đan (X) = dẫnđỉnh a tới một đỉnh d nào đó nằm ngoài tập B.- Nếu b  h(B) thì (a, b)  W.Ta loại w1 , w2 , ... , wq ra khỏi W rồi thay các cạnh(a, b) , u1 , u2 , ... , uq vào W. Khi đó, W vẫn là một cặp ghép và số cạnh tăngthêm 1, trái với giả thiết W là cặp ghép lớn nhất.85.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: 	- Nếu b  h(B) thì b  h(B2). 	Ký hiệu đỉnh d’ = h-1(b)  B2. 	Đường đan: dẫn đỉnh d’ trong B2 tới đỉnh d nằm ngoài B. 	Vậy thì: d’  B1. Suy ra mâu thuẫn.95.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: 	2) Trường hợp a  B: Suy ra b  h(B2) vì (a, b) không tựa vào tập C. Ký hiệu: d’ = h-1(b)  B2. Đường đan dẫn đỉnh d’ tớiđỉnh a ở ngoài tập B. Vậy thì d  B1. Mâu thuẫn.Vậy C là một tập tựa của đồ thị và |C| = |W|.Vì k là số phần tử của tập đỉnh tựa nhỏ nhất nênk  |C| = |W|. Định lý được chứng minh. 105.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp) Ký hiệu d0 = max { |B| - |F(B)|  B  V1 }. 	Vì   V1 và || - |F()| = 0 - 0 = 0 nên d0 luôn là một số không âm. Định lý 5.3: Số phần tử của tập tựa bé nhất của đồ thị hai phần G = (V1, V2, F) là |V1| - d0 .115.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp) Chứng minh định lý: Giả sử C là một tập tựa bất kỳ. Tách C = C1  C2 , trong đó C1  V1 và C2  V2.Ký hiệu: C1’ = V1 \ C1. Khi đó, F(C1’)  C2 , vì nếu ngược lại thì:a  C1’ mà đỉnh kề của nó y  Ccạnh (a, y) sẽ không tựa vào tập C  mâu thuẫn. 125.3. MỘT SỐ TÍNH CHẤT CỦA ĐỒ THỊ HAI PHẦN (tiếp)Chứng minh định lý: C1  F(C1’) là một tập tựa và C1  F(C1’)  C. Do đó, với mỗi tập tựa có thể thay bằng một tập tựadạng C1  F(C1’) với số phần tử không lớn hơn.Vậy, số phần tử của tập tựa bé nhất là:	min { | C1  F(C1’) |  C1  V1 } 	= min { | C1 | + | F(C1’) |  C1  V1} 	= | V1| - max { | C1’| - | F(C1’) |  C1’  V1} = | V1 | - d0.  13SỐ HỤT CỦA ĐỒ THỊ HAI PHẦNTừ Định lý 5.3, ta gọi d0 là số hụt của đồ thị.Hệ quả 5.4:	a) Số ổn định trong của đồ thị hai phần G là 	| V2| + d0 b) Số phần tử của cặp ghép lớn nhất của G là 	| V1| - d0. 14BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)Giả thiết: - Mỗi nhân viên đảm nhận được k nhiệm vụ- Mỗi nhiệm vụ có đúng k nhân viên có thể đảm nhận.Kết luận: Luôn có thể phân công công việc thích hợp.15BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)Ký hiệu: V1 - tập nhân viên, |V1| = n	 V2 - tập nhiệm vụ, |V2| = m.Xây dựng độ thị hai phần G = (V1,V2, F) :	xi  F(yj)  xi đảm nhận được nhiệm vụ yj. Từ giả thiết, mỗi đỉnh kề với k cạnh, do đó số cạnh kềvới F(B)  số cạnh kề với B.- Số cạnh kề với B là k.| B | - Số cạnh kề với F(B) là k.| F(B) |.16BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)Số cạnh kề với F(B)  số cạnh kề với B nên	|B|  |F(B)| , suy ra d0 = 0. Theo Hệ quả 5.4, lực lượng của cặp ghép lớn nhất là |V1| - d0 = |V1| . Do đó, có thể phân công n nhân viên đảm nhân n nhiệm vụ.Thay đổi vai trò giữa V1 và V2 , suy ra lực lượng của cặp ghép lớn nhất bằng |V2|, nên |V1| = |V2|. Bài toán luôn giải được. 175.4. ĐỒ THỊ RIÊNG HAI PHẦNTừ một đồ thị đã cho có trích được một đồ thị riêng hai phần hay không ?Định lý 5.5:	Đồ thị vô hướng G = (V, E) với:- |V| = 2n ,- bậc của mỗi đỉnh không nhỏ hơn n ;	luôn có đồ thị riêng hai phần G” = (V1, V2, E”) trong đó: | V1 | = |V2 | = | E”| = n vàE’’ là cặp ghép lớn nhất của G.185.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)Chứng minh định lý:Xây dựng đồ thị riêng hai phần G” = (V1, V2, E”):Lấy dần vào E’’ các cạnh của G: các đỉnh trên cáccạnh này khác nhau đôi một cho đến khi bất kỳ cạnhnào còn lại cũng kề với một cạnh trong E”.Giả sử | E” | = k. 1) Nếu k = n, định lý được chứng minh.195.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)Chứng minh định lý:	2) Nếu k < n thì |V |  2k +2.	Giả sử E” = {(a1, a2), (a3, a4), ..., (a2k-1, a2k)}. 	Khi đó có ít nhất hai đỉnh a2k+1, a2k+2 không nằm trên cạnh nào thuộc E”.	Theo cách chọn tập E’’ thì a2k+1, a2k+2 chỉ kề với các đỉnh trên E” và kề với ít nhất n đỉnh trong E”.205.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)Trong E” đánh dấu các đỉnh kề với a2k+1 và a2k+2: ít nhất có một đỉnh ai được đánh dấu 2 lần.Giả sử aj là đỉnh kề với ai trong E”, loại (ai, aj) ra khỏi E” , thêm vào (ai, a2k+1) và (aj, a 2k+2).Số cạnh trong E” tăng thêm 1.Tiếp tục như vậy, sau một số bước, | E”| = n, và ta xâydựng được đồ thị riêng hai phần G”.  	21VÍ DỤ 5.7Đồ thị và đồ thị riêng hai phần:12345612345622