Khác biệt giữa bản sửa đổi của “Cây bao trùm”
Nội dung được xóa Nội dung được thêm vào
thuật toán tìm kiếm theo chiều rộng, tìm kiếm theo chiều sâu, Prim, Kruskal đều có bài riêng, không cần phải nêu chi tiết ở đây. |
thêm hình minh họa |
||
Dòng 1:
{{hợp nhất từ|Cây tối đại}}
[[File:4x4 grid spanning tree.svg|thumb|Một cây bao trùm (các cạnh màu xanh) của một đồ thị lưới]]
'''Cây bao trùm''' ([[tiếng Anh]]: ''spanning tree''), còn được gọi là '''cây khung''', của đồ thị G là [[Cây (cấu trúc dữ liệu)|cây]] con của đồ thị G, chứa tất cả các đỉnh của G. Nói cách khác, cây bao trùm của một đồ thị G là một [[đồ thị]] con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.
Hàng 12 ⟶ 13:
==Số các cây bao trùm của một đồ thị liên thông==
[[Image:Cayley's formula 2-4.svg|thumb|[[Công thức Cayley]] đếm số cây bao trùm của một đồ thị đầy đủ. Có tất cả <math>2^{2-2}=1</math> cây bao trùm của <math>K_2</math>,
<math>3^{3-2}=3</math> cây bao trùm của <math>K_3</math>, và <math>4^{4-2}=16</math>
cây bao trùm của <math>K_4</math>.]]
Gọi ''t(G)'' là số các cây bao trùm của đồ thị liên thông G. Trong một số trường hợp, số ''t(G)'' có thể tính trực tiếp.
Chảng hạn nếu ''G'' là một cây, khi đó ''t(G)=1'', còn khi ''G'' là một [[đồ thị vòng]] <math>C_n</math> với ''n'' đỉnh thì ''t(G)=n''.
| |||