ĐỊNH LÝ KURATOWSKI TƠ MÀU ĐỒ THỊ T Ơ MÀU ĐỒ THỊ ... - 123doc

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Cơ sở dữ liệu >

ĐỊNH LÝ KURATOWSKI TƠ MÀU ĐỒ THỊ T Ơ MÀU ĐỒ THỊ TƠ MÀU ĐỒ THỊ T Ơ MÀU ĐỒ THỊ TƠ MÀU ĐỒ THỊ TƠ MÀU ĐỒ THỊ BÀI TỐN THỰC TẾ

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (550.94 KB, 178 trang )

3. ĐỊNH LÝ KURATOWSKI

Định lý Kuratowski: Một đồ thị là đồ thị phẳng khi và chỉkhi nó khơng chứa đồ thị con đồng phôi với K3,3hoặc K5a bd e1G abc de fhg2G abc de kig j3GVí dụ: G2và G3là hai đồ thị đồng phơi vì chúng có thể nhận được từ đồ thị G1bằng các phép phân chia sơ cấp.

4. TƠ MÀU ĐỒ THỊ

Bài tốn: Để phân biệt các miền trên bản đồ ta phải tô màu chúng bằng các màu khác nhau.Hỏi cần ít nhất bao nhiêu màu để tô một bản đồ bất kỳ sao cho các miền kề nhau không cùng mộtmàu.B BCD EF CA DE FG

4. T Ơ MÀU ĐỒ THỊ

Mơ hình hố bài tốn: + Mỗi miền tương ứng một đỉnh của đồ thị.+ Hai đỉnh có cạnh nối nếu chúng là hai miền cóchung biên giới. Đồ thị nhận được gọi là đồ thị đối ngẫu của bản đồ.Đồ thị đối ngẫu của bản đồ là đồ thị phẳng.Bài tốn tương đương: tơ màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau thì được tơ bởi hai màukhác nhau.

4. TƠ MÀU ĐỒ THỊ

Ví dụ:A BCD EA BD EC

4. T Ơ MÀU ĐỒ THỊ

Định nghĩa: Tô màu đồ thị là việc gán màu chocác đỉnh của đồ thị sao cho không có hai đỉnh kề nhau được gán cùng một màu.Định nghĩa: số màu của một đồ thị là số màu tốithiểu cần để tô màu đồ thị này. Định lý 4 màu: số màu của một đồ thị phẳng bấtkỳ là một số không lớn hơn 4. Nhận xét:- Số màu của đồ thị lưỡng phân là 2 màu.- Số màu của đồ thị đầy đủ Knlà n màu

4. TÔ MÀU ĐỒ THỊ

Ví dụ:D AE BCA BCD E

4. TƠ MÀU ĐỒ THỊ

Ví dụ: Bài tốn lập lịch thi Hãy lập lịch thi trong trường đại học sao chokhơng có sinh viên nào phải thi đồng thời hai môn cùng một lúcGiải: Mô hình hóa bài tốn như sau:- Mỗi đỉnh là một mơn thi- Hai đỉnh có cạnh nối nếu đó là hai mơn mà mộtsinh viên nào đó phải thi. Thời gian mỗi mơn thi ứng với một màu.Bài tốn trở thành bài tốn tơ màu cho đồ thị trênsao cho hai đỉnh kề nhau có màu khác nhau.Bài 7BÀI TỐN TÌM ĐƯỜNG ĐINGẮN NHẤTBộ mơn: Khoa học máy tínhKhoa: Cơng nghệ thơng tin – SPHN

1. BÀI TỐN THỰC TẾ

Có 6 điểm du lịch trong một khu sinh thái là a, b, c, d, e, z. Giữa hai điểm có thể có hoặc khơngcó đường đi trực tiếp.Hãy tìm đường đi có khoảng cách ngắn nhất từ điểm a đến z.

1. BÀI TOÁN THỰC TẾ

Xem Thêm

Tài liệu liên quan

• Lý thuyết đồ thị định nghĩa và phân loại
  • 178
  • 1,461
  • 11

Tải bản đầy đủ (.ppt) (178 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(3.19 MB) - Lý thuyết đồ thị định nghĩa và phân loại-178 (trang) Tải bản đầy đủ ngay ×