Đang chuẩn bị liên kết để tải về tài liệu:
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 số.Hay 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