Sáng kiến kinh nghiệm THPT: Phát triển năng lực học sinh thông qua thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

29
lượt xem 1
download

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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là chỉ ra hướng vận dụng DFS và BFS trong lý thuyết đồ thị vào giải các bài toán và tìm ra các biện pháp để giúp học sinh trung học phổ thông hình thành và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập lập trình.

Chủ đề:

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

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Phát triển năng lực học sinh thông qua thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)

PHÁT TRIỂN NĂNG LỰC HỌC SINH THÔNG QUA THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS) VÀ TÌM KIẾM THEO CHIỀU RỘNG (BFS) A. MỞ ĐẦU 1. Lý do chọn đề tài. Đổi mới phương pháp dạy học là một nhiệm vụ quan trọng của ngành giáo dục nhằm nâng cao chất lượng đào tạo, góp phần thực hiện công nghiệp hoá hiện đại hóa đất nước. Lý thuyết đồ thị (trong Tin học) là một chuyên ngành quan trọng đã được ứng dụng vào nhiều ngành khoa học, kỹ thuật khác nhau vì lý thuyết đồ thị là phương pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa các mối quan hệ của các đối tượng được nghiên cứu. Vận dụng lý thuyết đồ thị trong dạy học sinh để mô hình hóa các mối quan hệ chuyển thành phương pháp dạy học đặc thù sẽ nâng cao được hiệu quả dạy học thúc đẩy quá trình tự học tự nghiên cứu của học sinh theo hướng tối ưu hóa đặc biệt nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng tạo của học sinh. Việc cung cấp thêm một phương pháp giải bài tập cho học sinh Tin học 11 tham gia học lập trình là một nhu cầu cần thiết. Xuất phát từ những lý do trên tôi lựa chọn đề tài: “Phát triển năng lực học sinh thông qua thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)”. 2. Mục tiêu, nhiệm vụ của đề tài. - Mục tiêu của đề tài: Chỉ ra hướng vận dụng DFS và BFS trong lý thuyết đồ thị vào giải các bài toán và tìm ra các biện pháp để giúp học sinh trung học phổ thông hình thành và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập lập trình. - Nhiệm vụ của đề tài: - Tìm hiểu những nội dung cơ bản của lý thuyết đồ thị được trang bị cho học sinh Tin học. - Chỉ ra hệ thống bài tập có thể vận dụng lý thuyết đồ thị để giải. - Chỉ ra được những dấu hiệu cụ thể để nhận dạng “Bài toán” có thể khai thác lý thuyết đồ thị trong quá trình giải bài toán. - Chỉ ra các phương án vận dụng lý thuyết đồ thị vào giải toán. 1
+ Tiếp cận chương trình mới môn Tin học 2018 phần đồ thị có trong mạch kiến thức CS 3. Giả thuyết khoa học. Nếu ta có các phương pháp giúp học sinh Tin học 11 vận dụng kiến thức về lý thuyết đồ thị vào giải các bài toán thì sẽ giúp học sinh giải quyết được một số lớp bài toán góp phần nâng cao chất lượng dạy học cũng như phát triển được năng lực của học sinh. 4. Phương pháp nghiên cứu. a. Nghiên cứu lý luận. - Nghiên cứu các văn bản, tài liệu chỉ đạo của Bộ GD & ĐT liên quan đến đổi mới phương pháp dạy học, đổi mới ra đề kiểm tra, danh mục thiết bị dạy học Tin học. - SGK, phân phối chương trình, sách giáo viên, chuẩn của bộ môn Tin ở trung học phổ thông, sách nâng cao, sách chuyên đề. - Các tài liệu về lý thuyết đồ thị và những ứng dụng của nó trong thực tiễn cuộc sống và trong dạy học. - Các công trình nghiên cứu các vấn đề liên quan trực tiếp đến phương pháp đồ thị. b. Thực nghiệm sư phạm. - Chỉ ra cho học sinh các dấu hiệu "nhận dạng" và cách thức vận dụng lý thuyết đồ thị vào giải bài tập. - Biên soạn hệ thống bài tập luyện tập cho học sinh và một số đề bài kiểm tra để đánh giá khả năng vận dụng lý thuyết đồ thị vào giải các bài toán. - Tiến hành thực nghiệm và đánh giá kết quả thực nghiệm. 2
B. NỘI DUNG I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ. 1. Đồ thị và tầm quan trọng. Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng hiện đại. Các bài toán đặt ra nếu được đưa về lý thuyết đồ thị để giải sẽ tiết kiệm được rất nhiều thời gian, ý tưởng thuật toán sẽ rõ ràng, chương trình ngắn gọn và dễ hiểu. Nếu hiểu và biết vận dụng tốt lý thuyết đồ thị sẽ giúp chúng ta giải quyết được rất nhiều bài toán đặt ra trong thực tế (xem ở phần giải quyết vấn đề). Khoa học và kỹ thuật phát triển làm xuất hiện hàng loạt bài toán trong thực tiển được quy về mô hình đồ thị. 1.1. Định nghĩa đồ thị: Cho tập hợp X khác rỗng, E là tập hợp các cặp phần tử của X được sắp xếp thứ tự hoặc không sắp thứ tự. Cặp (X, E) được gọi là một đồ thị. Kí hiệu đồ thị là G = (X, E) hoặc đôi khi nếu không gây nhầm lẫn kí hiệu tắt là G. 1.2. Một số khái nhiệm. - Các phần tử thuộc tập X gọi là đỉnh của đồ thị G. - Cho 2 đỉnh x1, x2X, nếu e = (x1,x2)E là cặp sắp thứ tự thì e được gọi là một cung của đồ thị, hoặc nếu e là cặp không sắp thứ tự thì e được gọi là một cạnh của đồ thị. - e = (x1,x2) là cung thì x1 là đỉnh đầu của cung, x2 là đỉnh cuối của cung e. - e = (x1,x2) là cạnh thì x1 và x2 là 2 đỉnh kề của cạnh e hoặc 2 đỉnh thuộc cạnh e. - Hai đỉnh x1 và x2 (x1 ≠ x2) của đồ thị được gọi là 2 đỉnh kề nhau nếu chúng là 2 đầu của một cạnh hoặc một cung. - Hai cạnh a, b (hoặc 2 cung a, b) gọi là 2 cạnh kề nhau (hoặc 2 cung kề nhau) nếu chúng có một đỉnh chung. - Khuyên là cạnh (hoặc cung) có 2 đầu trùng nhau. - Đỉnh treo là đỉnh thuộc duy nhất một cạnh hoặc cung. - Đỉnh cô lập là đỉnh không thuộc cạnh hoặc cung nào. 3
1.3. Phân loại đồ thị. Cho đồ thị G = (X, E), nếu E chỉ gồm các cạnh thì G là đồ thị vô hương. Nếu E chỉ gồm các cung thì đồ thị G là đồ thị có hướng. Nếu E gồm cả cạnh và cung thì G là đồ thị hỗn hợp. Đa đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đa đồ thị khi và chỉ khi nó là đồ thị không khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng ít nhất 2 cạnh (hoặc 2 cung nối theo thứ tự của cặp đỉnh). Đơn đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đơn đồ thị khi và chỉ khi nó là đồ thị không khuyên và mỗi cặp đỉnh được nối với nhau không quá một cạnh (hoặc cung). 2. Biểu diễn đồ thị. Biểu diễn đồ thị trên máy tính theo cấu trúc nào thì sẽ có giải thuật theo cấu trúc đó. Với học sinh Tin học 11, biểu diễn bằng ma trận (mảng 2 chiều) là dễ hiểu và phù hợp nhất. Cách khai thác trên mảng 2 chiều đã được học sinh làm nhiều ở SGK Tin học 11. Các cách biểu diễn đồ thị: 2.1. Biểu diễn bằng hình học. Minh họa cách biểu diễn ` Đ.Nai Thanh Hoá An Giang Hà Tây TP. HCM Long An Hà Nội Khánh Hoà Nam Định Huế Hình 1: Đơn đồ thị, vô hướng 4
` 2 2 1 4 1 4 6 3 5 3 5 Hình 2: Đa đồ thị, vô hướng Hình 3: Đa đồ thị, có hướng 2.2. Biểu diễn đồ thị bằng ma trận liên thuộc (Ma trận kề). Giả sử đồ thị G = (X, E) có tập đỉnh X = (x1,x2, x3,…,xn), tập cạnh (hoặc cung) là E. Ta xây dựng ma trận vuông A cấp n sao cho  i,j, 1i,jn có: 1 2 3 Ma trận A là ma trận liên thuộc (ma trận kề) 4 5 Nhận xét : Nếu G là độ thị vô hướng thì Hình 4: Đồ thị và ma trận kề Ma trận A sẽ đối xứng qua đường chéo chính, Aij = Aji  i,j, 1i,jn. 2.3. Biểu diễn bằng ma trận trọng số. Trong nhiều bài toán về đồ thị, mỗi cạnh (hoặc cung) e = (xi, xj) của đồ thị thường được gắn với một số c (e) gọi là trọng số của cạnh (hoặc cung) e. Khi đó thường xây dựng ma trận vuông cấp n là ma trận C có mỗi phần tử C[i,j] = c(e) nếu tồn tại cạnh (hoặc cung) e = (xi, xj), ngược lại khi không có cạnh nối xi với xj thì C[i,j] =  (kí hiệu  là giá trị không xác định). Trong nhiều trường hợp, ngậm định C[i,i] = 0 với mọi đỉnh i trong đồ thị không khuyên. 3. Tìm kiếm trên đồ thị và tìm thành phần liên thông trên đồ thị. Hiểu được bản chất của các phép tìm kiếm và tìm thành phần liên thông trên đồ thị chúng ta có thể giải quyết được rất nhiều các dạng bài toán đặt ra (thể hiện ở 5
phần áp dụng). Qua tìm kiếm trên đồ thị chúng ta có thể kết hợp tính toán, thống kê, sắp xếp và tổng hợp được các kết quả. 3.1. Một số khái niệm. Định nghĩa 1: Đường đi có độ dài k (k nguyên dương) từ đỉnh u tới đỉnh v trên đồ thị vô hướng G = (V, E) là dãy các đỉnh u = x0, x1, x2, x3,…, xk = v mà các cạnh (xi, xi+1)E, i=0,1,2,…,k-1. Đường đi này còn có thể biểu diễn dưới dạng dãy các cạnh: (x0,x1), (x1,x2),….,(xk-1,xk). Đỉnh u gọi là đỉnh đầu (xuất phát), đỉnh v gọi là đỉnh cuối (đỉnh đích) của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là một chu trình. Đường đi hay chu trình được gọi là đơn nếu không có cạnh nào bị lặp lại. Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại) Định nghĩa 2: Đường đi có độ dài k (k nguyên dương) từ đỉnh u tới đỉnh v trên đồ thị có hướng G = (V, E) là dãy các đỉnh u = x0, x1, x2, x3,…, xk = v mà các cung (xi, xi+1)E, i = 0,1,2,…,k-1. Đường đi này còn có thể biểu diễn dưới dạng dãy các cung: (x0,x1), (x1,x2),….,(xk-1,xk). Đỉnh u gọi là đỉnh đầu (xuất phát), đỉnh v gọi là đỉnh cuối (đỉnh đích) của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là một chu trình (mạch vòng). Đường đi hay chu trình được gọi là đơn nếu không có cung nào bị lặp lại. Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại) Định nghĩa 3: Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa 2 đỉnh bất kỳ của nó. Định nghĩa 4: Cho đồ thị vô hướng G = (V, E) và đồ thị con của G là đồ thị G‟ = (V‟, E‟). Đồ thị G‟ được gọi là một vùng liên thông (hoặc thành phần liên thông) của G nếu: + G‟ liên thông; + Không tồn tại đường đi nào từ một đỉnh thuộc G‟ tới 1 đỉnh không thuộc G‟ (nói cách khác là bảo đảm tính tối đại của liên thông trong G‟). 6
Ví dụ: Trong hình 5 xét 2 đồ thị G và H: G chỉ có 1 vùng liên thông duy nhất, H có 3 vùng liên thông là H1, H2, H3. H2 G H1 H H3 Hình 5: G liên thông, H gồm 3 vùng liên thông Định nghĩa 5: Đỉnh v được gọi là đỉnh khớp (đỉnh rẻ nhánh) của đồ thị vô hướng G = (V, E) nếu khi loại bỏ đỉnh v và các cạnh liên thuộc với nó thì số thành phần liên thông của G tăng thêm. Cạnh e  E được gọi là cầu nếu loại bỏ nó khỏi đồ thị G thì số thành phần liên thông của G tăng thêm 1 đơn vị. 3.2. Tìm kiếm trên đồ thị. Tìm kiếm trên đồ thị là duyệt (thăm) tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng 1 lần. Vì vậy, việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là một vấn đề quan trọng. Các thuật toán này giữ một vai trò quan trọng trong việc thiết kế các thuật toán trên đồ thị. Trên đồ thị có 2 thuật toán tìm kiếm cơ bản: - Thuật toán tìm kiếm theo chiều sâu (DFS.) - Thuật toán tìm kiếm theo chiều rộng (BFS). 3.3. Tìm đường đi và kiểm tra tính liên thông. Tìm đường đi và kiểm tra tính liên thông là một hình thức ứng dụng các thuật toán tìm kiếm trên đồ thị. Đường đi tìm được theo thuật toán tìm kiếm theo chiều rộng là đường đi ngắn nhất (theo số cạnh) từ đỉnh s đến đỉnh t. 7
4. Đường đi ngắn nhất trên đồ thị. Trong các ứng dụng thực tế. Bài toán tìm đường đi ngắn nhất giữa 2 đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, Bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp tiết kiệm để đưa một hệ động lực từ trạng thái xuất phát đến trạng thái đích, bài toán lập lịch thi công các công đoạn trong một công trình thi công lớn,… II. THỰC TRẠNG CỦA VẤN ĐỀ. 1. Thuận lợi. Lý thuyết đồ thị có thể giải quyết được nhiều bài toán đặt ra trong thực tế phù hợp với đối tượng học sinh giỏi Tin học 11, đặc biệt là những bài toán thể hiện quan hệ nhị phân giữa các đối tượng rời rạc. Vận dụng lý thuyết đồ thị giúp học sinh có thêm một luồng kiến thức mới để làm giàu hơn tư duy thuật toán của mình. Có khá nhiều tài liệu giới thiệu về các vấn đề liên quan đến lý thuyết đồ thị như: sách cấu trúc dữ liệu và giải thuật, Sách Toán rời rạc,…và các tài liệu trên mạng Internet. Giáo viên và học sinh phát huy được tính năng động trong quá trình dạy - học đạt kết quả cao hơn. Một số kiến thức dễ sử dụng và hiệu quả cao. Ví dụ: phép tìm kiếm và kiểm tra vùng liên thông trên đồ thị. 2. Khó khăn. - Trong việc nắm bắt và hiểu được các khái niệm cơ bản liên quan đến lý thuyết đồ thị. - Lý thuyết đồ thị rất rộng và nhiều phần kiến thức khó nên không thể truyền tải hết tới học sinh và khó để đưa vào hết trong đề tài. - Đưa ra các giải thuật bằng ngôn ngữ Pascal và C++ để minh hoạ các kiến thức đưa ra ở phần cơ sở lý luận. 8
- Đưa ra hệ thống các dạng bài tập có thể giải quyết hiệu quả bằng lý thuyết đồ thị và cách giải các bài tập đó. - Để khắc phục được một phần khó khăn nêu trên, trong đề tài tôi chỉ đề cập đến những phần quan trọng của lý thuyết đồ thị có ứng dụng nhiều trong thực tế và phù hợp với học sinh THPT, đặc biệt là học sinh Tin học 11. 9
III. HAI THUẬT TOÁN VÀ MỘT SỐ BÀI TẬP ÁP DỤNG 1. Tìm kiếm theo chiều rộng. Ý tưởng: Đỉnh xuất phát v ở đây cũng được thăm đầu tiên nhưng có khác với DFS ở chổ là: Sau đó các đỉnh chưa được thăm mà là lân cận của v sẽ được thăm kế tiếp theo nhau, rồi mới đến các đỉnh chưa được thăm là lân cận lần lượt của các đỉnh này và cứ tương tự như vậy. Ví dụ: Thứ tự đi trong hình 6: Bắt đầu từ 1 => 2 => 7 => 8 => hết node ngang. Tiếp tục 2 => 3 => 6 hết node ngang. Bắt đầu 7 => không có node ngang. Tiếp tục 8=>9 => 12 hết node ngang Bắt đầu 3 => 4 => 5 => hết node ngang Tiếp tục 6 => không có node ngang Bắt đầu 9 => 10=> 11 hết node ngang Tiếp tục 12 => không có node ngang Bắt đầu 4 => hết node Tiếp tục 5 => hết node Bắt đầu 10 => hết node Hình 6 Tiếp tục 11 => hết node Mô hình thuật toán tìm kiếm theo chiều rộng +) Ngôn ngữ Pascal Procedure BFS(v); {Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v} Begin Queue:=; Queue
Begin u
Free[v]=false; // đánh dấu đỉnh v Push(v); // đẩy đỉnh v vào queue } } Bài tập cơ sở số 1: Viết chương trình ghi ra thứ tự duyệt DFS xuất phát từ đỉnh s. Đồ thị gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau. Dữ liệu vào: Dòng đầu: gồm 3 số nguyên n, m, s (1
Begin readln(n,m,s); for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure Push(u:integer); begin inc(cuoi); Q[cuoi] := u; end; Function Pop : integer; Begin Pop := Q[dau]; inc(dau); end; Procedure BFS(i : integer); Var u, v : integer; Begin Push(i); Free[i] := false; While dau
init; readf; BFS(s); end; BEGIN main; END. +) Ngôn ngữ C++ #include using namespace std; int a[101][101]; queue q; int n,m,Free[101], u,v,s; void BFS(int s) { q.push(s); Free[s]=0; while (!q.empty()) { int u = q.front(); q.pop(); cout > m>> s; for (int i=1; i
for (int i=1; i> u>> v; a[u][v]=1; a[v][u]=1; } for (int i=1; i
2. Tìm kiếm theo chiều sâu Ý tưởng: Đỉnh xuất phát v được thăm. Tiếp theo đó, một đỉnh y chưa được thăm, mà là lân cận của v, sẽ được chọn và một phép tìm kiếm theo chiều sâu xuất phát từ y lại được thực hiện. Khi một đỉnh u đã được “với tới” mà mọi đỉnh lân cận của nó đều đã được thăm rồi, thì ta sẽ quay ngược lên đỉnh cuối cùng vừa được thăm, (mà còn có đỉnh y lân cận với nó chưa được thăm), và một phép tìm kiếm theo chiều sâu xuất phát từ y lại được thực hiện. Phép tìm kiếm sẽ kết thúc khi không còn một nút nào chưa được thăm mà vẫn có thể với tới được từ một nút đã được thăm. Hình 7 Ví dụ thứ tự đi trong hình7. Bắt đầu từ 1 => 2 => 3 => 4 => hết đường đi Quay lại 3 => 5 => hết đường đi Tiếp tục từ 3 quay lại 2 => 6 => hết đường đi Quay lại 2 => quay lại 1 => 7 => hết đường đi Tiếp tục từ 1 => 8 => 9=> 10 => hết đường đi Quay lại 9 => 11 => hết đường đi Tiếp tục 9=> quay lại 8 => 12 => hết đường đi Quay lại 8 => quay lại 1 => hết đường => KẾT THÚC. 16
Mô hình thuật toán tìm kiếm theo chiều sâu: +) Ngôn ngữ Pascal Procedure DFS(v); {tìm theo chiều sâu bắt đầu từ đỉnh v, các biến Chuaxet, ke là cục bộ} Begin Thăm đỉnh (v); Chuaxet[v]:=false; For mỗi đỉnh y Ke( v) do If chuaxet[y] then DFS(); End; Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán sau: BEGIN For vV do Chuaxet[v]:=true; For vV do if Chuaxet[v] then DFS(v); END. +) Ngôn ngữ C++ void dfs(int u) { free[u] = false; // đánh dấu đỉnh u đã được thăm for (int v=1; v
Bài tập cơ sở số 2: Viết chương trình ghi ra thứ tự duyệt DFS xuất phát từ đỉnh s. Đồ thị gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau. Dữ liệu vào:  Dòng đầu: gồm 3 số nguyên n, m, s (1
for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure DFS(u : integer); Var v : integer; Begin writeln(u); Free[u] := false; For v := 1 to n do If A[u,v] and Free[v] then dfs(v); end; Procedure main; Var i : integer; Begin init; readf; DFS(s); end; BEGIN main; END. +) Ngôn ngữ C++ Const maxn = 101; Var a : array [1..maxn,1..maxn] of boolean; free : array [1..maxn] of boolean; Q : array [1..maxn] of integer; n, m, s: integer; dau, cuoi : integer; Procedure init; Begin fillchar(a,sizeof(a),false); fillchar(Free,sizeof(Free),true); end; 19
Procedure readf; Var i, u, v : integer; Begin readln(n,m,s); for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure DFS(u : integer); Var v : integer; Begin writeln(u); Free[u] := false; For v := 1 to n do If A[u,v] and Free[v] then dfs(v); end; Procedure main; Var i : integer; Begin init; readf; DFS(s); end; BEGIN main; END. Bài tập cơ sở số 3: Tìm thành phần liên thông của đồ thị Cho một đồ thị G = (V,E). Hãy cho biết số thành phần liên thông của đồ thị và mỗi thành phần liên thông gồm những đỉnh nào. Gợi ý làm bài: Điều kiện liên thông của đồ thị thường là một yêu cầu tất yếu trong nhiều ứng dụng, chẳng hạn một mạng giao thông hay mạng thông tin nếu không liên thông thì xem như bị hỏng, cần sửa chữa. Vì thế, việc kiểm tra một đồ thị có liên thông hay không là một thao tác cần thiết trong nhiều ứng dụng khác 20