Luận văn Thạc sĩ Toán học: Một số bài toán tối ưu trên đồ thị và ứng dụng

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

Thêm vào BST

Báo xấu

28
lượt xem 4
download

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

Một số bài toán tối ưu tổ hợp có thể được mô hình hóa (và giải) một cách rất tự nhiên bằng ngôn ngữ đồ thị. Luận văn này sẽ tập trung vào một lớp bài toán tiêu biểu trong số đó. Tác giả cũng trình bày mô hình toán học và phương pháp giải, sau đó minh họa bằng một ứng dụng thực tiễn.

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 Thạc sĩ Toán học: Một số bài toán tối ưu trên đồ thị và ứng dụng

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Lê Thị Phương Loan MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ: TOÁN HỌC Hà Nội - 2019
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Lê Thị Phương Loan MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ: TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Nguyễn Hoàng Thạch Hà Nội - 2019
LỜI CAM ĐOAN Tôi xin cam đoan những nội dung trong luận văn là do sự tìm hiểu, nghiên cứu của bản thân và sự hướng dẫn tận tình của thầy Nguyễn Hoàng Thạch. Các kết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kỳ một hội đồng bảo vệ luận văn thạc sĩ nào và cũng chưa được công bố trên bất kỳ một phương tiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan trên. Hà Nội, ngày 30 tháng 10 năm 2019 Người cam đoan Lê Thị Phương Loan
LỜI CẢM ƠN Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của TS Nguyễn Hoàng Thạch. Nhân dịp này em xin bày tỏ lòng biết ơn thầy về sự hướng dẫn hiệu quả cùng những kinh nghiệm trong suốt quá trình học tập, nghiên cứu và hoàn thành luận văn. Tôi xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi của Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam trong quá trình tôi thực hiện luận văn. Tôi xin chân thành cảm ơn Viện Toán học và các thầy cô anh chị trong phòng Cơ sở Toán học của Tin học đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu. Xin cảm ơn các bạn học viên chuyên ngành Toán ứng dụng khoá 2017- 2019 đã giúp đỡ, động viên tôi trong quá trình thực hiện luận văn. Cuối cùng, luận văn chắc chắn sẽ không tránh khỏi những khiếm khuyết. Vì vậy tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo và các bạn học viên để luận văn này được hoàn chỉnh hơn.
1 MỤC LỤC Lời cam đoan Lời cảm ơn Mục lục 1 Lời nói đầu 3 Danh sách bảng 5 Danh sách hình vẽ 6 1 KIẾN THỨC CHUẨN BỊ 7 1.1 CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ . . . . . . . . . . . . . 7 1.1.1 Các định nghĩa và thí dụ . . . . . . . . . . . . . . . . . . . 7 1.1.2 Biểu diễn đồ thị . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 ĐƯỜNG ĐI VÀ TÍNH LIÊN THÔNG . . . . . . . . . . . . . . 15 1.2.1 Đường đi và chu trình . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Tính liên thông . . . . . . . . . . . . . . . . . . . . . . . . 17 2 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ 19 2.1 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT . . . . . . . . . . . 20 2.2 THUẬT TOÁN DIJKSTRA . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . . 23 2.2.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 27
2 2.2.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 THUẬT TOÁN BELLMAN-FORD . . . . . . . . . . . . . . . . 28 2.3.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . . 30 2.3.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 31 2.3.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4 SO SÁNH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3 ỨNG DỤNG: BÀI TOÁN LẬP KẾ HOẠCH 34 3.1 MÔ TẢ BÀI TOÁN . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 MÔ HÌNH ĐỒ THỊ . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Phương pháp thế năng . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Phương pháp PERT . . . . . . . . . . . . . . . . . . . . . 42 4 KẾT LUẬN VÀ KIẾN NGHỊ 46 4.1 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2 KIẾN NGHỊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 TÀI LIỆU THAM KHẢO 47
3 LỜI NÓI ĐẦU Trong khi tối ưu luôn là một trong những lĩnh vực quan trọng và có lịch sử lâu đời của toán học ứng dụng, thì tối ưu tổ hợp lại là một nhánh khá "trẻ" chỉ bắt đầu phát triển mạnh từ khoảng đầu thế kỷ 20, do nhu cầu phát sinh từ một nền sản xuất hiện đại, quy mô lớn. Các bài toán tối ưu tổ hợp hiện diện khắp nơi trong cuộc sống hiện đại, từ việc lên kế hoạch, tổ chức các dây chuyền sản xuất, kho bãi đến những khía cạnh đời thường gần gũi hơn như giao thông đô thị, sắp xếp thời khóa biểu, . . . Cũng được phát triển mạnh trong thế kỷ 20 là lý thuyết đồ thị. Các mô hình đồ thị cho phép thể hiện một cách trực quan các tập hợp các đối tượng rời rạc và các mối quan hệ giữa chúng. Ban đầu gắn liền với khoa học máy tính, hiện nay lý thuyết đồ thị bản thân nó đã trở thành một lĩnh vực toán học riêng và vẫn phát triển mạnh. Các mô hình đồ thị có thể được tìm thấy trong thiết kế máy tính và phần mềm, trong mạng viễn thông, trong sinh học, trong các nghiên cứu về mạng xã hội, trong kinh tế, . . . Một số bài toán tối ưu tổ hợp có thể được mô hình hóa (và giải) một cách rất tự nhiên bằng ngôn ngữ đồ thị. Luận văn này sẽ tập trung vào một lớp bài toán tiêu biểu trong số đó. Trong khuôn khổ luận văn, tôi sẽ trình bày mô hình toán học và phương pháp giải, sau đó minh họa bằng một ứng dụng thực tiễn. Luận văn được chia thành ba chương: Chương 1 Kiến thức chuẩn bị Trình bày các khái niệm, tính chất, mệnh đề, các nội dung cơ bản để phục vụ cho nội dung trong luận văn.
4 Chương 2 Bài toán tìm đường đi ngắn nhất trên đồ thị Đây là phần chính của luận văn. Trong chương này sẽ nêu ra bài toán, phương pháp giải, giả mã và chứng minh tính đúng đắn của các thuật toán. Chương 3 Ứng dụng: Bài toán lập kế hoạch Nêu ra một mô hình thực tiễn, và cách áp dụng từ bài toán tìm đường đi ngắn nhất bên trên để giải quyết mô hình đó. Các khái niệm, nội dung trong luận văn được tham khảo từ các tài liệu [1], [2], [3], [4], [5], [6] và viết lại theo ý hiểu của tác giả.
5 Danh sách bảng 3.1 Ví dụ mô hình dự án . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Danh sách hình vẽ 1.1 Đơn đồ thị vô hướng(a) và có hướng(b) . . . . . . . . . . . . . . . . 9 1.2 Đơn đồ thị vô hướng có trọng số(a) và có hướng có trọng số (b) . . . . 9 1.3 Hai phép biểu diễn đồ thị vô hướng trong hình 1.1a . . . . . . . . . . 12 1.4 Hai phép biểu diễn đồ thị có hướng trong hình 1.1b . . . . . . . . . . 13 1.5 Hai phép biểu diễn đồ thị có trọng số trong hình 1.2a . . . . . . . . . 14 1.6 Ví dụ về một đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . 16 2.1 Minh họa cho chứng minh ý 1. . . . . . . . . . . . . . . . . . . . . 23 2.2 Minh họa cho chứng minh ý 2 trường hợp 1. . . . . . . . . . . . . . 24 2.3 Minh họa cho chứng minh ý 2 trường hợp 2. . . . . . . . . . . . . . 25 2.4 Minh họa cho chứng minh ý 2 trường hợp 3. . . . . . . . . . . . . . 26 2.5 Thực thi thuật toán Dijkstra . . . . . . . . . . . . . . . . . . . . . 27 2.6 Minh họa cho chứng minh trường hợp 2 . . . . . . . . . . . . . . . . 31 2.7 Thực thi thuật toán Bellman-Ford . . . . . . . . . . . . . . . . . . . 32 3.1 Đồ thị Conjunctive . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Biểu diễn đồ thị của bảng 3.1 bằng phương pháp thế năng . . . . . . . 39 3.3 Biểu diễn kết quả bằng phương pháp thế năng . . . . . . . . . . . . . 42 3.4 Biểu diễn đồ thị của bảng 3.1 bằng phương pháp PERT . . . . . . . . 44 3.5 Biểu diễn kết quả bằng phương pháp PERT . . . . . . . . . . . . . . 44 3.6 Biểu diễn của bài toán bằng biểu đồ Gantt . . . . . . . . . . . . . . 45
7 CHƯƠNG 1 KIẾN THỨC CHUẨN BỊ 1.1 CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ Các khái niệm, nội dung được trình bày sau đây nhằm phục vụ cho nội dung trong khuôn khổ luận văn. Để tìm hiểu thêm các kiến thức về đồ thị, độc giả có thể tham khảo các tài liệu trong mục tài liệu tham khảo. 1.1.1 Các định nghĩa và thí dụ Định nghĩa 1.1.1. Một đồ thị vô hướng G = (V, E) được xác định bởi: • V là một tập khác rỗng gồm các đỉnh, • E là tập các cặp đỉnh (không thứ tự), được gọi là cạnh. Hai đỉnh thuộc một cạnh được gọi là các đầu mút của cạnh đó. Trong khuôn khổ luận văn, ta xét các đồ thị hữu hạn, tức là có tập hợp đỉnh hữu hạn.
8 Nếu giữa hai đỉnh bất kỳ có không quá một cạnh thì G được gọi là một đồ thị đơn. Định nghĩa 1.1.2. Một đồ thị có hướng G = (V, E) được xác định bởi: • V là một tập khác rỗng gồm các đỉnh, • E là một tập gồm các cạnh có hướng (hay cung), mỗi cạnh đi từ một đỉnh đầu tới một đỉnh cuối. Nếu với hai đỉnh u, v bất kỳ, có nhiều nhất một cạnh đi từ u tới v thì G được gọi là một đồ thị đơn có hướng. Nếu (a, b) ∈ E thì (a, b) được gọi là cạnh (cung) của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b. Ví dụ 1.1.1. a. Đồ thị vô hướng G = (V, E) trong đó: V = {a, b, c, d, e, f }, E = {(a, b), (a, e), (b, e), (c, d)} (Hình 1.1.a) b. Đồ thị có hướng G = (V, E) trong đó: V = {a, b, c, d, e, f }, E = {(a, b), (b, e), (c, d), (d, c), (e, a), (f, f )} (Hình 1.1b) Đồ thị G = (V, E) được gọi là đồ thị có trọng số (hay trọng đồ), nếu mỗi cạnh có một trọng số kết hợp, thường được cung cấp bởi một hàm trọng số w : E → R. Ví dụ 1.1.2. a. Đồ thị vô hướng G = (V, E) trong đó: V = {a, b, c, d, e, f }, E = {(a, b), (a, e), (b, e), (c, d)}
9 (a) Đơn đồ thị vô hướng (b) Đơn đồ thị có hướng Hình 1.1: Đơn đồ thị vô hướng(a) và có hướng(b) và w(a, b) = 3, w(a, e) = 4, w(b, e) = 4.5, w(c, d) = 6 (Hình 1.2a) b. Đồ thị có hướng G = (V, E) trong đó: V = {a, b, c, d, e, f }, E = {(a, b), (b, e), (c, d), (d, c), (e, a), (f, f )} w(a, b) = 1.5, w(b, e) = 2, w(c, d) = 5,w(d, c) = 3.2, w(e, a) = 4, w(f, f ) = 8 (Hình 1.2b) (a) (b) Hình 1.2: Đơn đồ thị vô hướng có trọng số(a) và có hướng có trọng số (b) Định nghĩa 1.1.3. Một đồ thị con của đồ thị G là một đồ thị H = (W, F ) sao cho W ⊂ V, F ⊂ E. Tiếp sau đây là một số thuật ngữ cơ bản của lý thuyết đồ thị.
10 Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và các cạnh của đồ thị vô hướng. Nếu (u, v) là một cạnh nằm trong đồ thị G = (V, E) ta nói đỉnh v kề với đỉnh u. Trong đồ thị vô hướng, quan hệ kề là đối xứng. Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v). Để biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta dựa vào định nghĩa sau: Định nghĩa 1.1.4. Bậc của một đỉnh trong một đồ thị vô hướng là số lượng các cạnh liên thuộc trên nó. Ký hiệu: deg(v). Đỉnh v được gọi là đỉnh cô lập nếu deg(v) = 0. Đỉnh v được gọi là đỉnh treo nếu deg(v) = 1. Ta xét các thuật ngữ tương tự cho đồ thị có hướng Tương tự với đồ thị vô hướng, ta có khái niệm về quan hệ kề đối với đồ thị có hướng. Và trong một đồ thị có hướng, quan hệ kề không nhất thiết đối xứng. Nếu v kề với u trong một đồ thị có hướng, đôi lúc ta viết u → v. Nếu (u, v) là một cạnh trong một đồ thị G = (V, E) , ta nói rằng (u, v) liên thuộc từ (incident from) đỉnh u và liên thuộc đến (incident to) đỉnh v. Định nghĩa 1.1.5. Trong một đồ thị có hướng, bậc đi ra của một đỉnh là số lượng cạnh rời khỏi nó, bậc đi vào của một đỉnh là số lượng cạnh nhập vào nó. Bậc của một đỉnh trong đồ thị có hướng là bậc đi ra cộng bậc đi vào của nó. Hay ta còn có thể viết dưới dạng sau: Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V . Kí hiệu:
11 d+ (v) = {x ∈ V |(v, x) ∈ E} d− (v) = {y ∈ V |(y, v) ∈ E} Khi đó |d+ (v)| được gọi là bậc đi ra, |d− (v)| được gọi là bậc đi vào của v. d(v) = d+ (v) + d− (v) Đỉnh v được gọi là đỉnh cô lập nếu d+ (v) + d− (v) = 0. Đỉnh v được gọi là đỉnh treo nếu d+ (v) + d− (v) = 1. 1.1.2 Biểu diễn đồ thị Biểu diễn đồ thị trên mặt phẳng là một biểu diễn cho ta phép nhìn nhận đối tượng này một cách khá trực quan. Tuy nhiên, ta vẫn cần tới các biểu diễn khác của đồ thị để đáp ứng các đòi hỏi khác nhau của các ứng dụng. Và có hai cách thường dùng để biểu diễn một đồ thị G = (V, E) : sử dụng một danh sách kề hoặc sử dụng một ma trận kề. Phép biểu diễn danh sách kề cung cấp một cách gắn gọn để biểu diễn các đồ thị thưa - là những đồ thị mà |E| nhỏ hơn nhiều so với |V |2 . Phép biểu diễn ma trận kề được ưa dùng khi đồ thị là trù mật -|E| sát với |V |2 hoặc khi ta cần nhanh chóng biết một cạnh nối hai đỉnh đã cho hay không. Biểu diễn đồ thị bằng danh sách kề Trong khoa học máy tính, danh sách kề là một cấu trúc dữ liệu gắn bó chặt chẽ với việc biểu diễn đồ thị. Phép biểu diễn danh sách kề của một đồ thị G = (V, E) gồm một mảng Adj có độ lớn là |V |, ứng với các đỉnh của V . Với mỗi đỉnh u của đồ thị, ta cho tương ứng với nó một danh sách các đỉnh kề với u, nghĩa là sao cho có cạnh
12 (u, v) ∈ E. Nếu G là một đồ thị có hướng thì tổng các chiều dài của tất cả các danh sách kề là |E|, bởi mỗi cạnh (u, v) thể hiện v xuất hiện trong Adj[u]. Nếu G là một đồ thị vô hướng thì tổng các chiều dài của tất danh sách kề là 2|E|, vì nếu (u, v) là một cạnh vô hướng thì u xuất hiện trong danh sách kề của v và ngược lại. Danh sách kề có thể thay đổi để biểu diễn đồ thị có trọng số. Khi đó, trọng số w(u, v) của cạnh (u, v) được lưu trữ với đỉnh v trong danh sách kề của u. Một nhược điểm của phép biểu diễn danh sách kề đó là để xác định xem một cạnh đã cho (u, v) có tồn tại trong đồ thị hay không, ta không còn cách nào nhanh hơn là tìm kiếm v trong danh sách kề Adj[u].Có thể khắc phục nhược điểm này bằng một phép biểu diễn ma trận kề của đồ thị, để đổi lại, ta phải dùng nhiều bộ nhớ hơn. Ví dụ 1.1.3. Hai phép biểu diễn đồ thị vô hướng Hình 1.1a. (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.3: Hai phép biểu diễn đồ thị vô hướng trong hình 1.1a Ví dụ 1.1.4. Hai phép biểu diễn của đồ thị có hướng Hình 1.1b
13 (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.4: Hai phép biểu diễn đồ thị có hướng trong hình 1.1b Biểu diễn đồ thị bằng ma trận kề Xét đơn đồ thị vô hướng G = (V, E) với tập đỉnh V = {v1 , v2 , . . . , vn }. Khi đó ma trận kề của đồ thị G là ma trận    a11 a12 . . . a1n     a21 a22 . . . a2n  A = (aij )n×n =    . . .      an1 an2 . . . ann trong đó:   1, nếu (vi , vj ) ∈ E  aij =  0, nếu (vi , vj ) ∈  /E
14 Dễ thấy rằng ma trận kề A của đồ thị có hướng G hoàn toàn xác định G. Vì vậy, ma trận kề được coi là một biểu diễn của G. Ta có một số tính chất: Tính chất 1.1.1. i. Ma trận kề của đồ thị vô hướng là một ma trận đối xứng. ii. Tổng các phần tử trên dòng i (cột j) bằng bậc của đỉnh tương ứng. Cũng tương tự phép biểu diễn danh sách kề của một đồ thị, phép biểu diễn ma trận kề có thể được dùng cho các đồ thị có trọng số. Khi đó, nếu G là một đồ thị có trọng số, ta có ma trận A = (aij )n×n trong đó:   w(vi , vj ), nếu (vi , vj ) ∈ E  aij =  0,  nếu (vi , vj ) ∈ /E Ví dụ 1.1.5. Ví dụ về danh sách kề và ma trận kề có trọng số cho đồ thị trong ví dụ 1.2a. (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.5: Hai phép biểu diễn đồ thị có trọng số trong hình 1.2a
15 1.2 ĐƯỜNG ĐI VÀ TÍNH LIÊN THÔNG 1.2.1 Đường đi và chu trình Xét một đồ thị vô hướng Giả sử G = (V, E) là một đồ thị vô hướng. Một đường đi trong G là một dãy v0 e1 v1 e2 v2 . . . en vn sao cho: + Với mọi i = 0, 1, 2, .., n, vi ∈ V , + Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ). Khi đó, n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối của đường đi trên. Một chu trình là một đường có điểm đầu và điểm cuối trùng nhau. Một đường đi đơn (chu trình đơn) là một đường đi (chu trình) không đi qua cạnh nào quá một lần. Xét một đồ thị có hướng Hoàn toàn tương tự, ta có các định nghĩa với đồ thị có hướng. Giả sử G = (V, E) là một đồ thị có hướng. Một đường đi trong G là một dãy v0 e1 v1 e2 v2 . . . en vn sao cho: + Với mọi i = 0, 1, 2, .., n, vi ∈ V , + Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1 , vi ). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối của đường có hướng trên. Một đường đi đơn (chu trình đơn) là một
16 đường đi (chu trình) không đi qua cạnh nào quá một lần. Trong trường hợp đồ thị có hướng, xét một đường đi v0 e1 v1 e2 v2 . . . en vn , mỗi cạnh ei đều có đỉnh đầu là đỉnh đứng trước và đỉnh cuối là đỉnh đứng sau ei trong dãy, tức là nó được xác định bởi chính hai đỉnh đó. Vì vậy, khi đồ thị không có cạnh bội, ta biểu diễn đường đi bằng dãy các đỉnh, bỏ qua các cạnh, và đơn giản gọi dãy các đỉnh v0 v1 v2 . . . vn của G là đường đi trong G nếu với mọi i = 0, 1, ...., n − 1, (vi , vi+1 ) là một cạnh của G. Ví dụ 1.2.1. Giả sử G = (V, E) là đồ thị có hướng như hình 1.6. Khi đó: a. a → b → f → e → b → c là một đường đi có hướng với đỉnh đầu là a, đỉnh cuối là c với độ dài bằng 5. b. a → b → e → d → c → b → e → f là một đường đi vô hướng với đỉnh đầu là a, đỉnh cuối là f với độ dài bằng 7. c. b → f → e → b là một đường đi có hướng khép kín. d. b → e → d → c → b là một đường đi vô hướng khép kín. Hình 1.6: Ví dụ về một đồ thị có hướng