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

• Toán học
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng