Bài giảng Lý thuyết đồ thị: Chương 2 - PGS.TS. Hoàng Chí Thành

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

13
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 2 Hàm grundy trên đồ thị, cung cấp cho người đọc những kiến thức như: 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ổng. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 2 - PGS.TS. Hoàng Chí Thành

CHƯƠNG 2 HÀM GRUNDY TRÊN ĐỒ THỊ 1/29
NỘ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ổng 2/29
2.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/29
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/29
ĐỊNH NGHĨA HÀM GRUNDY Giả 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))}. 5/29
CÁC TÍNH CHẤT 1)  x, y  V, nếu y  F(x) thì g(x)  g(y). 2)  u  N , u < g(x) : u  g(F(x)) , nghĩa là:  y  F(x) : g(y) = u. 6/29
NHẬN XÉT 1. Đồ thị có đỉnh nút thì không có hàm Grundy. 2. Nếu F(x) =  thì g(x) = 0. 3. Tập hợp {x x  V, g(x) = 0} luôn khác rỗng. 4.  x  V : g(x)  F(x) - hàm Grundy nhận giá trị không lớn. 7/29
VÍ DỤ 2.1 Hàm Grundy có thể không duy nhất 1 0 0 1 0 1 2 1 0 0 1 0 Hình 2.1. Đồ thị có hai hàm Grundy 8/29
VÍ DỤ 2.2 Hàm Grundy có thể không tồn tại Hình 2.2. Đồ thị không có hàm Graundy Vậy với điều kiện nào thì một đồ thị có hàm Grundy? 9/29
2.2. ĐIỀU KIỆN TỒN TẠI Định lý 2.1: Đồ thị G không có chu trình thì có duy nhất một hàm Grundy. Chứng minh: Không mất tính tổng quát, giả thiết rằng đồ thị G liên thông. Xây dựng hai dãy tập con các đỉnh: V0, V1, . . . và P0, P1, . . . lần lượt như sau: V0 = V P0 = { x | F(x) = Ø} 10/29
2.2. ĐIỀU KIỆN TỒN TẠI (tiếp) Tập P0 không rỗng. Vì nếu P0 rỗng có nghĩa là mọi đỉnh trong V luôn có đỉnh kề. Khi đó xuất phát từ một đỉnh có thể tạo một đường đi dài tuỳ ý. Điều này là vô lý vì trong G không có chu trình. V1 = V0 \ P0 P1 = {x | x V1  F(x)  V \ V1} V2 = V1 \ P1 …….……. Pi = {x | x  Vi  F(x)  V \ Vi} Vi+1 = Vi \ Pi 11/29
2.2. ĐIỀU KIỆN TỒN TẠI (tiếp)  Nếu Pk rỗng thì Vk cũng rỗng, nghĩa là ta đã vét hết các đỉnh của đồ thị. Thật vậy, giả sử ngược lại: Pk =  nhưng Vk ≠ . Khi đó, với mỗi x  Vk sẽ có y  F(x) để y  V \ Vk, nghĩa là y  Vk . Vậy với mọi đỉnh trong Vk luôn có đỉnh kề cũng thuộc Vk . 12/29
2.2. ĐIỀU KIỆN TỒN TẠI (tiếp)  Khi đó xuất phát từ một đỉnh trong Vk có thể tạo ra một đường đi dài tuỳ ý. Điều này là vô lý vì đồ thị G không có chu trình. P0 P1 ... Pk V0 V1 V2 Vk Hình 2.3. Cách xây dựng dãy tập con P0, P1, . . ., Pk 13/29
2.2. ĐIỀU KIỆN TỒN TẠI (tiếp) Bây giờ, ta xây dựng hàm g : V  N như sau: - Với mọi x  P0 ta đặt g(x) = 0. - Với mỗi x  P1 nghĩa là x  P0 và F(x)  P0 , do hàm g đã được xác định trên P0 , nên hàm g tại x được xác định một cách duy nhất: g(x) = min {N \ g(F(x))}. 14/29
2.2. ĐIỀU KIỆN TỒN TẠI (tiếp) Tiếp tục cách làm trên ta sẽ lần lượt xác định được giá trị hàm g tại mỗi đỉnh của đồ thị một cách duy nhất. Định lý được chứng minh và ta có thuật toán tìm hàm Grundy cho đồ thị phi chu trình. 15/29
VÍ DỤ 2.3 Xét đồ thị có hướng trong hình vẽ và cách xây dựng hàm Grundy trên nó. P1 b 1 2 0 P3 a d P0 0 c P2 Hình 2.4. Đồ thị và các tập con Pi 16/29
2.3. TỔNG CỦA CÁC ĐỒ THỊ Cho hai đồ thị dưới dạng ánh xạ kề: G1 = (V1,F1) và G2 = (V2,F2)  Định nghĩa 2.2: Đồ thị G = (V, F) được gọi là tổng của G1 và G2 , ký hiệu là G1+ G2 với: 1) V = V1  V2 2) (x,y)  F(a,b)  x = a  y  F2(b) hoặc x  F1(a)  y = b. 17/29
2.3. TỔNG CỦA CÁC ĐỒ THỊ (tiếp) a a1 a2 ... ak b1 b2 . . . bk b Hình 2.5. Cách xây dựng đồ thị tổng Giả sử đồ thị G1 có hàm Grundy g1, đồ thị G2 có hàm Grundy g2. Liệu đồ thị tổng G1 + G2 có hàm Grundy hay không và mối quan hệ của nó với các hàm g1, g2 như nhế nào? 18/29
d - TỔNG CÁC SỐ NGUYÊN  Để trả lời câu hỏi này, ta đưa ra phép toán d-tổng trên các số nguyên như sau: Với các số nguyên không âm u, v  N , ta biểu diễn chúng dưới dạng nhị phân như sau: u = uk uk-1 … u1 u0 v = vk vk-1 . . . v1v0 , với ui, vi là các chữ số 0 hoặc 1. Đặt wi = (ui + vi) mod 2. 19/29
d - TỔNG CÁC SỐ NGUYÊN (tiếp) Số nguyên w có biểu diễn nhị phân là: wk wk-1 . . . w1w0 được gọi là d - tổng của u và v, ký hiệu là: w = u  v. 20/29