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 mt 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 m Grundy của đồ thG
nếu:
x V : g(x) = min {N \ g(F(x))}.