tailieunhanh - Giáo trình đồ thị - Hàm Grundy trên đồ thị

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ị. Trước tiên, ta ký hiệu tập các số nguyên không âm là N = {0, 1, 2, . . .}. . Hàm Grundy Định nghĩa : 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))}. | BÀI 03 Hàm Grundy trên đồ thị 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ị. Trước tiên ta ký hiệu tập các số nguyên không âm là N 0 1 2 . . . . . Hàm Grundy Định nghĩa 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 Vx e V g x min N g F x . Từ định nghĩa trên suy ra hai tính chất đặc trưng của hàm Grundy như sau 1 V x y e V nếu y e F x thì g x g y . 2 V u e N u g x u e g F x nghĩa là 3 y e F x để g y u. Tính chất 1 chỉ ra rằng g x không nằm trong tập giá trị của g trên F x và tính chất 2 khẳng định g x là số nguyên không âm bé nhất trong số các số không thuộc tập giá trị của hàm g trên F x . Từ định nghĩa của hàm Grundy ta có một số nhận xét sau đây 1. Đồ thị có đỉnh nút thì không thể có hàm Grundy. 2. Nếu F x 0 thì g x 0 . 3. Tập hợp x I x eV g x 0 luôn luôn khác rỗng. 4. V x e V g x I F x I nghĩa là hàm Grundy nhận giá trị không lớn. Ví dụ Hàm Grundy có thể không duy nhất. Hình . Đồ thị có hai hàm Grundy Ví dụ Hàm Grundy có thể không tồn tại. Hình . Đồ thị không có hàm Grundy Vậy với điều kiện nào thì một đồ thị có hàm Grundy. Định lý Đồ 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 có thể giả thiết rằng đồ thị G liên thông. Ta xây dựng hai dãy tập con các đỉnh V0 V1 . và Po p1 . lần lượt như sau Vo V Po x F x 0 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 Vo Po P1 x x eVi A F x c V V1 v2 V1 P1 Pi x x eVi A F x c V Vi với i 2 V 1 Vi Pi Chú ý 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 là pk rỗng nhưng Vk không rỗng khi đó với mỗi x E Vk sẽ có y G F x để y t V Vk nghĩa là y G Vk. Vậy với mọi đỉnh trong Vk luôn có đỉnh kề cũng thuộc Vk. Khi đó xuất phát từ một đỉnh trong Vk có thể tạo