Luận văn Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng chuyên ngành: Hệ thống thông tin

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI DỮ LIỆU MỜ DẠNG KHOẢNG Chuyên ngành: Hệ thống thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI DỮ LIỆU MỜ DẠNG KHOẢNG Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUẬT QUÂN SỰ Cán bộ hướng dẫn chính: PGS.TS. Nguyễn Thiện Luận Cán bộ chấm phản biện 1: Cán bộ chấm phản biện 2: Luận văn thạc sĩ được bảo vệ tại: HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ HỌC VIỆN KỸ THUẬT QUÂN SỰ Ngày tháng năm 2011 HỌC VIỆN KỸ THUẬT QUÂN SỰ CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG SAU ĐẠI HỌC Độc lập – Tự do – Hạnh phúc Hà Nội, ngày 12 tháng 05 năm 2011 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: PHAN NHƯ MINH Giới tính: Nam Ngày, tháng, năm sinh: 23/09/1978 Nơi sinh: Vĩnh Phúc Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 I- TÊN ĐỀ TÀI: Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. II- NHIỆM VỤ VÀ NỘI DUNG: Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Đặt ra và giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng III- NGÀY GIAO NHIỆM VỤ: 12/10/2010 IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 05/05/2011 V- CÁN BỘ HƯỚNG DẪN: PGS.TS. Nguyễn Thiện Luận CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN QL CHUYÊN NGÀNH PGS.TS. Nguyễn Thiện Luận Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua. Ngày tháng năm 2011 TRƯỞNG PHÒNG SĐH TRƯỞNG KHOA QL NGÀNH MỤC LỤC Trang Trang phụ bìa Nhiệm vụ luận văn Mục lục Tóm tắt luận văn Danh mục hình vẽ Tóm tắt luận văn Họ và tên học viên: Phan Như Minh Lớp: Hệ thống thông tin Khoá: 21 Cán bộ hướng dẫn: PGS.TS. Nguyễn Thiện Luận Tên đề tài: Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Tóm tắt: Nghiêu cứu ứng dụng logic mờ trong tin học và thuật toán tìm đường đi ngắn nhất có cung là trọng số xác định từ đó xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất có cung với số mờ dạng khoảng. Đưa ra mô phỏng thuật toán giải bài toán tìm đường đi ngắn nhất với trọng số là số mờ dạng khoảng từ giải thuật Dijsktra và lý thuyết mờ quy hoạch tuyến tính dạng khoảng. Kiểm tra hàm liên thuộc. Tìm ra tất cả các đường đi từ các cung mờ. Tìm ra độ dài cung mờ nhỏ nhất giá trị Lmin. Tính ra độ tương tự. Tìm ra đường đi ngắn nhất từ các cung mờ với độ tương tự cao nhất. DANH MỤC HÌNH VẼ Hình 1.1 Đơn đồ thị, giả đồ thị 6 Hình 1.2. Đồ thị có hướng và Đa đồ thị có hướng 7 Hình 1.3. Bậc của đồ thị 8 Hình 1.4. Bậc của đồ thị có hướng 9 Hình 1.5. Biểu diễn đồ thị bằng ma trận liền kề 10 Hình 1.6. Biểu diễn đồ thị bằng ma trận liền kề 10 Hình 1.7. Biểu diễn đồ thị bằng ma trận liên thuộc 11 Hình 1.8. Biểu diễn đường đi sơ cấp 12 Hình 1.9. Biểu diễn đồ thị G và G’ 12 Hình 1.10. Biểu diễn các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s). 13 Hình 1.11. Đồ thị G là liên thông mạnh đồ thị G’ là liên thông yếu 15 Hình 1.12. Biểu diễn Đường đi Euler và đồ thị Euler 17 Hình 1.13. Đồ thị Euler và đồ thị nửa Euler 18 Hình 1.14. Xây dựng đường đi 18 Hình 1.15. Xây dựng đường đi 19 Hình 1.16. Xây dựng đường đi 20 Hình 1.17. Xây dựng đường đi GT và G 22 Hình 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 24 Hình 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 25 Hình 1.20. Đồ thị Hamilton 27 Hình 1. 21. Đồ thị phân đôi 28 Hình 1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị 29 Hình 2.1. Tập mờ 34 Hình 2. 2. Đồ thị hàm liên thuộc của tập mờ 35 Hình 2.3. Miền của tập mờ 37 Hình 2.4. Đồ thị đánh giá 38 Hình 2. 5. Đồ thị đánh giá nhiệt độ 38 Hình 2.6. Ví dụ hàm liên thuộc 41 Bảng 2.7. Mô hình suy diễn xấp sỉ 48 Bảng 1.8. Suy luận xấp xỉ 46 Bảng 1.9. Bảng điều kiện suy diễn xấp sỉ 47 Hình 3.1. Đồ thị G(u,v) có hướng 54 Hình 3.2. Miền biên của tập mờ 56 Hình 3.3. Số mờ dạng tam giác 57 Hình 3.4. Số mờ dạng hình thang 58 Hình 3.4.Biểu diễn số mờ dạng hình thang 58 Hình 3.5.Tìm đường đi ngắn nhất 60 Hình 4.1. Giao diện chính của chương trình 62 Hình 4.2. Các bước thực hiện 62 Hình 4.3. Mô phỏng thuật toán 63 Hình 4.4. Chọn số đỉnh 63 Hình 4.5. Chọn cung đường đi 64 Hình 4.6. Nhập các cung a, b, c và thông báo 64 Hình 4.7. Tìm tất cả các đường đi 65 Hình 4.7. Tính giá trị Lmin 65 Hình 4.8. Bảng độ tương tự 66 Hình 4.9. Bảng thông báo kết quả tìm được 66 Hình 4.10. Chọn đỉnh nhập dữ liệu 67 Hình 4.11. Kết quả kiểm tra xây dựng hàm liên 67 Hình 4.12. Kết quả tất cả các đường đi 68 Hình 4.13. Bảng kết quả tìm Lmin 68 Hình 4.14. Bảng kết quả độ tương tự 68 Hình 4.15. Bảng kết quả đường đi ngắn nhất 68 DANH MỤC BẢNG Bảng 1.1. Kết quả tính toán theo thuật toán Dijkstra 31 Bảng 2.1. Phép phủ định 42 Bảng 2.2. Phép hoặc 43 Bảng 2.3. Phép nhân logic 43 Bảng 2.4. Phép cộng XOR 44 Bảng 2.5. Phép kéo theo 44 Bảng 2.6. Phép tương đương 45 Bảng 2.7. Bảng chân lý 45 Bảng 2.8. Suy luận xấp xỉ 46 Bảng 2.9. Bảng điều kiện suy diễn xấp sỉ 47 Bảng 3.1. Độ tương tự giữa hai số mờ 60 MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các ngành giao thông vận tải, mạng viễn thông, kinh tế, kỹ thuật, công nghệ thông tin và các ngành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính. Một trong những lớp bài toán tối ưu đầu tiên được nghiên cứu là thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định. Bài toán tìm đường đi ngắn nhất là vấn đề quan trọng trong lý thuyết đồ thị, nó đã được nghiên cứu từ lâu và có nhiều ứng dụng trong nhiều ngành khoa học nói chung, khoa học máy tính và hệ thống thông tin nói riêng. Nhiều giải thuật (Dijkstra, Bellman-Ford, Floyd...) đã được phát triển để tìm đường đi ngắn nhất và ngày nay đã được nhiều nhà nghiên cứu nhằm cải tiến xây dựng giải thuật giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Bài toán tìm đường đi ngắn nhất cũng được phát triển rộng rãi và trở thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà tìm đường đi ngắn nhất với các cạnh có trọng số xác định. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong báo cáo này mà tôi sẽ trình bày, người ta giả sử đồ thị là vô hướng các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là: Xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Nhưng câu hỏi cần đặt ra là nếu trọng số đã cho được biểu diễn là một cung mở thuộc khoảng ( a,b) thì sao? Nếu trọng số có khoảng nằm ở đường biên trái thì có thể các phương án là chấp nhận được. Nếu trọng số có khoảng nằm ở đường biên phải thì khó có thể chấp nhận được đó là đường đi tối ưu, do vậy ta chưa thể khẳng định được đó là đường đi ngắn nhất vì giả sử bên cạnh cung đó còn có các cung khác liền kề và có trọng số gần như tương đương thì sao? Nếu áp dụng giải thuật ( Dijkstra, Bellman-Ford, Floyd...) thì rất khó mới có thể tìm ra được theo hướng đi ngắn nhất và tối ưu. Ví dụ : Trong một chuyến đi du lịch từ thành phố A đến thành phố E Vẫn biết rằng : A có thể đi hai đường. A đi qua B rồi lại từ B đi đến D sau đó đến E. A đi qua C rồi lại từ C đi đến D sau đó đến E. Giả sử : Đường đi từ A® B và A® C là một cung được biểu diễn là một cung mờ dạng khoảng thì sao? Để giải quyết bài toán trên: Nhờ ứng dụng logic mờ trong tin học. Bài toán tối ưu bài toán quy hoạch tuyến tính dạng khoảng sẽ giúp ta giải quyết vấn đề này. Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn. Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán tìm đường đi ngắn nhất với các cung khoảng mờ cho đường đi là quá lớn (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng. Trong những năm gần đây nhiều nhà toán học đã chuyển sang nghiên cứu giải quyết bài toán tìm đường đi ngắn nhất có trọng số là các cung mờ dạng khoảng. Trong báo cáo này, tôi sẽ trình bày thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Vì những lý do trên, tôi chọn đề tài “Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng.” làm đề tài nghiên cứu của mình. 2. Mục đích nghiên cứu Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. 3. Phạm vi nghiên cứu Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Dừng lại ở khâu Tìm đường đi ngắn nhất với các dữ liệu về có trọng số dạng khoảng. 4. Phương pháp nghiên cứu Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. Xây dựng phần mềm thử nghiệm. Phân tích đánh giá kết quả để ứng dụng thực tế. Nội dung của luận văn được trình bày trong 4 chương. Chương 1. Lý thuyết đồ thị và thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định Chương 2. Lý thuyết mờ và ứng dụng bài toán quy hoạch tuyến tính dạng khoảng. Chương 3. Xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất biểu diễn cung đường đi là số mờ dạng khoảng. Chương 4. Cài đặt thử nghiệm. Chương 1 LÝ THUYẾT ĐỒ THỊ VÀ THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ TRỌNG SỐ XÁC ĐỊNH 1.1. Khái niệm cơ bản về lý thuyết đồ thị Lý thuyết đồ thị là ngành khoa 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 đưa ra từ thế kỷ thứ 18 bởi nhà toán học Thụy Sĩ tên là Leonard Euler. Ông đã dùng đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Đồ thị được dùng để giải quyết nhiều bài toán khác nhau. Ví dụ dùng đồ thị để xác định xem có thực hiện được một mạch điện trên một bảng điện phẳng không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán: “ Tìm đường đi ngắn nhất” giữa hai thành phố trong một mạng giao thông. 1.1.1. Các định nghĩa về đồ thị: Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh đó. Người ta thường ký hiệu đồ thị G = (V,E), trong đó V là tập hợp các đỉnh (Verterx), E là tập hợp các cạnh (Edge). Người ta phân loại đồ thị theo các đặc tính và số cạnh nối các cặp đỉnh của đồ thị. * Định nghĩa 1: Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. * Định nghĩa 2: Một đa đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị. * Định nghĩa 3: Một giả đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh (không nhất thiết là phân biệt). Với vÎV, nếu (v,v)ÎE thì ta nói có một khuyên tại đỉnh v. v1 v2 v3 v4 v5 v6 v7 v1 v2 v3 v4 v5 v6 Tóm lại, giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể chứa các khuyên và các cạnh bội. Đa đồ thị là loại đồ thị vô hướng có thể chứa cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại đồ thị vô hướng không chứa cạnh bội hoặc các khuyên. Đơn đồ thị Giả đồ thị Hình 1.1 Đơn đồ thị, giả đồ thị * Định nghĩa 4: Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. * Định nghĩa 5: Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các chiều mũi tên trên các cung được gọi là đồ thị vô hướng nền của G. v6 v7 v3 v4 v5 v6 v1 v2 v3 v5 V5 v1 v2 Đồ thị có hướng Đa đồ thị có hướng Hình 1.2. Đồ thị có hướng và Đa đồ thị có hướng Đồ thị ảnh hưởng: Khi nghiên cứu tính cách của một nhóm nguời, ta thấy một số người có thể có ảnh hưởng lên suy nghĩ của những người khác. Đồ thị có hướng được gọi là đồ thị ảnh hưởng có thể dùng để mô hình bài toán này. Mỗi người của nhóm được biểu diễn bằng một đỉnh. Khi một người được biểu diễn bằng đỉnh a có ảnh hưởng lên người được biểu diễn bằng đỉnh b thì có một cung nối từ đỉnh a đến đỉnh b. Thi đấu vòng tròn: Một cuộc thi đấu thể thao trong đó mỗi đội đấu với mỗi đội khác đúng một lần gọi là đấu vòng tròn. Cuộc thi đấu như thế có thể được mô hình bằng một đồ thị có hướng trong đó mỗi đội là một đỉnh. Một cung đi từ đỉnh a đến đỉnh b nếu đội a thắng đội b. Các chương trình máy tính có thể thi hành nhanh hơn bằng cách thi hành đồng thời một số câu lệnh nào đó. Điều quan trọng là không được thực hiện một câu lệnh đòi hỏi kết quả của câu lệnh khác chưa được thực hiện. Sự phụ thuộc của các câu lệnh vào các câu lệnh trước có thể biểu diễn bằng một đồ thị có hướng. Mỗi câu lệnh được biểu diễn bằng một đỉnh và có một cung từ một đỉnh tới một đỉnh khác nếu câu lệnh được biểu diễn bằng đỉnh thứ hai không thể thực hiện được trước khi câu lệnh được biểu diễn bằng đỉnh thứ nhất được thực hiện. Đồ thị này được gọi là đồ thị có ưu tiên trước sau. 1.1.2. Bậc của đồ thị. * Định nghĩa 1: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v)ÎE. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. * Định nghĩa 2: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0. v1 v2 v3 v4 v5 v6 v7 Hình 1.3. Bậc của đồ thị Ta có deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, deg(v5)=4, deg(v6)=1, deg(v7)=2. Đỉnh v4 là đỉnh cô lập và đỉnh v6 là đỉnh treo. * Mệnh đề 1: Cho đồ thị G = (V, E). Khi đó 2|E| = . Chứng minh: Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. Hệ quả 1: Số đỉnh bậc lẻ của một đồ thị là một số chẵn. Chứng minh: Gọi V1 và V2 tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ của đồ thị G = (V, E). Khi đó 2|E| = + Vế trái là một số chẵn và tổng thứ nhất cũng là một số chẵn nên tổng thứ hai là một số chẵn. Vì deg(v) là lẻ với mọi v Î V2 nên |V2| là một số chẵn. Mệnh đề 2: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Chứng minh: Xét đơn đồ thị G=(V,E) có |V|=n. Khi đó phát biểu trên được đưa về bài toán: trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau (xem Thí dụ 6 của 2.2.3). * Định nghĩa 3: Đỉnh u được gọi là nối tới v hay v được gọi là được nối từ u trong đồ thị có hướng G nếu (u,v) là một cung của G. Đỉnh u gọi là đỉnh đầu và đỉnh v gọi là đỉnh cuối của cung này. v1 v2 v3 v4 v5 v6 * Định nghĩa 4: Bậc vào (t.ư. bậc ra) của đỉnh v trong đồ thị có hướng G, ký hiệu degt(v) (t.ư. dego(v)), là số các cung có đỉnh cuối là v. H 1.4. Bậc của đồ thị có hướng degt(v1) = 2, dego(v1) = 3, degt(v2) = 5, dego(v2) = 1, degt(v3) = 2, dego(v3) = 4, degt(v4) = 1, deg0(v4) = 3, degt(v5) = 1, dego(v5) = 0, degt(v6) = 0, dego(v6) = 0. Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo. * Mệnh đề 3: Cho G =(V, E) là một đồ thị có hướng. Khi đó = |E|. Chứng minh: Kết quả có ngay là vì mỗi cung được tính một lần cho đỉnh đầu và một lần cho đỉnh cuối. 1.1.3. Biểu diễn đồ thị bằng ma trận Định nghĩa 1: Cho đồ thị G=(V,E) (vô hướng hoặc có hướng), với V={v1,v2,..., vn}. Ma trận liền kề của G ứng với thứ tự các đỉnh v1,v2,..., vn là ma trận A=, trong đó aij là số cạnh hoặc cung nối từ vi tới vj. Như vậy, ma trận liền kề của một đồ thị vô hướng là ma trận đối xứng, nghĩa là , trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng. Ví dụ 1: Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4 là: v1 v2 v3 v4 Hình 1.5. Biểu diễn đồ thị bằng ma trận liền kề Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4, v5 là: v1 v2 v5 v4 v3 Hình 1.6. Biểu diễn đồ thị bằng ma trận liền kề * Định nghĩa 2: Cho đồ thị vô hướng G=(V,E), v1, v2, ..., vn là các đỉnh và e1, e2, ..., em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận M=, bằng 1 nếu cạnh ej nối với đỉnh vi và bằng 0 nếu cạnh ej không nối với đỉnh vi. Ví dụ 2: Ma trận liên thuộc theo thứ tự các đỉnh v1, v2, v3, v4, v5 và các cạnh e1, e2, e3, e4, e5, e6 là: v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 Hình 1.7. Biểu diễn đồ thị bằng ma trận liên thuộc 1.1.4. Tính liên thông * Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là một số nguyên dương, trong đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) G=(V,E) là một dãy các cạnh (hoặc cung) e1, e2, ..., en của đồ thị sao cho e1=(x0,x1),e2=(x1,x2), ...,en=(xn-1,xn), với x0=u và xn=v. Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh x0, x1, ..., xn. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh. Đường đi hoặc