TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 3

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ị. | 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. 1 0 0 ---- --- 1 c 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à P0 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 eV1 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 G 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

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton