I. Tổng quan về cây khung của đồ thị và vai trò cốt lõi
Trong lý thuyết đồ thị, cây khung của đồ thị là một khái niệm nền tảng, đóng vai trò then chốt trong việc giải quyết nhiều bài toán tối ưu hóa mạng lưới. Một cây khung, hay còn gọi là cây phủ hoặc cây bao trùm, là một đồ thị bộ phận đặc biệt của một đồ thị vô hướng liên thông G. Cụ thể, tài liệu "Bài giảng Lý thuyết đồ thị" của Đặng Nguyễn Đức Tiến (HCMUS – 2010) định nghĩa: “Nếu đồ thị bộ phận T của đồ thị vô hướng liên thông G = (V, E) là một cây thì khi đó cây T được gọi là cây khung (spanning tree) của đồ thị G.” Điều này có nghĩa là cây khung phải thỏa mãn hai điều kiện: nó là một cây (không chứa chu trình) và nó chứa tất cả các đỉnh của đồ thị gốc G. Sự tồn tại của một cây khung là dấu hiệu xác nhận tính liên thông của đồ thị. Một định lý quan trọng khẳng định: “Một đơn đồ thị là liên thông nếu và chỉ nếu nó có cây khung.” Điều này cho thấy mối quan hệ mật thiết giữa cấu trúc cây và đặc tính kết nối của toàn bộ đồ thị. Việc tìm kiếm và xây dựng cây khung đồ thị không chỉ là một bài toán lý thuyết mà còn là cơ sở cho các thuật toán duyệt đồ thị như tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS). Quá trình duyệt qua các đỉnh trong các thuật toán này thực chất chính là quá trình hình thành một cây khung của đồ thị đang xét.
1.1. Định nghĩa chính xác về cây khung cây phủ của đồ thị
Một cây khung (spanning tree) của một đồ thị vô hướng liên thông G=(V, E) là một đồ thị con T=(V, E') của G. Đồ thị con T phải là một cây, nghĩa là nó không chứa bất kỳ chu trình nào và vẫn đảm bảo tính liên thông. Quan trọng nhất, T phải "phủ" toàn bộ các đỉnh của G, tức là tập đỉnh của T trùng với tập đỉnh V của G. Nếu G có n đỉnh, thì bất kỳ cây khung nào của nó cũng sẽ có chính xác n đỉnh và n-1 cạnh. Ví dụ, một đồ thị G có 13 đỉnh và 20 cạnh, thì cây bao trùm của nó sẽ có 13 đỉnh và 12 cạnh. Việc loại bỏ các cạnh thừa để phá vỡ chu trình là cách cơ bản để hình thành cây khung từ một đồ thị liên thông. Mỗi đồ thị liên thông có thể có một hoặc nhiều cây khung khác nhau.
1.2. Mối liên hệ giữa cây khung và tính liên thông của đồ thị
Tính liên thông của đồ thị là một tính chất cơ bản, và cây khung là công cụ để chứng minh và khai thác tính chất này. Chứng minh cho mệnh đề "Một đơn đồ thị là liên thông nếu và chỉ nếu nó có cây khung" rất trực quan. Chiều đảo: Nếu G có cây khung T, vì T là cây nên luôn có đường đi giữa hai đỉnh bất kỳ. Do T là đồ thị bộ phận của G, nên G cũng có đường đi giữa hai đỉnh bất kỳ, suy ra G liên thông. Chiều thuận: Nếu G liên thông nhưng không phải là cây, nó phải chứa ít nhất một chu trình đơn. Ta có thể loại bỏ một cạnh bất kỳ trong chu trình đó mà không làm mất tính liên thông. Quá trình này được lặp lại cho đến khi không còn chu trình nào, kết quả thu được là một đồ thị con không có chu trình, liên thông và chứa mọi đỉnh của G - đó chính là một cây khung.
1.3. Cách xác định số cây khung trong đồ thị đầy đủ Kn
Việc đếm số lượng cây khung có thể có của một đồ thị là một bài toán quan trọng. Đối với trường hợp đặc biệt là đồ thị đầy đủ Kn (đồ thị có n đỉnh và mọi cặp đỉnh đều được nối với nhau bằng một cạnh), số lượng cây khung được xác định bởi một công thức nổi tiếng. Theo Định lý Borchart, Sylvester, Cayley: “Số cây khung của đồ thị đầy đủ Kn là n^(n-2).” Ví dụ, để trả lời câu hỏi “Đồ thị đầy đủ K5 có bao nhiêu cây khung?”, ta áp dụng công thức với n=5. Số cây khung sẽ là 5^(5-2) = 5^3 = 125. Công thức này cho thấy số lượng cây khung tăng rất nhanh khi số đỉnh của đồ thị tăng lên, thể hiện sự phức tạp và đa dạng trong cấu trúc kết nối của đồ thị.
II. Thách thức tìm cây khung nhỏ nhất trong lý thuyết đồ thị
Khi các cạnh của đồ thị được gán thêm một giá trị, gọi là trọng số hoặc chi phí, bài toán tìm cây khung trở nên phức tạp hơn và mang ý nghĩa thực tiễn to lớn. Đây là lúc khái niệm đồ thị có trọng số ra đời. Trong một đồ thị có trọng số, mỗi cây khung sẽ có một tổng trọng số, được tính bằng tổng trọng số của tất cả các cạnh thuộc cây khung đó. Bài toán không còn là tìm một cây khung bất kỳ, mà là tìm ra cây khung có tổng trọng số nhỏ nhất, được gọi là cây khung nhỏ nhất (Minimum Spanning Tree - MST). Đây là một bài toán tối ưu hóa kinh điển trong lý thuyết đồ thị. Ví dụ, trong bài toán xây dựng hệ thống đường cao tốc nối các thành phố, mỗi đỉnh là một thành phố và trọng số mỗi cạnh là chi phí xây dựng con đường tương ứng. Mục tiêu là kết nối tất cả các thành phố với tổng chi phí thấp nhất, tương đương với việc tìm cây khung nhỏ nhất của đồ thị. Tương tự, bài toán nối mạng máy tính sao cho tổng chi phí dây cáp là tối thiểu cũng là một ứng dụng trực tiếp của việc tìm cây khung nhỏ nhất. Việc lựa chọn sai các cạnh có thể dẫn đến một cây khung với chi phí rất cao, do đó, các thuật toán hiệu quả để giải quyết bài toán này là cực kỳ cần thiết.
2.1. Khái niệm đồ thị có trọng số và bài toán tối ưu hóa
Một đồ thị có trọng số (weighted graph) là một đồ thị G = (V, E) mà mỗi cạnh e ∈ E được gán một số thực không âm c(e), gọi là trọng số hoặc chi phí. Tổng trọng số của một cây khung T, ký hiệu c(T), là tổng chi phí của các cạnh thuộc T. Bài toán cây khung nhỏ nhất yêu cầu tìm trong số tất cả các cây khung của G một cây T* sao cho c(T*) là nhỏ nhất. Đây là một bài toán tối ưu hóa tổ hợp, vì không gian tìm kiếm là tập hợp tất cả các cây khung có thể có của đồ thị, một không gian thường rất lớn. Việc duyệt qua tất cả các cây khung để tìm cây có trọng số nhỏ nhất là không khả thi đối với các đồ thị lớn, đòi hỏi phải có các thuật toán thông minh và hiệu quả.
2.2. Sự khác biệt giữa cây khung nhỏ nhất và cây khung lớn nhất
Bên cạnh cây khung nhỏ nhất, tồn tại một khái niệm đối ngược là cây khung lớn nhất (Maximum Spanning Tree). Đây là cây khung có tổng trọng số các cạnh là lớn nhất. Mặc dù ít phổ biến hơn trong các ứng dụng thực tế, bài toán này vẫn có giá trị lý thuyết. Về mặt thuật toán, việc tìm cây khung lớn nhất có thể được quy về bài toán tìm cây khung nhỏ nhất. Cách tiếp cận đơn giản là nhân tất cả các trọng số của các cạnh trong đồ thị với -1, sau đó áp dụng một thuật toán tìm cây khung nhỏ nhất (như Prim hoặc Kruskal) trên đồ thị mới. Cây khung kết quả sẽ chính là cây khung lớn nhất của đồ thị ban đầu. Điều này cho thấy hai bài toán này có cùng bản chất cấu trúc và độ phức tạp tính toán.
III. Hướng dẫn thuật toán Prim tìm cây khung đồ thị hiệu quả
Thuật toán Prim, do Robert Prim đề xuất năm 1957, là một trong hai thuật toán tham lam kinh điển để tìm cây khung nhỏ nhất trong một đồ thị có trọng số, liên thông và vô hướng. Tư tưởng chính của thuật toán là xây dựng cây khung bắt đầu từ một đỉnh tùy ý. Tại mỗi bước, thuật toán sẽ mở rộng cây đang xây dựng bằng cách thêm vào một cạnh có trọng số nhỏ nhất, với điều kiện cạnh này phải nối một đỉnh đã có trong cây với một đỉnh chưa có trong cây. Quá trình này đảm bảo rằng cấu trúc được tạo ra luôn là một cây và không tạo thành chu trình. Thuật toán sẽ dừng lại khi cây đã chứa đủ n đỉnh (tương đương với việc đã thêm n-1 cạnh), lúc đó ta thu được một cây khung nhỏ nhất của đồ thị. Thuật toán Prim đặc biệt hiệu quả với các đồ thị dày (dense graphs), nơi số cạnh gần bằng số cạnh tối đa có thể có. Sự đơn giản trong logic và cách tiếp cận cục bộ tối ưu tại mỗi bước làm cho thuật toán Prim trở thành một công cụ mạnh mẽ trong lý thuyết đồ thị và các ứng dụng mạng lưới.
3.1. Nguyên lý hoạt động cốt lõi của thuật toán Prim
Nguyên lý của thuật toán Prim dựa trên chiến lược "tham lam" (greedy). Thuật toán chia tập đỉnh V của đồ thị thành hai tập: tập Y chứa các đỉnh đã thuộc cây khung đang xây dựng, và tập V\Y chứa các đỉnh còn lại. Khởi đầu, Y chỉ chứa một đỉnh gốc tùy chọn. Ở mỗi bước lặp, thuật toán tìm cạnh e = (v, w) có trọng số nhỏ nhất sao cho v ∈ Y và w ∈ V\Y. Cạnh e này sau đó được thêm vào cây khung, và đỉnh w được chuyển từ V\Y sang Y. Quá trình này được lặp lại n-1 lần. Điểm mấu chốt là ở mỗi bước, thuật toán luôn chọn giải pháp "tốt nhất" tại thời điểm đó (cạnh rẻ nhất để mở rộng cây) mà không cần quan tâm đến các bước sau. Điều kỳ diệu là chiến lược cục bộ này lại dẫn đến một giải pháp tối ưu toàn cục, tức là một cây khung nhỏ nhất.
3.2. Các bước triển khai chi tiết thuật toán Prim qua ví dụ
Xét một đồ thị G. Các bước triển khai thuật toán Prim như sau:
- Khởi tạo: Chọn một đỉnh bắt đầu, ví dụ đỉnh 1. Đặt Y = {1} và tập cạnh của cây khung T = ∅.
- Lặp: Tìm trong số các cạnh nối một đỉnh trong Y với một đỉnh ngoài Y, chọn cạnh có trọng số nhỏ nhất. Ví dụ, nếu các cạnh có thể chọn là (1,2) với trọng số 4 và (1,4) với trọng số 3, ta sẽ chọn cạnh (1,4).
- Cập nhật: Thêm cạnh (1,4) vào T và thêm đỉnh 4 vào Y. Lúc này, Y = {1, 4} và T = {{1,4}}.
- Lặp lại bước 2: Bây giờ ta tìm cạnh nhỏ nhất nối các đỉnh trong {1, 4} với các đỉnh bên ngoài. Quá trình này tiếp tục cho đến khi Y chứa tất cả các đỉnh của đồ thị và T có n-1 cạnh. Kết quả cuối cùng là một cây khung nhỏ nhất.
3.3. Chứng minh tính đúng đắn của thuật toán Prim
Tính đúng đắn của thuật toán Prim có thể được chứng minh bằng phương pháp phản chứng. Giả sử S là cây khung được tạo bởi thuật toán Prim và T là một cây khung nhỏ nhất bất kỳ của đồ thị G. Nếu S = T, thuật toán đúng. Nếu S ≠ T, gọi ek+1 là cạnh đầu tiên được Prim chọn nhưng không thuộc T. Khi thêm ek+1 vào T, sẽ tạo ra một chu trình. Chu trình này phải chứa một cạnh e không thuộc S. Vì Prim đã chọn ek+1 thay vì e ở bước đó, điều này có nghĩa là c(ek+1) ≤ c(e). Nếu ta tạo cây T' bằng cách bỏ cạnh e và thêm cạnh ek+1 vào T, ta được một cây khung mới có tổng trọng số c(T') ≤ c(T). Vì T là cây khung nhỏ nhất, nên T' cũng phải là cây khung nhỏ nhất. Lặp lại quá trình này, ta có thể biến đổi T thành S mà không làm tăng tổng trọng số, suy ra S cũng là một cây khung nhỏ nhất.
IV. Phương pháp Kruskal Bí quyết xây dựng cây khung tối ưu
Thuật toán Kruskal, được phát minh bởi Joseph Kruskal vào năm 1956, là một phương pháp tham lam khác để tìm cây khung nhỏ nhất của một đồ thị có trọng số. Khác với thuật toán Prim xây dựng cây từ một điểm duy nhất và mở rộng ra, thuật toán Kruskal tiếp cận bài toán bằng cách xây dựng một "rừng". Ban đầu, mỗi đỉnh của đồ thị được xem là một cây riêng lẻ trong khu rừng này. Thuật toán sẽ xét tất cả các cạnh của đồ thị theo thứ tự trọng số tăng dần. Với mỗi cạnh, nếu việc thêm nó vào tập hợp các cạnh đã chọn không tạo ra một chu trình đơn, cạnh đó sẽ được chấp nhận. Việc này tương đương với việc hợp nhất hai cây khác nhau trong rừng thành một cây lớn hơn. Quá trình này tiếp tục cho đến khi chỉ còn lại một cây duy nhất, chứa tất cả các đỉnh và n-1 cạnh. Cây này chính là cây khung nhỏ nhất. Thuật toán Kruskal đặc biệt hiệu quả với các đồ thị thưa (sparse graphs), nơi số cạnh ít hơn nhiều so với số đỉnh bình phương.
4.1. Tư tưởng tham lam trong thuật toán Kruskal
Tư tưởng tham lam của thuật toán Kruskal thể hiện ở việc luôn ưu tiên chọn cạnh có trọng số nhỏ nhất có thể. Bằng cách sắp xếp tất cả các cạnh của đồ thị theo thứ tự trọng số không giảm, thuật toán đảm bảo rằng nó luôn xem xét các "lựa chọn rẻ nhất" trước. Tại mỗi bước, quyết định thêm một cạnh vào cây khung chỉ dựa trên hai tiêu chí: (1) nó có phải là cạnh rẻ nhất chưa được xét hay không, và (2) nó có tạo ra chu trình hay không. Thuật toán không cần "nhìn xa" hay quay lui. Chiến lược này hoạt động hiệu quả vì một cạnh có trọng số nhỏ sẽ không bao giờ bị bỏ qua trừ khi nó tạo ra một chu trình, nghĩa là các đỉnh mà nó nối đã được kết nối với nhau thông qua một đường đi gồm các cạnh còn rẻ hơn.
4.2. Hướng dẫn từng bước xây dựng cây khung với Kruskal
Các bước thực hiện thuật toán Kruskal như sau:
- Khởi tạo: Tạo một tập hợp T rỗng để chứa các cạnh của cây khung nhỏ nhất. Tạo ra n tập hợp con riêng biệt, mỗi tập chứa một đỉnh của đồ thị.
- Sắp xếp: Sắp xếp tất cả các cạnh của đồ thị theo thứ tự trọng số tăng dần.
- Lặp: Lần lượt duyệt qua danh sách các cạnh đã sắp xếp. Với mỗi cạnh (u, v): a. Kiểm tra xem u và v có thuộc cùng một tập hợp con hay không. Nếu không, tức là thêm cạnh (u, v) không tạo ra chu trình. b. Nếu không tạo chu trình, thêm (u, v) vào T và hợp nhất hai tập hợp con chứa u và v.
- Dừng: Thuật toán kết thúc khi T có đủ n-1 cạnh. T chính là tập các cạnh của cây khung nhỏ nhất.
4.3. Phân tích và chứng minh hiệu quả của thuật toán Kruskal
Hiệu quả của thuật toán Kruskal phụ thuộc chủ yếu vào hai thao tác: sắp xếp các cạnh và kiểm tra chu trình (thông qua cấu trúc dữ liệu Union-Find). Việc sắp xếp m cạnh mất thời gian O(m log m). Các thao tác Union-Find có thể được thực hiện rất nhanh. Do đó, độ phức tạp tổng thể của thuật toán thường bị chi phối bởi bước sắp xếp. Tính đúng đắn của thuật toán cũng được chứng minh bằng phản chứng, tương tự như thuật toán Prim. Giả sử T là cây được tạo bởi Kruskal và S là một cây khung nhỏ nhất. Nếu T ≠ S, gọi ek là cạnh đầu tiên trong T không thuộc S. Thêm ek vào S sẽ tạo ra chu trình C. Chu trình C này phải chứa ít nhất một cạnh e không thuộc T. Theo cách Kruskal xây dựng T, c(ek) ≤ c(e). Thay thế e bằng ek trong S tạo ra một cây khung S' với c(S') ≤ c(S). Bằng cách lặp lại quá trình này, S có thể được biến đổi thành T mà không làm tăng tổng trọng số, chứng tỏ T cũng là cây khung nhỏ nhất.
V. Ứng dụng thực tiễn của cây khung đồ thị trong thực tế
Khái niệm cây khung của đồ thị, đặc biệt là cây khung nhỏ nhất, có vô số ứng dụng quan trọng trong thế giới thực, vượt ra ngoài phạm vi của lý thuyết đồ thị thuần túy. Bất cứ khi nào có một bài toán yêu cầu kết nối một tập hợp các điểm với chi phí tối thiểu mà không tạo ra sự dư thừa (chu trình), bài toán cây khung nhỏ nhất sẽ là mô hình phù hợp. Các ứng dụng trải dài từ kỹ thuật mạng, quy hoạch đô thị, sinh học tính toán đến phân tích dữ liệu. Ví dụ, trong thiết kế vi mạch, các thuật toán tìm cây khung được sử dụng để bố trí đường dây nối các chân linh kiện sao cho tổng chiều dài dây dẫn là ngắn nhất, giảm thiểu độ trễ tín hiệu và chi phí vật liệu. Trong phân cụm dữ liệu, các thuật toán này có thể giúp xác định các cụm tự nhiên bằng cách xây dựng một cây khung nhỏ nhất trên đồ thị của các điểm dữ liệu và sau đó loại bỏ các cạnh dài nhất. Sự linh hoạt và hiệu quả của các thuật toán như Prim và Kruskal làm cho chúng trở thành những công cụ không thể thiếu cho các kỹ sư, nhà khoa học và nhà quy hoạch.
5.1. Tối ưu hóa chi phí mạng lưới với bài toán cây khung nhỏ nhất
Một trong những ứng dụng kinh điển nhất là thiết kế mạng lưới. Ví dụ như bài toán “xây dựng hệ thống đường cao tốc” được đề cập trong tài liệu. Các thành phố là các đỉnh, và chi phí xây dựng đường nối hai thành phố là trọng số của cạnh. Để đảm bảo mọi người có thể đi từ thành phố bất kỳ đến thành phố khác với tổng chi phí xây dựng là nhỏ nhất, các nhà quy hoạch cần tìm cây khung nhỏ nhất của đồ thị này. Tương tự, trong việc thiết kế mạng lưới điện, mạng viễn thông, hoặc đường ống dẫn nước/dầu, mục tiêu là kết nối tất cả các điểm tiêu thụ với nguồn cung cấp bằng tổng chiều dài cáp hoặc đường ống ít nhất. Thuật toán Kruskal và thuật toán Prim cung cấp các giải pháp hiệu quả cho những bài toán quy mô lớn này.
5.2. Vai trò của cây khung trong thiết kế mạng máy tính
Trong lĩnh vực mạng máy tính, cây khung đóng vai trò cực kỳ quan trọng trong các giao thức chuyển mạch lớp 2 của mạng Ethernet. Giao thức Spanning Tree Protocol (STP) được thiết kế để ngăn chặn các vòng lặp (broadcast storms) trong một mạng có các kết nối dự phòng. STP hoạt động bằng cách tự động xây dựng một cây khung logic trên toàn bộ mạng. Nó sẽ vô hiệu hóa các liên kết dư thừa có thể tạo ra chu trình. Bằng cách này, chỉ có một đường đi duy nhất giữa hai thiết bị bất kỳ trong mạng, loại bỏ hoàn toàn các vòng lặp trong khi vẫn duy trì tính liên thông. Về cơ bản, STP sử dụng một biến thể của thuật toán tìm cây khung để tạo ra một cấu trúc liên kết không có chu trình, đảm bảo sự ổn định và hiệu quả của mạng.
VI. Kết luận và định hướng phát triển lý thuyết cây khung
Tóm lại, cây khung của đồ thị là một cấu trúc cơ bản nhưng vô cùng mạnh mẽ trong lý thuyết đồ thị. Từ việc xác định tính liên thông của một đồ thị đơn giản cho đến việc giải quyết các bài toán tối ưu hóa phức tạp trong đồ thị có trọng số, cây khung luôn là một công cụ phân tích và giải quyết vấn đề hiệu quả. Hai thuật toán kinh điển, thuật toán Prim và thuật toán Kruskal, với triết lý tham lam của mình, đã cung cấp những phương pháp hiệu quả để tìm ra cây khung nhỏ nhất, tạo nền tảng cho vô số ứng dụng thực tiễn trong kỹ thuật, kinh tế và khoa học. Các thuật toán này không chỉ giải quyết bài toán mà còn minh họa cho sức mạnh của các chiến lược thuật toán đơn giản trong việc tìm ra giải pháp tối ưu toàn cục. Lý thuyết về cây khung đồ thị vẫn tiếp tục là một lĩnh vực nghiên cứu sôi nổi. Các nhà khoa học máy tính không ngừng tìm cách cải tiến các thuật toán hiện có, đặc biệt là cho các đồ thị quy mô cực lớn hoặc các đồ thị động (dynamic graphs) nơi cấu trúc và trọng số có thể thay đổi theo thời gian. Các bài toán biến thể của cây khung nhỏ nhất, như cây Steiner hoặc cây khung bị ràng buộc về bậc, vẫn là những thách thức mở, hứa hẹn nhiều khám phá mới trong tương lai.
6.1. Tóm tắt các thuật toán tìm cây khung đồ thị phổ biến
Các thuật toán tìm cây khung có thể được chia thành hai loại chính. Thứ nhất là các thuật toán cho đồ thị không trọng số, như tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS), chúng tạo ra một cây khung như một sản phẩm phụ của quá trình duyệt đồ thị. Thứ hai, và quan trọng hơn, là các thuật toán cho đồ thị có trọng số để tìm cây khung nhỏ nhất. Thuật toán Prim xây dựng cây một cách liên tục từ một đỉnh, phù hợp với đồ thị dày. Thuật toán Kruskal xây dựng cây bằng cách hợp nhất các thành phần liên thông, phù hợp với đồ thị thưa. Cả hai đều là thuật toán tham lam và đảm bảo tìm ra lời giải tối ưu. Sự lựa chọn giữa chúng phụ thuộc vào đặc điểm cụ thể của đồ thị đầu vào.
6.2. Triển vọng nghiên cứu và các bài toán mở liên quan
Lĩnh vực nghiên cứu về cây khung vẫn còn nhiều tiềm năng. Các hướng phát triển chính bao gồm việc thiết kế các thuật toán song song và phân tán để xử lý các đồ thị khổng lồ không thể chứa trong bộ nhớ của một máy tính. Các bài toán trên đồ thị động, nơi các cạnh và đỉnh có thể được thêm hoặc bớt, đòi hỏi các thuật toán có thể cập nhật cây khung nhỏ nhất một cách nhanh chóng mà không cần tính toán lại từ đầu. Ngoài ra, các bài toán có thêm ràng buộc, chẳng hạn như tìm cây khung có đường kính nhỏ nhất hoặc số lá tối đa, là những thách thức lý thuyết hấp dẫn và có ứng dụng trong các lĩnh vực chuyên biệt. Những bài toán này thường khó hơn nhiều so với bài toán cây khung nhỏ nhất kinh điển và vẫn là chủ đề nghiên cứu tích cực trong cộng đồng lý thuyết đồ thị.
