tailieunhanh - Sử dụng chu trình Euler xây dựng tất cả các đồ thị có dãy bậc cho trước

Một vấn đề cơ bản của lí thuyết đồ thị đã tồn tại từ lâu là tìm tất cả các đồ thị có dãy bậc là một dãy số tự nhiên cho trước. Vấn đề này không chỉ là lí thuyết cơ bản mà còn có ứng dụng trong khoa học và thực tế. | Sử dụng chu trình Euler xây dựng tất cả các đồ thị có dãy bậc cho trước HNUE JOURNAL OF SCIENCE DOI: Natural Sciences 2019, Volume 64, Issue 3, pp. 74-81 This paper is available online at SỬ DỤNG CHU TRÌNH EULER XÂY DỰNG TẤT CẢ CÁC ĐỒ THỊ CÓ DÃY BẬC CHO TRƯỚC Vũ Đình Hòa Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Một vấn đề cơ bản của lí thuyết đồ thị đã tồn tại từ lâu là tìm tất cả các đồ thị có dãy bậc là một dãy số tự nhiên cho trước. Vấn đề này không chỉ là lí thuyết cơ bản mà còn có ứng dụng trong khoa học và thực tế. Kết quả chính trong bài báo này là một thuật toán dựa trên khái niệm đồ thị cân bằng (có thể xây dựng được nhờ các chu trình Euler đan màu) để xác định tất cả đồ thị có dãy bậc cho trước. Từ khóa: Đồ thị đơn, chu trình Euler, bậc của đỉnh. 1. Mở đầu Bài báo này chỉ khảo sát đồ thị đơn vô hướng. Các khái niệm cơ sở có thể tham khảo từ nhiều nguồn tài liệu khác nhau như trong tài liệu [1]. Một dãy số tự nhiên d = (d1 ,.,dn) được gọi là dãy bậc nếu tồn tại một đồ thị đơn vô hướng n đỉnh để bậc của đỉnh i là di . Một vấn đề cơ bản của lí thuyết đồ thị đã tồn tại từ lâu là tìm tất cả các đồ thị có dãy bậc là một dãy số tự nhiên cho trước. Vấn đề này không chỉ là lí thuyết cơ bản mà còn có ý nghĩa thực tế [2, 3]. Hình 1. Hệ thống mạng cung cấp thực phẩm Chesapeake Bay [2] Đã có nhiều nhà khoa học đề cập tới nó, như Havel [4], Erdös và Gallai [5], Hakimi và Havel [4], Zoltán [6], Hyunju Kima, Zoltán Toroczkai, István Miklós, Péter L. Erdos, László A. Székely trong [5], M. Mihail- N. Vishnoi [3], Jonathan McLaughlin [4]. Tuy nhiên, cho đến nay, vấn đề này vẫn chưa được giải quyết triệt để. Havel [4], Erdös và Gallai [4], Hakimi và Havel [4] mới chỉ Ngày nhận bài: 12/12/2018. Ngày sửa bài: 13/3/2019. Ngày nhận đăng: 20/3/2019. Tác giả liên hệ: Vũ Đình Hòa. Địa chỉ e-mail: hoavudinh@ 74 Sử dụng chu trình