tailieunhanh - Tính duy nhất của bao đóng đồ thị

Trong bài báo này, ta chứng tỏ rằng bao đóng của một đồ thị G cho trước được xác định duy nhất, không phụ thuộc vào quá trình nối các cặp đỉnh có tổng bậc không nhỏ hơn n. Ta cũng đưa ra thuật toán xác định chu trình Hamilton trong đồ thị ban đầu nếu biết trước một chu trình Hamilton trong đồ thị cl(G). | Một sỗ vấn đề chọn lọc cùa Công nghệ thông tin Đà Nắng 18-20 tháng 8 năm 2004 TÍNH DUY NHÁT CỦA BAO ĐÓNG ĐỒ THỊ Vũ Đình Hòa Đỗ Như An Nguyễn Hữu Xuân Trường Khoa CNTT Trường ĐHSP Hà nội e-mail hoavd@. Khoa CNTT Trường ĐHTS Nha Trang. Tóm tắt Từ những năm 1976 Chvátal và Bondy 3 đã đưa ra khái niệm bao đóng. Bao đóng CỈ G cùa đồ thị đơn vô hướng G với p đinh được tạo bằng cách lần lượt noi các cặp đinh không kề nhau có tổng bậc không nhỏ hơn p. Bao đóng có một vai trò lý thuyết quan trọng trong việc xác định chu trình Hamilton chu trình đi qua tất cả các đinh của một đồ thị cho trước . Trong bài báo này ta chứng tò rằng bao đóng cùa một đồ thị G cho trước được xác định duy nhất không phụ thuộc vào quả trình nối các cặp đinh có tổng .bậc không nhò hơn n. Ta cũng đưa ra thuật toán xác định chu trình Hamilton trong đồ thị ban đầu nếu biết trước một chu trỉnh Hamilton trong đồ thị CỈ G . 1. CÁC KHÁI NIỆM Cơ BẢN Cho trước một đồ thị đơn vô hướng G V E với tập đỉnh V và tập cạnh E trong đó V có p đinh. Hai đình của đồ thị đựợc gọi là kề nhau nếu chúng được nối bởi một cạnh. Cho trước hai đỉnh kề nhau u và V ta kí hiệu cạnh nối u và V bời uv. Bậc của một đình là số cạnh xuất phát từ nó được ký hiệu bởi dG v hoặc chi đơn giàn là d v . Một đồ thị Gi được gọi là đồ thị con của đồ thị G2 V E2 nếu như ta có Vi a v2 và Et G E2. Khi bổ sung một cạnh e mới nối hai đỉnh không kề nhau của đồ thị G ta sẽ ký hiệu đồ thị thu được bởi G e. Một chu trình là một dãy đỉnh vb v2 . vk vt mà hai đình liên tiếp Vị và vi 1 vk i V được nối với nhau bởi một cạnh. Ta gọi một chu trình là chu trình Hamilton hình 1 nếu như nó đi qua tất cà các đình của đồ thị. Đe gọn ta gọi một đồ thị có chu trình Hamilton là đồ thị Hamilton. Hình 1. Các cạnh của chu trình Hamilton được vẽ đậm nét. 2. BAO ĐÓNG CỦA MỘT ĐỒ THỊ CHO TRƯỚC Khái niệm bao đóng cùa đồ thị được Bondy and Chvátal đưa ra lần đầu tiên trong 3 . Cho trước một đồ thị Go khi đó bao đóng của Go là đồ thị thu được bằng cách bổ sung .