Xem mã nguồn của Cây bao trùm

[[Tập tin:4x4 grid spanning tree.svg|nhỏ|Một cây bao trùm (các cạnh màu xanh) của một đồ thị lưới]]
[[Tập tin:Натурализация гамильтоновых циклов.jpg|nhỏ|Ba ví dụ trên biểu đồ lưới 8x8]]
'''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.

Cây bao trùm của đồ thị liên thông G cũng có thể định nghĩa như một đồ thị con không chu trình lớn nhất, hay một đồ thị con liên thông nhỏ nhất của G.
 
Mọi đồ thị liên thông đều có cây bao trùm.

== Định lý (sự tồn tại của cây khung)==

 Mọi đồ thị liên thông đều có chứa ít nhất 1 cây khung (cây tối đại)

==Số các cây bao trùm của một đồ thị liên thông==
[[Hình:Cayley's formula 2-4.svg|nhỏ|[[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''.
Với đồ thị ''G'' bất kỳ, số ''t(G)'' có tính nhờ [[Định lý Kirchhoff]].

'''[[Công thức Cayley]]''' là công thức cho số các cây bao trùm của đồ thị đầy đủ
<math>K_n</math> với ''n'' đỉnh: <math>t(K_n)=n^{n-2}</math>.

Nếu ''G'' là [[đồ thị hai phía đầy đủ]] <math>K_{p,q}</math>, thì <math>t(G)=p^{q-1}q^{p-1}</math>, còn nếu''G'' là  [[đồ thị khối ''n''-chiều]]
<math>Q_n</math>, thì <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>.
Các công thức này rút ra từ lý thuyết các ma trận.

Nếu ''G'' là một [[đa đồ thị]] và ''e'' là một cạnh của ''G'', thì số  ''t(G)'' các cây bao trùm của ''G'' thỏa mãn quan hệ ''t(G)=t(G-e)+t(G/e)'' (''deletion-contraction recurrence''), trong đó ''G-e'' là đa đồ thị suy ra từ ''G'' bằng cách xóa đi cạnh ''e'' và ''G/e'' là đồ thị [[rút gọn cạnh]]''e'' của ''G'', trong đó các cạnh bội xuất hiện từ phép rút gọn này không bị xóa.

==Thuật toán tìm cây bao trùm==
Có thể tìm cây bao trùm bằng thuật toán [[tìm kiếm theo chiều rộng]], hoặc thuật toán [[tìm kiếm theo chiều sâu]].

==Cây bao trùm nhỏ nhất==
Nếu trên tập các cạnh của G có một hàm, được gọi là hàm trọng số, nhận giá trị thực <math>\phi</math>(u,v), thì cây bao trùm có tổng trọng số trên các cạnh nhỏ nhất được gọi là [[cây bao trùm nhỏ nhất]]. Có nhiều thuật toán tìm cây bao trùm nhỏ nhất, chẳng hạn như [[thuật toán Prim]], [[thuật toán Kruskal]], [[thuật toán Borůvka]].

==Xem thêm==
*[[Cây bao trùm nhỏ nhất]]

==Tham khảo==
{{tham khảo}}

[[Thể loại:Cây (cấu trúc)]]
[[Thể loại:Giải thuật lý thuyết đồ thị]]
[[Thể loại:Lý thuyết đồ thị trong các bài toán tính toán]]