Tạp chí Khoa học Trường Đại học Sư phạm Hà Nội: Khoa học Tự nhiên, S. 3 (2019)

Cỡ chữ:  Nhỏ  Vừa  Lớn

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Ũ ĐINH HÒA

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.      

Toàn văn: PDF