tailieunhanh - Lý thuyết đồ thị (Nguyễn Thanh Sơn) - chương 4 ĐỒ THỊ PHẲNG

Đồ 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 | ĐỒ 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ị

• Toán học
• tô màu đồ thị
• lý thuyết đồ thị
• Vẽ đồ thị
• biểu diễn đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• Đồ thị tách cực
• Đa thức tô màu
• Đồ thị duy nhất tô màu
• Bài toán tô màu đồ thị
• Đồ thị duy nhất k tô màu danh sách
• Tô màu danh sách đỉnh
• Tô màu đỉnh
• Chu trình Hamilton
• kỹ thuật đồ hoạ
• Area Filling
• lập trình đồ hoạ vi tính
• tài liệu học Tô màu đồ thị
• Bài giảng Lý thuyết đồ thị
• Công thức Euler
• Định lý Kuratowski
• Luận văn thạc sĩ
• Tóm tắt luận văn thạc sĩ khoa học
• Luận văn thạc sĩ khoa học
• Ứng dụng bài toán tô màu đô thị
• Giáo dục đào tạo
• cao đẳng đại học
• ứng dụng của bài toán tô màu
• giáo trình toán học
• Luận văn Thạc sĩ Toán học
• Luật tương hỗ trong tô màu đồ thị
• Luật tương hỗ
• Phương pháp toán sơ cấp
• Bài giảng Toán rời rạc
• Toán rời rạc
• Tô màu đỉnh của đồ thị
• Thuật toán tham lam tô màu đỉnh
• Đồ thị hai phần
• Thuật toán tham lam
• Toán rời rạc ứng dụng trong tin học
• Đại cương về đồ thị
• Phân tích thuật toán
• Thiết kế thuật toán
• Tổng quan đồ thị
• Bài toán đồ thị
• Báo cáo chuyên đề Công nghệ thông tin
• Nhập môn trí tuệ nhân tạo
• Thuật giải heuristic
• Bài toán tô màu đỉnh
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• đồ thị
• nguyên lý đồ thị
• tài liệu về đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• Tóm tắt luận văn Thạc sĩ
• Tóm tắt luận văn Thạc sĩ Toán học
• Bài toán tô màu bản đồ
• Đồ thị không phẳng
• Bài toán lý thuyết đồ thi
• đồ thị trên máy tính
• ma trận
• Đường đi đồ thị
• thuật toán tô màu đô thị
• xếp lịch thi
• chuyên đề toán học
• kiến thức toán
• Sắc số của đồ thị
• chu trình độ dài chẵn
• thuật toán
• tìm sắc số đồ thị
• đồ thị vô hướng
• Định lý Kuratowsky
• Lý thuyết tổ hợp
• Nghịch đảo Mobius
• Bài toán tối ưu trên đồ thị
• Độ liên thông
• Nhân tử của đồ thị
• Lý thuyết ramsey