TAILIEUCHUNG - Kết quả mới về đồ thị Hamilton tối đại.

Kết quả mới về đồ thị Hamilton tối đại. Lý thuyết chung các hệ thống là thuật ngữ đã được L. Von Bertalarffy đưa vào vốn từ vựng khoa học để mô tả lý thuyết các hệ thống mở và các trạng thái cân bằng động năm 1933 tại trường đại học tổng hợp Chicago. | Tạp chí Tin học và Đĩêu khiển học 2006 117-122 KẾT QUÁ MỚI VỀ ĐỒ THỊ HAMILTON Tốl ĐẠI VÙ ĐÌNH HÒA1 ĐỒ NHƯ AN2 Khoa Công nghệ thông tin Trường Đại học Sư phạm Hà Nội 2Khoa Công nghệ thông tin Trường -Đại học Thủy sản Abstract. A graph is called a maximal uniquely Hamiltonian graph if it has the maximum number of edges among the graphs with the same number of vertieces and exact one Hamiltonian cycle. Maximal uniquely Hamiltonian graph was studied by Sheehan 5 . Sheehan proved that maximal 2 uniquely Hamiltonian graph with n 3 vertices contains 4 1 edges. He confirms that for every n 3 there is only maximal uniquely Hamiltonian graph. In this paper we construct two maximal 1TT-1- 1 . r n 71 uniquely Hamiltonian graphs with 9 vertices and show that for every n 7 there are at least 2L 2 J maximal uniquely Hamiltonian graphs. Tóm tắt. I t đồ thị được gọi là đồ thị Hamilton tối đại nếu như nó có số cạnh nhiêu nhất có thể trong các đồ thị có cùng số đỉnh và có đúng một chu trình Hamilton. Đồ thị Hamilton tối đại được Sheehan 5 nghiên cứu. Sheehan đã chứng minh rang đồ thị Hamilton tối đại với n đỉnh là duy nhất và có đúng y 1 cạnh. Trong bài này ta bác bỏ kết quả của Sheehan bằng cách chỉ ra hai đo thị Hamilton toi đại 9 đỉnh và xây dựng 21 2 do thị Hamilton toi đại n đỉnh sai khác nhau qua phép đẳng cấu. 1. MỞ ĐẦU Trong bài báo này chúng ta chỉ nói đến các đồ thị hữu hạn vò hướng. Mọi ký hiệu và. khái niệm ở đây được lấy từ 1 . Cho trước một đồ thị đơn vò hướng G ta. gọi một chu trình c của. G là. chu trình Hamilton nếu như nó đi qua. tất cả. các đỉnh của. đồ thị G. Hình 1. Đồ thị có hai chu trình Hamilton Trong Hình 1 ta. có một đồ thị với hai chu trình Hamilton khác nhau. Đồ thị không có chu trình Hamilton với nhiều cạnh nhất đã. được nghiên cứu bởi Erdỏs cũng như một số nhà. toán học khác. Nếu đồ thị G có một chu trình Hamilton thì nó được gọi là. đồ thị Hamilton. 118 vũ ĐÌNH HÒA Đỏ NHU AN Một đồ thị chỉ có đúng một chu trình Hamilton được gọi là dồ thị .

• Tự động hoá
• đồ thị Hamilton
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Lý thuyết đồ thị
• Chu trình Hamilton
• Đường đi Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đồ thị nửa Hamilton
• Chứng minh định lý Ore
• Định lý Dirac
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Chứng minh đồ thị là nửa Euler
• Chu trình Euler
• Bài toán lý thuyết đồ thị
• 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
• tài liệu học môn toán
• đồ thị
• toán học
• tài liệu đồ thị hamilton
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Đồ 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
• thuật toán tìm chu trình
• đồ thị liên thông
• Số đồ thị Hamilton
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị hamiton
• bài giảng đồ thị phẳng
• giáo dục
• đào tạo
• cao đẳng
• đại học
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Thuật toán tìm kiếm trên đồ thị
• Cây khung của đồ thị
• Bài tập Lý thuyết đồ thị
• Thực hành Lý thuyết đồ thị
• Đồ thì Euler
• Đồ thị cây
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đại cương về đồ thị
• Đồ thị có trọng số
• Bài toán đường đi ngắn nhất
• Hamilton
• tóan rời rạc
• khoa học tự nhiên