tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 4 - Nguyễn Thanh Sơn

Chương 4 - Đồ thị phẳng. Trong chương này sẽ cung cấp một số kiến thức cơ bản về đồ thị phẳng và tô màu đồ thị như: Định nghĩa, các phép rút gọn cơ bản, định lý Kuratowsky, công thức Euler. để biết thêm các nội dung chi tiết. | ĐỒ THỊ PHẲNG ntsonptnk@ NỘI DUNG Đồ thị phẳng Định nghĩa Các phép rút gọn cơ bản Định lý Kuratowsky Công thức Euler Tô màu đồ thị Lý thuyết đồ thị , chương 4 - Nguyễn Thanh Sơn ĐỒ THỊ PHẲNG Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Đồ 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. Khi G là một đồ thị phẳng thì mỗi 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 được gọi là một biểu diễn phẳng của G. Hai cạnh chung đỉnh được qui ước là không cắt nhau ĐỊNH NGHĨA Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn G1 là đồ thị phẳng. G2, G3 là các biểu diễn phẳng của G1 VÍ DỤ Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn C A D B C A D B C A D B G2 G1 G3 Các PHÉP BIẾN ĐỔI ĐỒNG PHÔI: Thêm 1 đỉnh nằm trên một cạnh Gộp 2 cạnh chung đỉnh bậc 2 thành 1 cạnh ĐỒ THỊ ĐỒNG PHÔI: Hai đồ thị được gọi là đồng phôi nếu mỗi đồ thị có được từ đồ thị kia bằng cách thực hiện một dãy . | ĐỒ THỊ PHẲNG ntsonptnk@ NỘI DUNG Đồ thị phẳng Định nghĩa Các phép rút gọn cơ bản Định lý Kuratowsky Công thức Euler Tô màu đồ thị Lý thuyết đồ thị , chương 4 - Nguyễn Thanh Sơn ĐỒ THỊ PHẲNG Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Đồ 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. Khi G là một đồ thị phẳng thì mỗi 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 được gọi là một biểu diễn phẳng của G. Hai cạnh chung đỉnh được qui ước là không cắt nhau ĐỊNH NGHĨA Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn G1 là đồ thị phẳng. G2, G3 là các biểu diễn phẳng của G1 VÍ DỤ Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn C A D B C A D B C A D B G2 G1 G3 Các PHÉP BIẾN ĐỔI ĐỒNG PHÔI: Thêm 1 đỉnh nằm trên một cạnh Gộp 2 cạnh chung đỉnh bậc 2 thành 1 cạnh ĐỒ THỊ ĐỒNG PHÔI: Hai đồ thị được gọi là đồng phôi nếu mỗi đồ thị có được từ đồ thị kia bằng cách thực hiện một dãy các phép biến đổi đồng phôi ĐỒ THỊ ĐỒNG PHÔI Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Các đồ thị đồng phôi VÍ DỤ Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Nếu G là đồ thị phẳng thì ta có thể tìm được đồ thị G1 đồng phôi với G và G1 có biểu diễn phẳng với các cạnh là các đoạn thẳng. ĐỊNH LÝ Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Tính phẳng của một đồ thị không thay đổi nếu thực hiện một hay nhiều lần các phép rút gọn sau đây: Bỏ đi các khuyên Bỏ bớt các cạnh song song, chỉ giữ lại một cạnh nối hai đỉnh. Gộp hai cạnh có chung đỉnh bậc 2 thành một cạnh. CÁC PHÉP RÚT GỌN CƠ BẢN Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn VÍ DỤ Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn Đồ thị đủ K5 không phẳng Đồ thị lưỡng phân đủ K3,3 không phẳng ĐỊNH LÝ KURATOWSKY Lý thuyết đồ thị - chương 4 - Nguyễn Thanh Sơn K5 và K3,3 là các đồ thị không phẳng đơn giản nhất theo nghĩa: Xóa bất kỳ đỉnh hoặc cạnh của các đồ thị trên sẽ nhận được đồ thị phẳng K5 là đồ thị