Tham khảo tài liệu 'graph - phần 3', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Khoa Công nghệ Thông tin ĐHKHTN. CHƯƠNG III. ĐO THỊ PHANG Định nghĩa a Đồ thì phang - Mồt đồ thì vồ hướng G được goi la phang nếu tồn tai mồt each 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 Khong 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 Them 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 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ữ lài môt canh nối hài đỉnh . c Gôp hai canh cô chung đỉnh bàc 2 thành môt canh. Đị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. K3 3 Để cương bài giang 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 Đồ thị cồn 2 3 5 Vé lai 5 7 7 Công
