TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 3: Đồ thị phẳng

Nội dung chương này trình bày khái niệm và định nghĩa, công thức Euler, một số đồ thị không phẳng, bất đẳng thức EV, định lý Kuratowski, ứng dụng đồ thị phẳng trong bài toán tô màu đồ thị, bài toán lập lịch thi. | Bài giảng LÝ THUYẾT ĐÒ THỊ GRAPH THEORY TRẦN QUỐC VIỆT Nội dung 1. Khái niệm và định nghĩa 2. Công thức Euler 3. Một số đồ thị không phẳng 4. Bất đẳng thức EV 5. Định lý KURATOWSKI 6. ứng dụng đồ thị phẳng trong Bài toán tô màu đồ thị Bài toán lập lịch thi 24 10 2013 Chương 3 ĐÒ THỊ PHẲNG Planar Graph 1. Khái niệm và định nghĩa Bài toán cổ Ba nhà ba giếng Có ba nhà ở gần ba cái giếng nhưng - Không có đường nối trực tiếp giữa các nhà với nhau - Không có đường nối trực tiếp giữa các giếng với nhau có cách làm các đường này mà đôi một không giao nhau hay không ngoài các điểm là nhà hay giếng 1 Khái niệm và định nghĩa Biểu diễn bài toán bằng đồ thị - Mỗi nhà một đỉnh - Mỗi giếng một đỉnh - Một đường đi giữa một nhà và một giếng một cạnh Tồn tại hay không cách vẽ đồ thị phân đôi đầy đủ K3 3 trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau 24 10 2013 Khái niệm và định nghĩa Định nghĩa đồ thỉ phăng - Một đồ thị được gọi là đồ thị phẳng Planar Graph nếu ta có thể vẽ nó trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau ở một điểm không phải là đỉnh của đồ thị việc vẽ đồ thị trên mặt phẳng gọi là biểu diễn phẳng của đồ thị Biểu diễn phẳng của G và Q3 Xem như bài tập Gợi ý cách c m K3 3 không phẳng - Ta thấy trong mọi biểu diễn phẳng của K3 3 Vj và v2 luôn kê với v4 v5. v3 phải nằm trong các vùng Fi hoặc F2 V v5 i -------9 3 R1 r2 2 Khái niệm và định nghĩa Cho G là đồ thị phẳng Q Các cạnh của đô thị chia mặt n phăng thành các miên Region Phần giới hạn bởi một chu trình O Miền 2 đơn không chứa bên trong một chu J trình đơn khác đuợc gọi là một miền hữu hạn. miên 1 miện 2 hữu hạn Mọi đồ thị phẳng luôn có một miền 3 vô hạn miền vô hạn duy nhất. 5 4 4 2 2 5 ĩ Chu trình giới hạn miền gọi là BÍên của mien 1 biên của miền 24 10 2013 Khái niệm và định nghĩa Ví dụ Fp F2 f3 F4 F5 các miền hữu hạn F6 Miền vô hạn

• Toán học
• Đồ thị phẳng
• Lý thuyết đồ thị
• Bài giảng lý thuyết đồ thị
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Định lý Kuratowski
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• tô màu đồ thị
• Vẽ đồ thị
• biểu diễn đồ thị
• bài toán luồng trên mạng
• Bài toán tô màu đồ thị
• Công thức Euler
• Đồ thị không phẳng
• Bài toán lý thuyết đồ thi
• Toán rời rạc
• Bài giảng Toán rời rạc
• Toán rời rạc ứng dụng trong tin học
• Đại cương về đồ thị
• Tạp chí đại học Tân Trào
• Tính chất đồ thị lên ràng buộc
• Môi trường tự nhiên
• Đồ thị ràng buộc
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Đồ thị con
• Đồ thị riêng
• Bài toán đường đi ngắn nhất
• Thuật toán cây nhị phân
• Đường đi đồ thị
• Chu trình Hamilton
• 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
• Phương pháp toán sơ cấp
• Bài toán tô màu bản đồ
• Giáo dục đào tạo
• cao đẳng đại học
• giáo trình toán
• công thức Enler
• giáo trình cao đẳng đại học
• đồ thị đồng phôi
• Phân tích thuật toán
• Thiết kế thuật toán
• Ngôn ngữ C
• Đối ngẫu hình học
• Đối ngẫu tổ hợp
• Bất đẳng thức cạnh đỉnh
• Đồ thị Petersen
• Đồ thị và Các thuật toán
• Hàm Grundy trên đồ thị
• Cây và một số ứng dụng
• Mạng vận tải