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

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.      

DOI: 10.18173/2354-1059.2019-0009