Bài giảng Chương 2: Hàm Grundy Trên Đồ Thị

CHƯƠNG 2HÀM GRUNDY TRÊN ĐỒ THỊ 1NỘI DUNG Hàm Grundy Sự tồn tại của hàm Grundy Tổng của các đồ thị Hàm Grundy của đồ thị tổng22.1. HÀM GRUNDY Định nghĩa Các tính chất Ví dụ Điều kiện cho sự tồn tại của hàm Grundy 3 2.1. HÀM GRUNDY (tiếp) Hàm Grundy là một hàm toán học xây dựng trên đồ thị, do P. M. Grundy đề xuất để nghiên cứu một số tính chất lý thú của đồ thị.	Ký hiệu N = {0, 1, 2, . . .} là tập các số nguyên không âm.4ĐỊNH NGHĨA HÀM GRUNDYGiả sử G = (V, F) là một đồ thị. Hàm g : V  N được gọi là hàm Grundy của đồ thị G nếu: 	  x  V : g(x) = min {N \ g(F(x))}.5CÁC TÍNH CHẤT1) 	 x, y  V, nếu y  F(x) thì g(x)  g(y). u  N , u u. (*)262.4. HÀM GRUNDY CỦA ĐỒ THỊ TỔNG (tiếp)Xét biểu diễn nhị phân của các số trên:	u = .... uk=0 ...	v = .... vk=1...	w = .... wk .....	t = 0...01k .....	Giả sử k là chỉ số của bit đầu tiên bằng 1 trong biểu diễn nhị phân của số t.	Nếu uk = 1 thì (uk + tk) mod 2 = 0. Suy ra: t  u < u, trái với mệnh đề (*). Vậy thì uk = 0.272.4. HÀM GRUNDY CỦA ĐỒ THỊ TỔNG (tiếp)	Do bit thứ k của t bằng 1 nên hoặc vk hoặc wk phải bằng 1. 	Giả sử vk = 1. 	Đặt s = t  v. Ta có s < v = g1(a). 	Vì g1 là hàm Grundy của đồ thị G1 nên tồn tại x  F1(a) sao cho s = g1(x). 282.4. HÀM GRUNDY CỦA ĐỒ THỊ TỔNG (tiếp)	Theo định nghĩa của đồ thị tổng thì:	(x,b)  F((a,b)) và	g((x,b)) = g1(x)  g2(b) = s  w 	 = t  v  w = u.	- Khi wk = 1, chứng minh hoàn toàn tương tự.	Phần 2 đã chứng minh xong và kết thúc chứng minh định lý. 29