[Seminar] SINH HOẠT KHOA HỌC: “BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG”

Vào 14h00 chiều thứ Tư ngày 27 tháng 11 năm 2024, Khoa Khoa học Cơ sở tổ chức sinh hoạt khoa học với chủ đề: “Bài toán tô màu đồ thị và ứng dụng”.

Người trình bày: ThS. Nguyễn Mai Quyên, GV Khoa Khoa học Cơ sở, ĐHKTQD.

Thành phần tham dự: Toàn thể GV Khoa Khoa học Cơ sở và các giảng viên quan tâm

Người trình bày đã trình bày các nội dung:

• Đồ thị phẳng
• Tô màu đồ thị
• Ứng dụng của bài toán tô màu đồ thị: Xếp lịch thi, phân bổ tần số, thanh ghi chỉ mục, chăn nuôi động vật

Một số ý kiến trao đổi:

– Tô màu đồ thị có rất nhiều ứng dụng thực tế trong các lĩnh vực khác nhau. Trong lập lịch trình và phân công: xếp lịch thi đấu thể thao để đảm bảo rằng không có hai trận đấu nào diễn ra cùng một lúc ở cùng một sân (các đỉnh kề nhau trong đồ thị đại diện cho các trận đấu và các cạnh đại diện cho các xung đột về sân thi đấu); phân bổ tài nguyên (ví dụ như máy móc, phòng làm việc) sao cho các tài nguyên không bị sử dụng đồng thời bởi các công việc có xung đột.

– Trong mạng viễn thông, bài toán tô màu có thể được áp dụng để phân bổ tần số cho các trạm phát sóng sao cho không có hai trạm kề nhau sử dụng cùng một tần số. Trong tối ưu hoá mạng máy tính, tô màu đồ thị có thể giúp xác định cách phân chia mạng máy tính sao cho các kênh truyền tải không bị trùng lặp và xung đột.

– Trong lập trình đồng thời, bài toán tô màu có thể được dùng để phân chia các tiến trình sao cho không có tiến trình nào xung đột với nhau khi truy cập tài nguyên chung.

– Trong phân tích mạng xã hội, tô màu đồ thị có thể giúp phân tích cấu trúc cộng đồng trong mạng xã hội, nơi các đỉnh đại diện cho người dùng và các cạnh đại diện cho mối quan hệ giữa họ.

– Bài toán tô màu đồ thị còn có nhiều ứng dụng thực tế trong các lĩnh vực như tối ưu hóa lịch trình, phân công tài nguyên, mạng viễn thông, và nhiều bài toán thực tế khác. Khi giảng dạy bài toán tô màu đồ thị, cần phải làm rõ các khái niệm cơ bản, ứng dụng thực tế, các thuật toán giải quyết bài toán, đồng thời khuyến khích sinh viên thực hành và tìm hiểu sâu hơn về các phương pháp giải quyết. Điều này sẽ giúp họ không chỉ hiểu lý thuyết mà còn có thể áp dụng vào các bài toán thực tế.

Một số hình ảnh