Lý thuyết đồ thị - Phần 4

Tham khảo tài liệu lý thuyết đồ thị - phần 4, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Lý thuyết đồ thị - Phần 4 3.4.Đồthịphẳng 3.4.1.Địnhnghiãvàvídụ  Biểudiễnphẳng  Đồthịphẳng  Vídụ1. biểudiễnphẳng biểudiễnkhôngphẳng đồthịphẳng đồthịphẳng 3.4.Đồthịphẳng  Vídụ2.  Vídụ3. 3.4.Đồthịphẳng 3.4.2.ĐịnhlýEulervàcáchệquả  ĐịnhlýEuler: Sốmiềnphẳng=sốcạnhsốđỉnh+2  Hệquả1: NếuG=(V,E)làđơnđồthịphẳng,liênthôngcómđỉnh (m≥ 3)vàncạnh.Khiđóm≤ 3n6 Vídụ4:ChứngminhK5khôngphẳng  Hệquả2: NếuG=(V,E)làđơnđồthịphẳng,liênthôngcómđỉnh (m≥ 3)vàncạnh,khôngcóchutrìnhđộdài3.Khiđó m≤ 2n4 Vídụ5:ChứngminhK3,3khôngphẳng 3.4.Đồthịphẳng 3.4.2.Đồthịđồngphôivà địnhlýKuratovski  Phépphânchiasơcấp  Từ một đồ thị phẳng G=(V,E), nếu bỏ đi một cạnh và thêm vào một đỉnhcùngvớihaicạnhnốiđỉnhvừa thêm với các đỉnh kề của cạnh vừa bỏ đi thi ta nói đã thực hiện một phépphânchiasơcấpđồthịG.  Đồthịđồngphôi  Hai đồ thị G1 và G2 được gọi là đồngphôinếuchúngcùngthuđược từ một đồ thị bằng một số hữu hạn cácphépphânchiasơcấp. 3.4.Đồthịphẳng  ĐịnhlýKuratovski Mộtđồthịkhôngphẳngkhivàchỉkhi nóchứamộtđồthịconđồngphôivới K3,3hoặcK5.  Vídụ:  ĐồthịPetersen  ĐồthịKnphẳngkhinào?  ĐồthịQnphẳngkhinào?