Đang chuẩn bị liên kết để tải về tài liệu:
Chương III: Đồ thị phẳng

Một đồ thị vô hướng G được gọi là phẳng nếu tồn tại một cách vẽ G trong mặt phẳng sao cho không có hai cạnh nào của G cắt nhau. | Khoa Công nghệ Thông tin ĐHKHTN. CHƯƠNG III. ĐỒ THỊ PHANG III.1 Định nghĩa a Đồ thì phang - Mồt đồ thì vồ hướng G được goi la phang nếu tồn tai mồt cach vẽ G trong mặt phang sao cho khồng cồ hai canh nao cua G cat nhau. - Khi G la mồt đồ thì phang thì mồi cach vẽ G trong mạt phang sao cho khồng cồ hai canh nao cua G cat nhau được goi la một biếu diẽn phang cua G. Ghi chu hai canh cồ chung mồt đỉnh được qui ước la khồng cat nhau Không cat nhau Ví du Đồ thì G1 la đồ thì phang va cac đồ thì G2 G3 la cac biếu diẽn phang cua G3 b Phẽp biến đoi đồng phoi Thẽm vao 1 đỉnh nam trẽn 1 canh hay gồp 2 canh cồ chung đỉnh bậc 2 thanh 1 canh. c Đồ thì đồng phoi Hai đồ thì được goi la đồng phoi nếu mồi đồ thì cồ được tư đồ thì kia bang cach thực hiẽn mồt day cac phẽp biến đoi đồng phoi. Đẽ cượng bai giang mồn Ly thuyết đồ thì trang III 1 Khoa Công nghệ Thông tin ĐHKHTN. Đình ly Nếu G là một đồ thị phang thì ta co thể tìm một đổ thị G1 đồng phôi vôi G sao chô cô thế vế G1 bàng càch chỉ dung càc đoan thàng. Ví du Các đổ thị sau đây đồng phôi III.2 Cac phệp rut gon cơ ban trện đô thị Tính phàng cua một đô thị không thay đôi nếu thực hiển một hay nhiểu làn càc phểp rut gọn sau đày à Bô đi càc khuyển b Bô bôt càc canh sông sông chỉ giữ lai môt canh nôi hai đỉnh . c Gôp hai canh cô chung đỉnh bàc 2 thành môt canh. III.3 Định ly Kuratowski Đình ly 1 ĐÔ thị đu K5 không phàng. Định ly 2 Đồ thị lưỡng phân đu K3 3 không phâng. Kß 3 Đe cương bái giáng mồn Ly thuyết đồ thị trang III 2 Khoa Công nghệ Thông tin ĐHKHTN. Nhân xét hai đổ thị K5 và K3 3 là các đồ thị không phang đơn giản nhất vơi các tính chát sau - Néu xồa đi 1 đỉnh hay 1 canh cua 2 đồ thị trén thì chung tá sé cồ được đồ thị phàng. - Đồ thị K5 la đồ thị khồng phang cồ ít đỉnh nhất. - Đồ thị K3 3 la đồ thị khồng phang cồ ít canh nhất. Định ly 3. Điéu kién can va đu đé mồt đồ thị lién thồng G cồ tính phang la G khồng chứ a bat ky đồ thị cồn naồ đồng phồi vơi K5 hay K3 3. Ví du. 2 3 5 Đổng phôi Đồ thi con 2 3 5 Vẽ lại 5 7 7 III.4 Cong