TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị

Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị được biên soạn nhằm cung cấp cho các bạn những kiến thức về đồ thị phẳng; công thức Euler; định lý Kuratowski; tô màu đồ thị; bài toán tô màu đồ thị; ứng dụng của đồ thị phẳng. | Chương 4 Đồ thị phẳng – Bài toán tô màu đồ thị 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ thị phẳng Bài toán mở đầu: Có 3 gia đình, 3 nhà cung cấp điện, nước, gas. Các gia đình đều cần điện, nước, gas và đều muốn đi dây riêng. Cần nối dây từ các gia đình đến các nhà cung cấp sao cho không dây nào cắt dây nào. 5/14/2020 4:53:08 AM Lý thuyết đồ thị A B C ? Đồ thị phẳng Định nghĩa: Đồ thị vô hướng G là đồ thị phẳng nếu ta có thể biểu diễn nó trên một mặt phẳng sao cho không có cạnh nào cắt nhau. VD: 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ thị phẳng Không là đồ thị phẳng Đồ thị phẳng (tt) Các đồ thị không phẳng nổi tiếng 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ thị K5 – đồ thị đầy đủ Đồ thị K3x3 – đồ thị hai phía đầy đủ Công thức Euler Xét đồ thị sau: Định lý: Cho G là đồ thị phẳng, liên thông với n đỉnh và m cạnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó, ta có: r = m - n + 2 5/14/2020 4:53:08 AM Lý thuyết đồ thị 1 4 3 2 5 6 Công thức Euler (tt) Chứng .

• Toán học
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị