Bài giảng Toán - Các Tập Hợp Đặc Biệt Trên Đồ Thị

CHƯƠNG 3CÁC TẬP HỢP ĐẶC BIỆT TRÊN ĐỒ THỊ1NỘI DUNG Tập ổn định trong Tập ổn định ngoài Nhân của đồ thị23.1. TẬP ỔN ĐỊNH TRONGĐịnh nghĩa 3.1Giả sử G = (V, F) là một đồ thị.Tập B  V được gọi là tập ổn định trong của đồ thị G nếu:  x  B : B  F(x) = .3VÍ DỤ 3.1 Bài toán tám quân hậu 	Hãy đặt 8 quân hậu vào các ô của một bàn cờ vua sao cho chúng không ăn được lẫn nhau. 4VÍ DỤ 3.1 (tiếp) Xây dựng đồ thị vô hướng biểu diễn bàn cờ vua: 	- 64 ô của bàn cờ là 64 đỉnh, 	- Hai đỉnh x và y có cạnh nối với nhau nếu đặt hai quân hậu vào hai ô đó, chúng có thể ăn lẫn nhau. Các ô cần tìm để đặt các quân hậu chính là một tập ổn định trong gồm 8 đỉnh.5VÍ DỤ 3.1 (tiếp) Bài toán trên có 92 nghiệm suy ra từ 12 tập ổn định trong khác nhau là:{A7,B2,C6,D3,E1,F4,G8,H5} {A6,B1,C5,D2,E8,F3,G7,H4}{A5,B8,C4,D1,E7,F2,G6,H3} {A3,B5,C8,D4,E1,F7,G2,H6}{A4,B6,C1,D5,E2,F8,G3,H7} {A5,B7,C2,D6,E3,F1,G4,H8}{A1,B6,C8,D3,E7,F4,G2,H5} {A5,B7,C2,D6,E3,F1,G8,H4}{A4,B8,C1,D5,E7,F2,G6,H3} {A5,B1,C4,D6,E8,F2,G7,H3}{A4,B2,C7,D5,E1,F8,G6,H3} {A3,B5,C2,D8,E1,F7,G4, H6}6VÍ DỤ 3.2Bài toán về dung lượng thông tin (C.E. Shannon)	Giả sử một máy phát có thể truyền đi 5 tín hiệu: a, b, c, d, e. ở máy thu mỗi tín hiệu có thể cho hai cách hiểu khác nhau như sau: 	 a  p, q ; b  q, r ; c  r, s ; d  s, t ; e  t, p 	Hỏi số các tín hiệu nhiều nhất có thể sử dụng để máy thu không bị nhầm lẫn là bao nhiêu?7VÍ DỤ 3.2 (tiếp)Xây dựng một đồ thị vô hướng gồm 5 đỉnh a, b, c, d, e. Hai đỉnh là kề nhau nếu chúng biểu thị hai tín hiệu có thể bị nhầm lẫn nhau ở máy thu. 	Hình 3.1. Sự nhầm lẫn của các tín hiệu và đồ thị biểu diễnabcdepqrstabedc8VÍ DỤ 3.2 (tiếp) Tập các tín hiệu cần chọn là một trong các tập ổn định trong dưới đây:	{a, c}	{a, d}	{b, d}	{b, e}	{c, e}.9TẬP ỔN ĐỊNH TRONG CỰC ĐẠI Tập con các đỉnh B được gọi là tập ổn định trong cực đại nếu thêm vào bất kỳ đỉnh nào cũng làm mất tính ổn định trong của nó. Tập B được gọi là tập ổn định trong lớn nhất nếu B là tập ổn định trong có nhiều phần tử nhất. 	Lực lượng của tập ổn định trong lớn nhất được gọi là số ổn định trong của đồ thị đó. 	Ta thường ký hiệu số ổn định trong của đồ thị là u.10TẬP ỔN ĐỊNH TRONG CỰC ĐẠI (tiếp)	Chú ý: Tập ổn định trong lớn nhất là tập ổn định trong cực đại, nhưng ngược lại thì không đúng. 11VÍ DỤ 3.3Các tập {a, b} và {c, d, e} đều là ổn định trong cực đạiHình 3.2. Đồ thị có tập ổn định trong cực đại nhưng không lớn nhấtabcde12SỐ ỔN ĐỊNH TRONGĐịnh lý 3.1 Đồ thị G có n đỉnh, bậc lớn nhất của các đỉnh là r. Khi đó, số ổn định trong u của đồ thị thỏa mãn: 13SỐ ỔN ĐỊNH TRONG (tiếp)Chứng minh định lý 	Giả sử B là tập ổn định trong lớn nhất với u phần tử. Với mỗi đỉnh y  B có ít nhất một đỉnh của B kề với y. Vì nếu ngược lại thì có thể bổ sung y vào B. 	Suy ra, số cạnh đi ra khỏi B (không kể hướng)  V \ B  = n - u. 	Mặt khác, số cạnh đó  r.u. Vậy r.u  n-u. 	Từ đó suy ra:  14TÌM TẬP ỔN ĐỊNH TRONG LỚN NHẤTThuật toán 3.1 	1. Chọn một đỉnh nào đó của đồ thị.	2. Bổ sung dần các đỉnh để được một tập ổn định trong cực đại. 	3. Nếu ta tìm được một tập ổn định trong có u đỉnh mà mọi tập con u+1 đỉnh đều không là tập ổn định trong, thì kết luận tập tìm được là tập ổn định trong lớn nhất và u chính là số ổn định trong của đồ thị này. 153.2. TẬP ỔN ĐỊNH NGOÀI Định nghĩa 3.2: Giả sử G = (V, F) là một đồ thị. Tập C  V được gọi là tập ổn định ngoài của đồ thị G nếu:  x  C : C  F(x)  .	Hay nói một cách khác:  x  C ,  y  C : y  F(x).16VÍ DỤ 3.4 Hãy đặt 5 quân hậu lên các ô của một bàn cờ vua sao cho chúng kiểm soát được toàn bộ bàn cờ. 	Biểu diễn đồ thị cho bàn cờ vua như ở Ví dụ 3.2. 	Khi đó, các ô cần tìm chính là một tập ổn định ngoài gồm 5 đỉnh. 	Một tập nghiệm của bài toán là: {C6 , D3 , E5 , F7 , G4}.173.2. TẬP ỔN ĐỊNH NGOÀI (tiếp) Tập C được gọi là tập ổn định ngoài cực tiểu nếu bớt đi bất kỳ đỉnh nào của nó cũng làm mất tính ổn định ngoài. Tập C được gọi là tập ổn định ngoài bé nhất nếu C là tập ổn định ngoài có ít phần tử nhất. 	Lực lượng của tập ổn định ngoài bé nhất được gọi là số ổn định ngoài của đồ thị.18TÌM TẬP ỔN ĐỊNH NGOÀI Thuật toán 3.2 Giả sử đồ thị G = (V, F) với V = {a1 , a2 , ... , an}.1) Xây dựng ánh xạ T : V  2V như sau: 	 a  V , T(a) = {a}  F-1(a) 2) Tìm tập con C  V có ít phần tử nhất mà T(C) = V.	Khi đó, C là một tập ổn định ngoài bé nhất của đồ thị G.19TÌM TẬP ỔN ĐỊNH NGOÀI (tiếp)Chú ý: Bước 2 của thuật toán 3.2 có thể thực hiện nhanh nhờ các nhận xét sau đây: 	- Đỉnh cô lập luôn luôn thuộc tập ổn định ngoài bé nhất của đồ thị G, nghĩa là đỉnh cô lập phải được giữ lại.20TÌM TẬP ỔN ĐỊNH NGOÀI (tiếp)Nếu tập con D các đỉnh chứa tập con C mà: 	T(D)  T(C) thì bỏ không xét tập D này. 	Thực hiện việc loại bỏ cho đến khi chỉ còn các đỉnh không thể loại bỏ được nữa. 	Tập đỉnh này chính là một tập ổn định ngoài bé nhất của đồ thị G.21VÍ DỤ 3.5Xét đồ thị có hướng sau:	G = 	T(a) = {a};	T(d) = {b,c,d};	T(b) = {a,b,c}; T(e) = {e}; T(c) = {a,c}	e là đỉnh cô lập phải giữ lại.acbdeHình 3.3. Đồ thị và tập ổn định ngoài22VÍ DỤ 3.5 (tiếp)Loại bỏ a, c ta lập được {b,d,e} là một tập ổn định 	ngoài bé nhất của G. - Loại bỏ a, b ta được {c,d,e} là một tập ổn định ngoài bé nhất khác của G. 23