TAILIEUCHUNG - giáo trình lý thuyết đồ thị

Tài liệu nhỏ này được biên soạn nhân dịp tôi và các bạn làm đề tài Toán rời rạc. Nội dung chủ yếu của tài liệu này viết về lí thuyết đồ thị, và đi sâu về đồ thị Halmilton. Xin nói rằng, tôi không lấy làm hãnh diện khi viết xong tài liệu này. Đây chỉ là một chút sự góp nhặt nhỏ bé từ các tài liệu khác. | Biên soạn Lê Đình Huy T A r -4- Ầ Lời nói đầu Tài liệu nhỏ này được biên soạn nhân dịp tôi và các bạn làm đề tài Toán rời rạc. Nội dung chủ yếu của tài liệu này viết về lí thuyết đồ thị và đi sâu về đồ thị Halmilton. Xin nói rằng tôi không lấy làm hãnh diện khi viết xong tài liệu này. Đây chỉ là một chút sự góp nhặt nhỏ bé từ các tài liệu khác chủ yếu là Đại cương về toán học hữu hạn - Hoàng Chúng mà được tôi rút ra để tổng hợp lại những gì đã được học. Tất nhiên một mình tôi thì không thể biên soạn được tài liệu này. Trong quá trình biên soạn xin chân thành cám ơn nhóm đề tài toán rời rạc của lớp tôi gồm các bạn Cù Minh Khương Phạm Thị Thu Hà Phan Phương Dung Nguyễn Thi Thùy Dung Phạm Thị Nâu. Cám ơn các thầy cô đã đón nhận. Chắc chắn tài liệu sẽ có những sai sót không tránh khỏi hi vọng được thầy cô bạn đọc đón nhận và góp ý. Mùa xuân Canh Dần TP Hồ Chí Minh Lê Đình Huy 1 Biên soạn Lê Đình Huy r l . 1 Ầ f i 1 Sơ lược vê Graph I Graph Đồ thị Hai chữ đồ thị vẫn thường xuyên xuất hiện trong đời sống toán học và cả trong đời sống hàng ngày. Trong các giờ toán chúng ta từng nói tới đồ thị của các hàm trong các công sở các nhân viên phải lập các biểu đồ theo dõi lượng tiêu thụ điện . Nói chung khái niệm đồ thị là một khái niệm khá quen thuộc với chúng ta nhằm biểu diễn tương quan qua lại giữa 2 hoặc nhiêu đối tượng toán học khác nhau. Ở đây khái niệm đồ thị vẫ được dùng theo nghĩa đó nhưng nó mang tính trừu tượng hơn. Lí thuyết đồ thị tiếng Anh và tiếng Đức đọc là graph nghiên cứu những tính chất toán học những quan hệ mà không phụ thuộc vào bản chất riêng của những mối quan hệ này. Để tránh bị hiểu nhầm là đồ thị của hàm số trong tài liệu này chúng tôi sẽ dùng thuật ngữ graph . Một graph có thể hiểu đơn giản là một hệ thống các đỉnh và các cạnh nối các đỉnh này với nhau. Một graph G được xác định bởi _ Tập hợp V những phần tử gọi là đỉnh của G. _ Tập hợp E những phần tử gọi là cạnh của G. Giả thuyết rằng V E là các tập hữu hạn V không rỗng. Kí hiệu G V E hay V

• Toán học
• bài giảng 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ị
• lý thuyết đồ thị
• 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ị
• Đạ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ị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• 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
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng