tailieunhanh - Lý thuyết đồ thị - Chương 4

Nội dung chương 4 trình bày về: Đồ thị phẳng và bài toán tô màu. Mời các bạn cùng tham khảo tài liệu. | Chương 3. Đồ thị phang va Bài toán Tô màu. CHƯƠNG 4. ĐỒ THỊ PHANG BAI TOAN TO MAU. . ĐINH NGHĨA VE ĐO 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ị phàng và G2 G3 là càc biêu diên phàng cua G1. Đô thị G1 Biểu diễn G2 G3 cua G1. Trương My 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. Mat h là màt vô han nhưng màt côn lài à b c d ê f g là nhưng màt hưu han. FIG. . Đ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 . ĐO thị KHONG phang loai 1 K3 3. Trương My Dung 44 Chương 3. Đồ thị phang va Bài toán Tô màu. . CONG THỨC EULER HỆQUẢ THÍ DỤ. . CONG THỨC ỆỤLER. Cho môt đồ thị phàng liên thông cô n đỉnh m canh và f mát tà cô n - m f 2 Chứng minh. Truy chưng trên sOÍcạnh m 1. Tà cô n 2 đỉnh và f 1 màt. Tà cô n - m f 2 - 1 1 2 Vày công thưc EULER đung chô trương hơp m 1. Già sư công thưc EULER đung chô trương hơp đô thị Gi-1 cô mi - 1 cành. Tà sê chưng minh công thưc EULER cung đung chô trương hơp đô thị cô mi cành.