Đang chuẩn bị liên kết để tải về tài liệu:
Phần tích thiết kế giải thuật (phần 5)

Đồ thị kiến thức nền tảng rất quan trọng trong công nghệ thông tin, dùng nó để thể hiện dữ liệu, tìm hướng giải quyết nhiều vấn đề, trong tài liệu này các bạn sẽ được gặp lại đồ thị với một thuật toán thú vị là tô màu độ thị và ứng dụng của việc đưa ra thuật toán này là sắp lịch thi cho sinh viên . | Chương 3. Đồ thị phang va Bài toán Tô màu. CHƯƠNG 4. ĐỒ THỊ PHANG BAI TOAN TÔ MAU. 4.1. ĐINH NGHĨA VE ĐÔ THỊ PHANG. Đ ô thị phang là môt đồ thị cô thể biểu diễn trên môt mát phàng hay trên hình cáu sao cho hài cung hay hài canh không cát nhau. Ghi chú. Hai canh cô chung môt đỉnh đươc gôi là không càt nhau. Không càt nhau . Thí dụ. Đồ thị G1 là đồ thị phang và G2 G3 là các biểu dien phang cua G1. Đồ thị G1 Biêu diên G2 G3 cua G1. Trương Mỹ Dung 43 Chương 3. Đồ thị phang va Bài toán Tô màu. Cho G là đồ thị phàng. Môt mặt FACE cUà G là môt mien giơi han bơi các canh không cô đỉnh làn cạnh ơ bên trong. Trong càc màt này luôn luôn cô môt và chỉ môt màt vô han. Đường biên CONTOUR cUa môt màt r là chu trình hơp thành tư càc canh biên cua r. Hài màt r và s đươc gôi là KE ADJACENTES nêu đương biên cua chung cô chung ít nhất môt canh. Hài màt không cô chung môt đỉnh nàô thì sê không ke. THÍ DỤ. Môt bàn đô địa dư là môt đô thị phàng vơi điêu kiên là không cô đàô . Đô thị này đàc biêt môi đỉnh cô bàc 3. Màt h là màt vô han nhưng màt côn lai à b c d ê f g là nhưng màt hưu han. FIG. 4.1. ĐO thị phang. Bai toan bặ lặng vặ bặ nhặ mặy. Tà cô 3 làng à b c mà tà muôn đàt đương nôi vơi 3 nhà mày môt nhà mày cung cấp nươc d môt nhà mày cung cap gà ê môt nhà mày cung cap điên f. Vấn đê đàt ra là tà cô thể đàt trên môt màt phàng saô chô càc đương dàn không giàô nhau ngôài càc đỉnh cực biên Đô thị biêu diên 3 làng và 3 nhà mày chô phêp định nghĩa môt lơp càc đô thị không phàng. FIG 4.2. ĐO thị KHÔNG phang loai 1 K3 3. Trương My Dung 44 Chương 3. Đồ thị phang va Bài toán Tô màu. 4.2. CONG THỨC EULER HỆQUẢ THÍ DỤ. 4.2.1. CONG THỨC ỆỤLER. Cho một đồ thị phang liên thông có n đỉnh m cạnh và f mặt ta có n - m f 2 Chứng minh. Truy chứng trên só cạnh m 1. Ta có n 2 đỉnh và f 1 mặt. Ta có n - m f 2 - 1 1 2 Vạy cóng thức EULER đung chó trứờng hơp m 1. Gia sứ cóng thức EULER đung chó trứờng hơp đó thị Gi-1 có mi - 1 canh. Ta sê chứng minh cóng thức EULER cung đung chó trứờng hơp đó thị có mi canh.