Cây khung và cây khung nhỏ nhất trong đồ thị

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu c&acirc;y khung v&agrave; c&acirc;y khung nhỏ nhất c&ugrave;ng với sự trợ gi&uacute;p của c&aacute;c h&igrave;nh ảnh v&iacute; dụ v&agrave; minh họa.</p> <p style="text-align: justify;">Trước khi t&igrave;m hiểu về c&acirc;y khung, ch&uacute;ng ta cần hiểu về hai loại đồ thị:</p> <ol style="text-align: justify;"> <li>Đồ thị v&ocirc; hướng</li> <li>Đồ thị li&ecirc;n th&ocirc;ng</li> </ol> <p style="text-align: justify;">Đồ thị v&ocirc; hướng l&agrave; đồ thị trong đ&oacute; c&aacute;c cạnh kh&ocirc;ng hướng theo bất kỳ theo hướng n&agrave;o (tức l&agrave; c&aacute;c cạnh đều c&oacute; hướng l&agrave; hai chiều, xu&ocirc;i v&agrave; ngược). H&igrave;nh ảnh minh họa b&ecirc;n dưới đ&acirc;y sẽ v&iacute; dụ về đồ thị v&ocirc; hướng như sau.</p> <p><img style="width: 100%;" src="../../../public_files/46b284c2-7cd6-4ffa-89f4-05ecbf68149f" alt="cau-truc-du-lieu-cay-khung" /></p> <p>Đồ thị li&ecirc;n th&ocirc;ng l&agrave; đồ thị trong đ&oacute; lu&ocirc;n c&oacute; đường đi từ một đỉnh đến bất kỳ đỉnh n&agrave;o kh&aacute;c.</p> <p><img style="width: 100%;" src="../../../public_files/392925df-b7ab-4f4c-baa6-967e3f60f00b" alt="cau-truc-du-lieu-cay-khung-2" /></p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Cấu tr&uacute;c dữ liệu c&acirc;y khung</h2> <p style="text-align: justify;">C&acirc;y khung l&agrave; một đồ thị con của một đồ thị li&ecirc;n th&ocirc;ng v&ocirc; hướng, bao gồm tất cả c&aacute;c đỉnh của đồ thị với số cạnh &iacute;t nhất c&oacute; thể. Nếu một đỉnh bị thiếu, th&igrave; n&oacute; kh&ocirc;ng phải l&agrave; c&acirc;y khung. C&aacute;c cạnh c&oacute; thể c&oacute; hoặc kh&ocirc;ng c&oacute; trọng số được g&aacute;n cho ch&uacute;ng.</p> <p style="text-align: justify;">Tổng số c&acirc;y khung c&oacute; $n$ đỉnh c&oacute; thể được tạo ra từ một đồ thị ho&agrave;n chỉnh bằng $n^{(n-2)}$.</p> <p style="text-align: justify;">Nếu&nbsp; $n = 4$, số c&acirc;y khung lớn nhất c&oacute; thể bằng $4^{4 - 2} = 16$. Như vậy, 16 c&acirc;y khung c&oacute; thể được h&igrave;nh th&agrave;nh từ một đồ thị ho&agrave;n chỉnh bao gồm 4 đỉnh.</p> <p style="text-align: justify;">V&iacute; dụ về c&acirc;y khung, ta sẽ c&ugrave;ng t&igrave;m hiểu về c&acirc;y khung với c&aacute;c v&iacute; dụ dưới đ&acirc;y.</p> <ul> <li style="text-align: justify;">Giả sử đồ thị ban đầu c&oacute; dạng như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/2488a91b-0c29-4b28-819c-02c07c09a9d8" alt="cau-truc-du-lieu-cay-khung-3" /></p> <ul> <li>Một số c&acirc;y khung c&oacute; thể được tạo từ biểu đồ tr&ecirc;n bao gồm:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/ead13550-e125-4b2d-aed1-eb4786e7c1ee" alt="cau-truc-du-lieu-cay-khung-4" /></p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&acirc;y khung nhỏ nhất</h2> <p style="text-align: justify;">Cho trước một đồ thị v&ocirc; hướng c&oacute; trọng số. Ch&uacute;ng ta muốn t&igrave;m một c&acirc;y con của đồ thị n&agrave;y nối tất cả c&aacute;c đỉnh (tức l&agrave; n&oacute; l&agrave; c&acirc;y khung) v&agrave; c&oacute; trọng số nhỏ nhất (tức l&agrave; tổng trọng số của tất cả c&aacute;c cạnh l&agrave; nhỏ nhất) của tất cả c&aacute;c c&acirc;y khung c&oacute; thể c&oacute;. C&acirc;y khung m&agrave; chứa tổng trọng số của c&aacute;c cạnh l&agrave; nhỏ nhất được gọi l&agrave; c&acirc;y khung nhỏ nhất.</p> <p style="text-align: justify;">Một v&iacute; dụ điển h&igrave;nh về ứng dụng của c&acirc;y khung nhỏ nhất l&agrave; khi một c&ocirc;ng ty lắp c&aacute;p muốn đặt đường d&acirc;y đến nhiều v&ugrave;ng l&acirc;n cận sao giảm thiểu số lượng c&aacute;p cần đặt l&agrave; &iacute;t nhất c&oacute; thể, như vậy, c&ocirc;ng ty lắp c&aacute;p n&agrave;y c&oacute; thể sẽ tiết kiệm được khoản tiền kh&aacute; lớn.</p> <p style="text-align: justify;">Thuộc t&iacute;nh của c&acirc;y khung nhỏ nhất bao gồm như sau:</p> <ul style="text-align: justify;"> <li>C&acirc;y khung nhỏ nhất của đồ thị l&agrave; duy nhất, nếu trọng số của tất cả c&aacute;c cạnh l&agrave; kh&aacute;c nhau. Nếu kh&ocirc;ng, c&oacute; thể c&oacute; nhiều c&acirc;y khung nhỏ nhất.</li> <li>C&acirc;y khung nhỏ nhất cũng l&agrave; c&acirc;y c&oacute; t&iacute;ch của trọng số c&aacute;c cạnh l&agrave; nhỏ nhất.</li> </ul> <p style="text-align: justify;">V&iacute; dụ về c&acirc;y khung nhỏ nhất, ta sẽ c&ugrave;ng t&igrave;m hiểu về định nghĩa c&acirc;y khung nhỏ nhất c&ugrave;ng với sự trợ gi&uacute;p của v&iacute; dụ dưới đ&acirc;y.</p> <ul> <li style="text-align: justify;">Ta c&oacute; đồ thị c&oacute; dạng ban đầu như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/6fd77e31-212d-455b-b554-a6b65adebb0a" alt="cau-truc-du-lieu-cay-khung-5" /></p> <ul> <li>C&aacute;c c&acirc;y khung c&oacute; thể được tạo ra từ biểu đồ tr&ecirc;n bao gồm như sau.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/8c0ffc3c-8652-4ecc-8181-8cc773766ea8" alt="cau-truc-du-lieu-cay-khung-6" /></p> <p><img style="width: 100%;" src="../../../public_files/c94dd150-e855-4419-9cbb-5811f8f58d30" alt="cau-truc-du-lieu-cay-khung-7" /></p> <p><img style="width: 100%;" src="../../../public_files/0a3c8933-165e-4dca-b294-744930e919b8" alt="cau-truc-du-lieu-cay-khung-8" /></p> <p><img style="width: 100%;" src="../../../public_files/ab5e6805-be4c-41f6-b6d2-f4840386fe58" alt="cau-truc-du-lieu-cay-khung-9" /></p> <ul> <li>Như vậy, c&acirc;y khung nhỏ nhất trong c&aacute;c c&acirc;y khung b&ecirc;n tr&ecirc;n l&agrave;:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/333d3b9e-4f8b-43e2-bf38-42441b85bdb1" alt="cau-truc-du-lieu-cay-khung-10" /></p> <p style="text-align: justify;">C&acirc;y khung nhỏ nhất từ biểu đồ được tạo bằng c&aacute;ch sử dụng c&aacute;c thuật to&aacute;n sau:</p> <ol style="text-align: justify;"> <li>Thuật to&aacute;n Prim</li> <li>Thuật to&aacute;n Kruskal</li> </ol> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Ứng dụng của c&acirc;y khung</h2> <ul style="text-align: justify;"> <li>Được sử dụng trong giao thức định tuyến mạng m&aacute;y t&iacute;nh.</li> <li>D&ugrave;ng để ph&acirc;n t&iacute;ch nh&oacute;m hoặc ph&acirc;n cụm.</li> <li>D&ugrave;ng trong quy hoạch mạng d&acirc;n sự.</li> <li>Để t&igrave;m đường đi trong bản đồ.</li> <li>Thiết kế c&aacute;c mạng như mạng viễn th&ocirc;ng, mạng lưới điện.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về cấu tr&uacute;c dữ liệu c&acirc;y khung. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>