1/29
CHƯƠNG 2
HÀM GRUNDY TRÊN ĐỒ THỊ
2/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
3/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
4/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.
5/29
ĐỊNH NGHĨA HÀM GRUNDY
Giả sử G= (V, F) là một đồ thị.
Hàm g: VN được gọi là hàm Grundy của đồ thị G
nếu:
x V : g(x) = min {N \ g(F(x))}.