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

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

105
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nghiêu cứu ứng dụng logic mờ trong tin học và thuật toán tìm đường đi ngắn nhất có cung là trọng số xác định từ đó xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất có cung với số mờ dạng khoảng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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
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ẽ ............................................................................................ Danh mục bảng: ............................................................................................... MỞ ĐẦU ....................................................................................................... 1 Chương I 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ị................................................ 5 1.1.1. Các định nghĩa về đồ thị: ....................................................... 5 1.1.2. Bậc của đồ thị. ....................................................................... 8 1.1.3. Biểu diễn đồ thị bằng ma trận .............................................. 10 1.1.4. Tính liên thông..................................................................... 11 1.1.5. Đường đi Euler và đồ thị Euler ............................................ 16 1.1.6. Bài toán người phát thư Trung Hoa:.................................... 20 1.1.7. Đường đi Hamilton và đồ thị Hamilton ............................... 23 1.2. Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất ................... 28 1.2.1. Bài toán tìm đường đi ngắn nhất: ......................................... 29 1.2.2. Thuật toán Dijkstra: ............................................................. 29 1.2.3. Bài toán áp dụng: ................................................................. 30 1.2.3. Thuật toán Floyd:................................................................. 33
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 2.1. Khái niệm tập mờ .......................................................................... 34 2.1.1. Định nghĩa tập mờ ............................................................... 34 2.1.2. Một số khái niệm của tập mờ ............................................... 36 2.1.3. Các ví dụ về tập mờ ............................................................. 37 2.2. Các phép toán trên tập mờ ............................................................. 39 2.2.1. Các phép toán trên tập hợp. .................................................. 39 2.2.2. Khái niệm hàm liên thuộc .................................................... 40 2.3. Mệnh đề và công thức .................................................................... 41 2.3.1. Khái niệm mệnh đề .............................................................. 41 2.3.2. Các kí hiệu ........................................................................... 41 2.3.3. Các phép toán trên mệnh đề ................................................. 42 2.3.4. Các tính chất ........................................................................ 45 2.4. Suy luận xấp xỉ dựa trên logic mờ.................................................. 45 2.5. Ứng dụng logic mờ xây dựng bài toán tối ưu mờ ........................... 48 2.5.1. Tối ưu mờ ............................................................................ 48 Chương 3 XÂY DỰNG GIẢI THUẬT 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 3.1. Mô hình bài toán ............................................................................ 52 3.2. Ví dụ .............................................................................................. 53 3.3. Bài toán tìm đường đi ngắn nhất có các cung mờ........................... 53 3.3.1. Xây dựng tập mờ ................................................................. 54 3.3.2. Miền xác định của tập mờ: ................................................... 54 3.3.3. Miền tin cậy của tập mờ ....................................................... 55 3.3.4. Miền biên của tập mờ........................................................... 55 3.4. Khái niệm số mờ............................................................................ 55
3.4.1. Định nghĩa số mờ................................................................. 55 3.4.2. Số mờ dạng tam giác:........................................................... 56 3.4.3. Số mờ dạng hình thang: ....................................................... 56 3.5. Một số phương pháp giải quyết bài toán ........................................ 58 3.5.1. Phép toán thực hiện trên số mờ tam giác. ............................. 58 3.6. Ví dụ áp dụng bài toán: ................................................................. 59 Chương 4 CÀI ĐẶT THỬ NGHIỆM 4.1. Một số giao diện của chương trình ................................................. 61 4.1.1. Giao diện chính của chương trình ........................................ 61 4.1.2. Các bước thực hiện chương trình. ........................................ 61 4.1.3. Các chức năng chính của chương trình................................. 61 4.1.3. Các chức năng chính của chương trình................................. 62 4.2. Cài đặt – thử nghiệm ...................................................................... 66 4.3. Đánh giá hiệu quả thuật toán đã xây dựng...................................... 68 KẾT LUẬN VÀ KIẾN NGHỊ .................................................................... 69 1. Kết luận ............................................................................................ 69 2. Kiến nghị .......................................................................................... 70 TÀI LIỆU THAM KHẢO.......................................................................... 71
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
1 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.
2 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.
3 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ế.
4 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.
5 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.
6 * Đị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. 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. v1 v2 v3 v4 v1 v2 v3 v5 v6 v7 v4 v5 v6 Đơ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.
7  Đồ 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. v1 v2 v3 v5 v1 v2 v3 V5 v6 v7 v4 v5 v6 Đồ 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.
8 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| =  deg(v) . vV 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| =  deg(v) +  deg(v) vV1 vV2
9 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. * Đị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. v1 v2 v3 v4 v5 v6 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 đó