Tiểu luận Lý thuyết đồ thị - Tìm đường đi ngắn nhất và ứng dụng

Lý thuyết đồ thị là ngành học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại . Những cơ bản của nó dược nhà toán học Thụy Sỹ vĩ đại Leonhard Euler đưa ra từ thế kỷ 18. Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó.Đây là công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh vực khoa học,kỹ thuật , kinh tế, xã hội, ......
Nội dung trích xuất từ tài liệu:
Tiểu luận " Lý thuyết đồ thị - Tìm đường đi ngắn nhất và ứng dụng" 0 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ------ TIỂU LUẬN TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG Giáo viên hướng dẫn: PGS.TSKH.Trần Quốc Chiến Học viên thực hiện: 1.Vũ Văn Khiên ( nhóm 2) 2.Mai Quốc Toản 3.Nguyễn Hoàng Vi 4.Phan Thành Nhất 5.Lưu Thế Vinh Lớp: Phương pháp Toán Sơ Cấp Khoá: 2009 – 2011 Kon Tum, tháng 3 năm 2010. 1 MỤC LỤC Lời nói đầu………………………………………………………………...Trang 01 Phần nội dung...............................................................................................Trang 02 I. Cơ sở lý thuyết…………………………………………….………………Trang 02 II. Bài toán đường đi ngắn nhất và ứng dụng… …………………………….Trang 05 Kết luận…………………………………………………………………....Trang 25 Tài liệu tham khảo……………………………………………………........Trang 26 2 LỜI NÓI ĐẦU Lý thuyết đồ thị là ngành học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó đã được nhà toán học Thụy sĩ vĩ đại Leonhard Euler đưa ra từ thế kỷ 18. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh vực khoa học, kỹ thuật, kinh tế, xã hội,... Môn lý thuyết đồ thị là môn học hấp dẫn, mang tính thực tế cao. Những vấn đề trong môn học như: các bài toán về đường đi, cây, mạng và các bài toán tô màu đã và đang được nhiều người quan tâm, nghiên cứu. Bài toán tìm đường đi ngắn nhất là bài toán quan trọng trong Lý thuyết đồ thị, nó được áp dụng để giải quyết rất nhiều bài toán trong thực tế như điều khiển tối ưu, giao thông vận tải, mạng viễn thông ... . Vì vậy, việc nghiên cứu nó là hết sức cần thiết vì nó có thể giải quyết được nhiều vấn đề khó khăn, phức tạp nảy sinh từ thực tế cuộc sống. Vì lí do đó, nhóm chúng em (nhóm 2) chọn đề tài: ''Đường đi ngắn nhất và ứng dụng'' để viết bài tiểu luận này. 3 PHẦN NỘI DUNG I. CƠ SỞ LÝ THUYẾT 1. Đồ thị vô hướng - Định nghĩa: Đồ thị vô hướng G = (V, E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnh e E được liên kết với một cặp đỉnh v, w (không kể thứ tự). v w - Ví dụ: e 2. Đồ thị có hướng. - Định nghĩa: Đồ thị có hướng G = (V , E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung . Mỗi cung được liên kết với một cặp đỉnh (v, w) có thứ tự. v w e - Ví dụ: - Đường đi, chu trình , tính liên thông  Cho đồ thị G=(V,E). Dãy  từ đỉnh v đến w là dãy các đỉnh và cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dãy  gọi là độ dài của dãy  . Dãy  từ đỉnh v đến đỉnh w độ dài n được biểu diễn như sau   (v, e1 , v1 , e2 , v2 ,..., vn 1 , en , w) 4 trong đó vi(i=1,2…,n-1) là các đỉnh trên dãy và ei(i=1,2…,n) là các cạnh trên dãy liên thông thuộc đỉnh kề trước và sau nó. Các đỉnh và cạnh trên có thể lặp lại. Đường đi từ đỉnh v đến w là dãy từ đỉnh v đến w, trong đó các cạnh không lặp lại. Đường đi sơ cấp : là đường đi không đi qua một đỉnh quá một lần Vòng là dãy có đỉnh đầu và đỉnh cuối trùng nhau. Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau Chu trình sơ cấp : là chu trình không đi qua một đỉnh quá một lần. Dãy có hướng : trong đồ thị có hướng là dãy các đỉnh và cung nối tiếp nhau (e1,e2,…,en) thỏa mãn đỉnh cuối của cung ei là đỉnh đầu của cung ei+1, i=1,..n-1. Đường đi có hướng trong đồ thị có hướng là dãy có hướng, trong đó các cung không lặp lại. Đường đi có hướng sơ cấp là đường đi có hướng không đi qua một đỉnh quá một lần. Vòng có hướng là dãy có hướng có đỉnh đầu và đỉnh cuối trùng nhau. Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau. Chu trình có hướng sơ cấp là chu trình có hướng không đi qua một đỉnh quá một lần . Đồ thị có hướng gọi là liên thông, nếu mọi cặp đỉnh của nó đều có đường đi nối chúng với nhau. Đồ thị có hướng gọi là liên thông mạnh, nếu mọi cặp đỉnh của nó đều có đường đi có hướng nối chúng với nhau. Đồ thị có hướng gọi là liên thông yếu, nếu đồ thị lót (vô hướng) của nó liên thông. Đồ thị có hướng gọi là bán liên thông, nếu với mọi cặp đỉnh (u,v) bao giờ cũng tồn tại đường đi có hướng từ u đến v hoặc từ v đến u. 5  Định lí 1: (i) Trong đồ thị vô hướng mỗi dãy từ đỉnh v đến w chứa đường đi sơ cấp từ v đến w (ii) Trong đồ thị có hướng mỗi dãy có hướng từ đỉnh v đến w chứa đường đi có hướng sơ cấp từ v đến w.  Định lí 2: Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ.  Trọng đồ (có hướng) là đồ thị (có hướng) mà mỗi cạnh (cung) của nó được gán một số. Trọng đồ được biểu diễn bởi G=(V,E,w), trong đó V là các đỉnh ,E là tập các cạnh(cung), và w : E  R là hàm số trên ...