TAILIEUCHUNG - Ebook Hướng dẫn giải bài tập toán rời rạc: Phần 2 – Đỗ Đức Giáo

Nối tiếp nội dung phần 1 cuốn sách “Hướng dẫn giải bài tập toán rời rạc”, phần 2 trình bày các nội dung: Đường Euler và hamilton - Bài toán tìm đường đi ngắn nhất, đồ thị phẳng - sắc số của đồ thị và bài toán tô màu bản đồ, lôgic và ứng dụng,… nội dung chi tiết. | Chương 8 ĐỔ THỊ PHẲNG - SẮC số CỦA Đổ THỊ VÀ BÀI TOÁN TÔ MÀU BẢN Đố A. TÓM TẮT LÝ THUYẾT 1. ĐỔ THỊ PHẲNG VÀ CÁC TÍNH CHẤT CỦA NÓ 1. Các khái niệm và các định nghĩa liên quan tới đồ thị phẳng Đổ thị vô hướng G x u gọi là đồ thị phẩng khi và chỉ khi G có thể vẽ được trên một mặt phẳng sao cho các cạnh của nó chỉ cắt nhau ở đỉnh mà thôi. Hình vẽ đó của G gọi là biểu diễn phẳng của đồ thị G và ký hiệu là Gp. Biểu diễn phẳng của G tạo ra trên mặt phẳng các diện hữu hạn mà mỗi diện là một miền của mặt phẳng được giới hạn bởi các cạnh của đồ thị G gọi là biên sao cho hai điểm bất kỳ của miền này đều có thể nối bằng một nét liền mà không gặp một đỉnh hoặc một cạnh nào ở bên trong. Ví dự G x u có dạng là một đồ thị phăng vì nó có biểu diễn phăng GpCÓ dạng được tạo nên bởi 4 diên d d2 d3 là 3 diên hữu hạn còn d4 là diện vô hạn. Diện vô hạn là phần mặt phẳng còn lại sau khi đã loại bỏ tất cả cả các diện hữu hạn của đổ thị Gp. 177 12- HDGBTTRR Hai diện trong biểu diễn phẳng của một đồ thị được gọi là kề nhau nếu biên của chúng có ít nhất một cạnh chung. Hai diộn chỉ tiếp xúc tại một điềm không gọi là hai diện kề nhau. Một cách tổng quát nếu G là một đổ thị phẳng thì biểu diễn phẳng cùa G ta ký hiệu là Gp chia mặt phẳng thành r miền dị d2 . dr trong đó r - 1 miền hữu hạn dj d2 . dj-j còn một miển vô hạn là dr. Ta ký hiệu m dị là bậc của diện dj với định nghĩa m dj số các cạnh của G tạo nên diện dj. Bậc của biểu diễn phẳng Gp là r m Gp m dị ở đây r là số diện được tạo ra trong biểu diễn i l phảng Gp củaG. Chu số của đồ thị G x u với 1X1 n đỉnh IUI m cạnh và p thành phần liên thông ký hiệu là C G m - n p. Chu số của đổ thị liên quan tới nhiều tính chất trong lý thuyết đổ thị trong đó có liên quan tới số diện trong biểu diễn phảng của đồ thị. Đồ thị K5 và K3 3 là không phẳng. Nếu mọi đồ thị G x u chứa K5 hoặc K3 3 như là đồ thị con cùa nó đều là đồ thị không phẳng. Nếu một đồ thị là phẳng mọi đồ thị nhận được từ đổ thị này bằng cách bỏ đi cạnh a b và thêm vào đỉnh mới c cùng hai .

• Toán học
• Hướng dẫn giải bài tập toán rời rạc
• Bài tập toán rời rạc
• Đường Euler và hamilton
• Bài toán tô màu bản đồ
• Lôgic ứng dụng
• Logic mệnh đề
• Ngôn ngữ hình thức
• Văn phạm và ôtômat
• Biểu thức chính quy
• Ngôn ngữ chính quy
• Đồ thị và ứng dụng
• Mô hình suy luận logic mệnh đề
• Suy luận logic mệnh đề
• Lý thuyết về suy luận logic mệnh đề
• Bài tập suy luận logic mệnh đề
• Quy luật logic cơ bản
• Giáo trình Logic học ký hiệu
• Logic học ký hiệu
• Ngôn ngữ logic mệnh đề
• Hình thức mệnh đề
• Bảng giá trị công thức mệnh đề
• đại số logic
• mệnh đề
• đại số mệnh đề
• chân trị mệnh đề
• phép toán mệnh đề
• phép toán logic
• toán lập trình
• cơ sở logic
• Bài giảng Toán tin
• Bài toán logic
• Mệnh đề logic
• Dạng mệnh đề logic
• Quy tắc suy diễn logic
• Sách tham khảo Logic toán
• Logic toán
• Các phép toán mệnh đề
• Mệnh đề liên hợp
• Phương trình logic
• Phép toán logic trên vị từ
• Ebook Logic toán
• Logic vị từ
• Hệ toán mệnh đề
• Bài tập Đại số logic
• Hàm mệnh đề
• Bài giảng Trí tuệ nhân tạo
• Trí tuệ nhân tạo
• Bài giảng Trí tuệ nhân tạo chương 5
• Sử dụng logic mệnh đề
• Sử dụng logic mệnh đề và vị từ
• Công thức mệnh đề
• Quy tắc suy luận logic
• Phép tính tiên đề
• Bài giảng Toán rời rạc
• Toán rời rạc
• Biểu thức logic
• Các luật logic
• Hàm đại số logic
• Logic mờ
• Định lý suy diễn
• Tính đầy đủ
• Tính phi mâu thuẫn
• Tính độc lập
• Logic vị từ cấp một
• Dạng chuẩn tắc
• Luật suy diễn
• Bài giảng Logic mờ
• Ứng dụng Logic mờ
• Mệnh đề mờ
• Phép toán logic cổ điển
• Khái niệm suy diễn mờ
• Luật suy diễn truyền thống
• Bài giảng Hệ chuyên gia
• Hệ chuyên gia
• Chuẩn hóa các công thức
• Định lý phân giải
• Mệnh đề logic phức hợp
• Toán tử logic
• Phép toán logic với các bit
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Tài liệu logic mệnh đề
• Lý thuyết đồ thị
• Ngành triết học
• Giáo trình Logic học
• Logic chuyên ngành
• Hợp giải trong logic mệnh đề
• Hợp giải trong logic vị từ
• Đề cương chi tiết học phần
• Chương trình đào tạo
• Ngành Công nghệ Dệt may
• Logic học đại cương
• Quy tắc suy luận
• Luật logic mệnh đề
• bài tập điều kiện
• nhập môn logic
• logic học
• bài tập logic
• toán đại số