Một số bài toán tô màu đồ thị

Lê Thị Mai Thảo
Khoa cơ bản, Trường Cao đẳng CNTT Hữu Nghị Việt Hàn
Email: maithao9983@gmail.com, thaoltm@viethanit.edu.vn

Tóm tắt
Nghiên cứu cung cấp một số kiến thức cơ bản về lí thuyết đồ thị và tô màu đồ thị, trình bày thuật toán tô màu cho các đỉnh và tô màu cho các cạnh của đồ thị. Đồng thời, nghiên cứu cũng mô hình hoá bởi đồ thị để giải một số bài toán thực tế như: Bài toán xếp lịch thi, bài toán điều khiển đèn hiệu nút giao thông. Ngoài ra, còn nghiên cứu khai thác một số ứng dụng của tô màu đồ thị trong việc giải các bài toán tổ hợp, bài toán đồ thị cạnh màu.

Từ khóa: Tô màu đồ thị, tô màu đỉnh, tô màu cạnh, đồ thị.

Fulltext:download

 

 

Chia sẻ